头像

lhqwd

北京化工大学




离线:7小时前



lhqwd
7小时前

最小生成树

定义 : 对于图 $ G = (V,E) $, 有 $n$ 个点, $m$ 条边, 由 $V$ 中所有 $n$ 个点和 $E$ 中 $n-1$ 条边构成的一个连通子图(即一棵树),称为 $G$ 的一个生成树, 边权值最小的为最小生成树.

求解方法:

  1. prim算法 $O(n^2)$
  2. kruskal算法 $O(mlogn)$

prim算法 :

一般用于稠密图:

#include <iostream>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 510;
int n,m;
int g[N][N];    //稠密图
int dist[N];    //表示某个结点到当前集合的最小距离(与dijkstra不同)
int st[N];      //是否在集合内

int prim()
{
    memset(dist, INF, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ ){

        int t = -1; 
        for (int j = 1; j <= n; j ++ )          //寻找不在集合内,且到集合距离最小的结点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;      //进入集合

        if (i && dist[t] == INF)    return INF; //不存在生成树
        if (i)  res += dist[t];

        for (int j = 1; j <= n; j ++ )      //更新其它结点
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n >> m;

    memset(g, INF, sizeof g);

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        g[a][b] = g[b][a] = min(g[a][b], v);    //无向图
    }

    int t = prim();

    if (t == INF)
        puts("impossible");
    else    
        cout << t << endl;

    return 0;
}

kruskal算法 :

一般用于稀疏图

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
const int M = 2 * N;
int n,m;

int f[N];       //并查集的操作

struct Edge{
    int a, b;
    int v;
}edge[M];

bool comp(Edge x, Edge y)       //自定义比较
{
    return x.v < y.v;
}

int find(int x)                 //寻找祖宗结点
{
    if (f[x] != x)  return f[x] = find(f[x]);
    return f[x];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1, comp);

    for (int i = 1; i <= n; i ++ )      //并查集的初始化
        f[i] = i;

    int res = 0;        //记录距离之和
    int cnt = 0;        //存储结点数量
    for (int i = 1; i <= m; i ++ ){      //枚举每条边

        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int fa = find(a);
        int fb = find(b);

        if (fa != fb){           //合并集合
            f[fa] = fb;
            res += v;
            cnt ++;
        }
    }
    if (cnt < n - 1)
        puts("impossible");
    else
        cout << res << endl;

    return 0;

}

AcWing 1140. 最短网络 原题链接

算法思路:

最小生成树的模板题, 输入矩阵形式, 采用prim算法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int g[N][N];
int n;
int dist[N];
int st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;

    for (int i = 1; i <= n; i ++ ){
        int t = -1;

        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;

        res += dist[t];

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> g[i][j];

    cout << prim() << endl;

    return 0;
}

AcWing 1141. 局域网 原题链接

算法思路 :

kruakal算法求最小生成树, 注意每次当两个点需要删边时, 将结果加上权值.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 220;

struct Edge{
    int a, b, v;

    bool operator < (const Edge &t)const 
    {
        return v < t.v;
    }
}edge[M];
int fa[N];
int n ,m;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}


int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= m; i ++ )
        cout << edge[i].v << endl;
    for (int i = 1; i <= m; i ++ ){
        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int aa = find(a);
        int bb = find(b);

        if (aa != bb)   fa[aa] = bb;
        else
            res += v;
    }

    cout << res << endl;

    return 0;
}

AcWing 1142. 繁忙的都市 原题链接

算法思路 :

同样是模板题, 注意理解题意, 要求被改造的道路能够连通整个图(被选入生成树里的点)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310, M = 8010;

struct Edge{
    int a, b, v;
    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}edge[M];

int n,m;
int fa[N];
int sum;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}


int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int aa = find(a);
        int bb = find(b);
        //cout << aa << ' ' << bb << endl;
        if (aa == bb)
            continue;
        else{
            sum ++;
            fa[aa] = bb;
            res = v;

        }
    }

    cout << sum << ' ' << res << endl;

    return 0;

}

AcWing 1143. 联络员 原题链接

算法思路 :

图中含有必选边和非必选边, 对于必选边我们直接加入到生成树中, 然后再根据kruskal算法加入非必选边

  • kruskal算法求最小生成树可以从中间开始
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, M = 10010;

struct Edge{
    int op, a, b, v;
    bool operator < (const Edge &t)const
    {
        if (op == t.op)
            return v < t.v;
        return op < t.op;
    }
}edge[M];
int fa[N];
int n, m;


int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}

int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int op, a, b, v;
        cin >> op >> a >> b >> v;
        edge[i] = {op, a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= m; i ++ ){
        int op = edge[i].op;
        int aa = find(edge[i].a);
        int bb = find(edge[i].b);
        int v = edge[i].v;

        if (op == 1){
            res += v;
            if (aa != bb)
                fa[aa] = bb;
        }else{
            if (aa == bb)
                continue;
            else{
                res += v;
                fa[aa] = bb;
            }
        }
    }


    cout << res << endl;

    return 0;
}

AcWing 1144. 连接格点 原题链接

算法思路 :

原图中有 $m * n$ 个点, 其中横向点之间、纵向点之间都有边, 根据kruskal算法,先加入纵向边(权值小),再加入横向边(权值大).
我们可以直接在加边时进行排序,避免sort().

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2 * 1e6 + 10, M = 2 * 1e6 + 10;
int g[1010][1010];
struct Edge{
    int a, b, v;

    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}edge[M];
int fa[N];
int n, m;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1, t = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            g[i][j] = t ++;

    for (int i = 1; i <= n * m; i ++ )
        fa[i] = i;

    int cnt = 0;
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j < n; j ++ ){
            int a = g[j][i], b = g[j + 1][i];
            int v = 1;
            //cout << a << ' ' << b << endl;
            edge[cnt ++] = {a, b, v};
        }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j < m; j ++ ){
            int a = g[i][j], b = g[i][j + 1];
            int v = 2;
            //cout << a << ' ' << b << endl;
            edge[cnt ++] = {a,b,v};
        }
    int x1, y1, x2, y2;
    while (~scanf("%d%d%d%d",&x1, &y1, &x2, &y2)){
        int a = g[x1][y1];
        int b = g[x2][y2];
        int aa = find(a);
        int bb = find(b);
        fa[aa] = bb;
    }

    int res = 0;

    for (int i = 0; i < cnt; i ++ ){
        int aa = find(edge[i].a);
        int bb = find(edge[i].b);
        int v = edge[i].v;
        if (aa == bb)
            continue;
        else{
            res += v;
            fa[aa] = bb;
        }
    }

    cout << res << endl;

    return 0;

}


活动打卡代码 AcWing 395. 冗余路径

lhqwd
9小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

const int N = 5010, M = 20010;

int h[N], e[M], ne[M], idx;

//时间戳:
int low[N], dfn[N];
int timecnt;

//栈:存储当前双联通分量里的结点
stack<int> stk;

//双连通分量的个数:
int dcc_cnt;
int id[N];

//记录某个边是不是桥:
int is_bridge[N];

//连通分量的度
int d[N];
int n,m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}


void tarjan(int u, int fa)              //u为当前结点,fa为其父节点,防止反向搜边
{
    low[u] = dfn[u] = ++ timecnt;
    stk.push(u);

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){        //没有被遍历过
            tarjan(j, i);
            low[u] = min(low[u], low[j]);       //更新u

            if (low[j] > dfn[u]){
                is_bridge[i] = is_bridge[i ^ 1] = 1;    //是桥
            }

        }else if (i != (fa ^ 1))        //不是父亲节点
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u]){
        dcc_cnt ++;
        int y;
        do{
            y = stk.top();
            stk.pop();
            id[y] = dcc_cnt;

        }while (y != u);
    }

}


int main()
{
    cin >> n >> m;
    memset (h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    tarjan(1, -1);

    for (int i = 0; i < idx; i ++ )     //遍历每条边
        if (is_bridge[i])
            d[id[e[i]]] ++;
    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i ++ )
        if (d[i] == 1)
            cnt ++;

    cout << (cnt + 1) / 2 << endl;

    return 0;
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

lhqwd
21小时前
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = 2 * N;

int n, m;
int h[N], e[M], ne[M], idx, w[M];
int din[N];
double f[N];
int toop[N];
int dout[N];
int cnt;

void add(int a, int b, int v)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = v, h[a] = idx ++;
}

void toopsort()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
        if (!din[i])
            q.push(i);

    while (q.size()){
        int u = q.front();
        q.pop();

        toop[++ cnt] = u;
        for (int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            din[j] --;
            if (!din[j])
                q.push(j);
        }
    }
}

int main()
{
    cin >> n >> m;
    memset (h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        add(a, b, v);
        din[b] ++;
        dout[a] ++;
    }

    toopsort();

    f[n] = 0;

    for (int i = cnt - 1; i >= 1; i -- ){
        int u = toop[i];
        for (int k = h[u]; k != -1; k = ne[k]){
            int j = e[k];

            f[u] += (f[j] + w[k]) * 1.0 / dout[u];

        }
    }

    printf("%.2f\n",f[1]);

    return 0;
}



lhqwd
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <stack>

using namespace std;

const int N = 1e5 + 10, M = 2 * 1e6 + 10;
typedef long long LL;
int h[N], hs[N], e[M], ne[M], idx;

int timecnt;
int dfn[N], low[N];
stack<int> stk;
int scc_cnt;
int in_stk[N];
int sizes[N];
int id[N];

int f[N], g[N];
unordered_set<LL> used;
int n, m, mod;

void add(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timecnt;

    stk.push(u);
    in_stk[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if (in_stk[j])
                low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]){
        scc_cnt ++;
        int y;
        do{
            y = stk.top();
            stk.pop();
            in_stk[y] = 0;
            id[y] = scc_cnt;
            sizes[scc_cnt] ++;
        }while (y != u);
    }

}

int main()
{
    cin >> n >> m >> mod;
    memset (h, -1, sizeof h);
    memset (hs, -1, sizeof hs);

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        scanf("%d%d",&a, &b);
        add(h, a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j]){
            int k = e[j];

            int a = id[i], b = id[k];
            if (a != b && !used.count((LL)a * 1e6 + b)){
                add(hs, a, b);
                used.insert((LL)a * 1e6 + b);
            }
        }

    for (int i = scc_cnt; i ; i -- ){
        if (!f[i]){
            f[i] = sizes[i];
            g[i] = 1;
        }
        for (int j = hs[i]; j != -1; j = ne[j]){
            int k = e[j];
            if (f[k] < f[i] + sizes[k]){
                f[k] = f[i] + sizes[k];
                g[k] = g[i];
            }else if (f[k] == f[i] + sizes[k])
                    g[k] = (g[k] + g[i]) % mod;
        }
    }

    int maxn = 0;
    int sum = 0;

    for (int i = 1; i <= scc_cnt; i ++ )
        if (f[i] > maxn){
            maxn = f[i];
            sum = g[i];
        }else if (f[i] == maxn)
            sum = (g[i] + sum) % mod;

    cout << maxn << endl << sum << endl;

    return 0;
}




活动打卡代码 AcWing 367. 学校网络

lhqwd
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

const int N = 110, M = N * N / 2;

int h[N], e[M], ne[M], idx;

int timecnt;
int low[N], dfn[N];
stack<int> stk;
int scc_cnt;
int id[N];
int in_stk[N];
int dout[N];
int din[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timecnt;
    stk.push(u);
    in_stk[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u]){
        scc_cnt ++;
        int y;
        do{
            y = stk.top();
            stk.pop();
            in_stk[y] = 0;
            id[y] = scc_cnt;

        }while (y != u);
    }

}

int main()
{
    int n;
    cin >> n;
    memset (h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ){
        int b;
        while (cin >> b && b){
            add(i, b);
        }
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j]){
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b){
                dout[a] ++;
                din[b] ++;
            }
        }

    int in_cnt = 0;
    int out_cnt = 0;
    for (int i = 1; i <= scc_cnt; i ++ ){
        if (!dout[i]){
            out_cnt ++;
        }
        if (!din[i]){
            in_cnt ++;
        }
    }

    if (scc_cnt == 1)
        cout << 1 << endl <<  0 << endl;
    else
        cout << in_cnt << endl << max(in_cnt, out_cnt) << endl;

    return 0;

}


活动打卡代码 AcWing 1174. 受欢迎的牛

lhqwd
1天前
#include <iostream>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

const int N = 1e5 + 10, M = 5e4 + 10;

int h[N], e[M], ne[M], idx;

int timecnt;            //时间戳
int dfn[N];             //每个点的时间戳
int low[N];             //low[u] : u所在的子树中所有点中所能向上走到的时间戳最小的点
int scc_cnt;            //强连通分量的数量
int id[N];              //id[i] : 表示i号点所在的强连通分量的编号
stack<int> stk;         //存储当前强连通分量里的所有点
int in_stk[N];          //记录该点是否在栈中

int sizes[N];            //强连通分量的结点数量
int dout[N];            //每个强连通分量的出度
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++ timecnt;
    stk.push(u);
    in_stk[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){               //j点没有被遍历过,j点一定是在子树中

            tarjan(j);              //遍历j
            low[u] = min(low[u], low[j]);       //遍历过后的j的low可能已经找到一个更高的结点,所以要去更新u

        }
        else if (in_stk[j])         //j在栈中,则j和u之间一定是一条横叉边或向前边,即j的时间戳一定比u小
            low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]){          //到此处,u的所有边已经遍历完,如果low[u] = dfn[u] : 得到了一个强连通分量
        scc_cnt ++;
        int y;                      //此时该强连通分量里的点全在栈中,全部取出
        do{
            y = stk.top();
            stk.pop();
            id[y] = scc_cnt;
            sizes[scc_cnt] ++;
        }while (y != u);
    }

} 


int main()
{
    cin >> n >> m;

    memset (h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j]){
            int k = e[j];

            int a = id[i], b = id[k];
            if (a != b){                //二者不在同一个强连通分量内,则由i -> k的边是缩点后点一条边,对于连通分量: a -> b
                dout[a] ++;
            }
        }

    int cnt = 0;
    int sum = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!dout[i]){
            cnt ++;
            sum = sizes[i];
            if (cnt > 1){
                sum = 0;
                break;
            }
        }

    cout << sum << endl;

    return 0;
}


活动打卡代码 AcWing 352. 闇の連鎖

lhqwd
1天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1000010, M = 2 * N;

int h[N], e[M], ne[M], idx;

int fa[N][20];
int depth[N];
int d[N];           //差分数组
int n, m;
int st[N];
int ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs()
{
    memset (depth, 0x3f, sizeof depth);
    depth[1] = 1;
    depth[0] = 0;

    queue<int> q;
    q.push(1);

    while (q.size()){
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];

            if (depth[j] > depth[t] + 1){
                depth[j] = depth[t] + 1;
                q.push(j);

                fa[j][0] = t;
                for (int k = 1; k <= 17; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b])
        swap(a, b);

    for (int k = 17; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];

    if (a == b)
        return a;

    for (int k = 17; k >= 0; k -- )
        if (fa[a][k] != fa[b][k]){
            a = fa[a][k];
            b = fa[b][k];
        }

    return fa[a][0];
}

int dfs(int u, int f)
{
    int res = d[u];

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (j != f){
            int s = dfs(j,u);
            if (s == 0)
                ans += m;
            else if (s == 1)
                ans ++;
            res += s;
        }
    }

    return res;
}


int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    bfs();

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        d[a] ++, d[b] ++ , d[p] -= 2;
    }

    dfs(1, -1);    

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 356. 次小生成树

lhqwd
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 6 * 1e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx, w[M];           //存最小生成树

struct Edge{
    int a, b, v;
    int used;
    bool operator < (const Edge &t)const 
    {
        return v < t.v;
    }
}edge[M];
int p[N];           //并查集的父节点

int depth[N];
int fa[N][20];      //lca的父节点

int dist1[N][20];       //最大值
int dist2[N][20];       //次大值

void add(int a, int b, int v)
{
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}

int find(int x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}

LL kruskal()
{
    for (int i = 1; i <= n; i ++ )
        p[i] = i;
    LL res = 0;
    for (int i = 1; i <= m; i ++ ){
        int a = find(edge[i].a);
        int b = find(edge[i].b);
        int v = edge[i].v;

        if (a != b){
            p[a] = b;
            res += v;
            edge[i].used = 1;
            add(edge[i].a, edge[i].b, v);
            add(edge[i].b, edge[i].a, v);
        }
    }

    return res;
}

void bfs(int u)
{
    memset (depth, 0x3f, sizeof depth);
    depth[0] = 0;
    depth[u] = 1;

    queue<int> q;
    q.push(u);

    while (q.size()){
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]){
            int j = e[i];

            if (depth[j] > depth[t] + 1){
                depth[j] = depth[t] + 1;
                q.push(j);


                fa[j][0] = t;
                dist1[j][0] = w[i];         //j向上一个点是t,dist = w[j -> t]
                dist2[j][0] = -INF;

                //处理j的fa, dist1, dist2
                for (int k = 1; k <= 17; k ++ ){
                    dist1[j][k] = -INF;
                    dist2[j][k] = -INF;
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];
                    int d[4] = {dist1[j][k - 1], dist2[j][k - 1], dist1[anc][k - 1], dist2[anc][k - 1]};
                    for (int z = 0; z < 4; z ++ ){
                        if (d[z] > dist1[j][k]){
                            dist2[j][k] = dist1[j][k];
                            dist1[j][k] = d[z];
                        }
                        else if (d[z] != dist1[j][k] && dist2[j][k] < d[z])
                            dist2[j][k] = d[z];
                    }

                }
            }

        }
    }
}

int lca(int a, int b, int v)
{
    int d1 = -INF;
    int d2 = -INF;
    int d[2 * N];
    int cnt = 0;
    if (depth[a] < depth[b])
        swap(a, b);

    for (int k = 17; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b]){
            d[cnt ++] = dist1[a][k];
            d[cnt ++] = dist2[a][k];
            a = fa[a][k];
        }

    if (a != b)
        for (int k = 17; k >= 0; k -- )
            if(fa[a][k] != fa[b][k]){
                d[cnt ++] = dist1[a][k];
                d[cnt ++] = dist2[a][k];
                d[cnt ++] = dist1[b][k];
                d[cnt ++] = dist2[b][k];
                a = fa[a][k];
                b = fa[b][k];
            }

    d[cnt ++] = dist1[a][0];
    d[cnt ++] = dist2[b][0];
    for (int i = 0; i < cnt; i ++ )
        if (d[i] > d1){
            d2 = d1;
            d1 = d[i];
        }else if (d[i] != d1 && d[i] > d2)
                    d2 = d[i];

    if (v > d1)
        return v - d1;
    if (v > d2)
        return v - d2;
    return INF;
}

int main()
{
    cin >> n >> m;
    memset (h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a,b,v,0};
    }
    sort(edge + 1, edge + m + 1);

    LL sum = kruskal();             //求最小生成树,同时建图

    bfs(1);
    LL res = 1e18;

    for (int i = 1; i <= m; i ++ )
        if (!edge[i].used){
            int a = edge[i].a;
            int b = edge[i].b;
            int v = edge[i].v;

            res = min(res, sum + lca(a, b, v));
        }


    cout << res << endl;
    return 0;
}



活动打卡代码 AcWing 1171. 距离

lhqwd
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int,int> PII;

const int N = 2e4 + 10, M = N * 2;

int h[N], e[M], w[M], ne[M], idx;

int n,m;

vector<PII> query[N];           //query[i].frist表示i对应的另一个节点,query[i].second表示询问编号
int res[N];                     //第i个询问的结果
int dist[N];                    //每个点到根节点的距离
int st[N];                      //记录每个节点的状态, 0: 没有遍历, 1 : 遍历没有回溯, 2 : 已经回溯而且被合并
int fa[N];                      //并查集需要


void add(int a, int b, int v)
{
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}

void bfs(int u)
{
    memset (dist, -1, sizeof dist);
    dist[u] = 0;

    queue<int> q;
    q.push(u);

    while (q.size()){
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];

            if (dist[j] == -1){
                dist[j] = dist[t] + w[i];
                q.push(j);
            }
        }
    }
}

void tarjan(int u)
{
    st[u] = 1;          //这个节点被遍历

    //遍历该节点的子树
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!st[j]){     //j节点还没有被遍历

            tarjan(j);  //开始遍历j节点
            fa[j] = fa[u];  //合并
        }
    }

    st[u] = 2;          //到这里u节点的子树已经遍历并回溯完毕,u节点也被标记为2

    for (auto it : query[u]){
        int t = it.first;
        int id = it.second;
        if (st[t] == 2){
            int lca = find(t);
            res[id] = dist[t] + dist[u] - 2 * dist[lca];
        }
    }

}



int main()
{
    cin >> n >> m;
    memset (h, -1, sizeof h);

    for (int i = 1; i < n; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        add(a, b, v), add(b, a, v);
    }

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        if (a != b){
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }

    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    bfs(1);                 //求各个节点到根节点的距离

    tarjan(1);    


    for (int i = 1; i <= m; i ++ )
        cout << res[i] << endl;

    return 0;
}



活动打卡代码 AcWing 1172. 祖孙询问

lhqwd
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 4 * 1e4 + 10, M = 2 * N;

int h[N], e[M], ne[M], idx;
int n, m;

int fa[N][20];          //fa[i][j] : i号节点向上跳2^j步后的节点
int depth[N];           //记录节点深度

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0;           //哨兵
    depth[root] = 1;        //根节点

    queue<int> q;
    q.push(root);

    while (q.size()){
        int u = q.front();
        q.pop();


        for (int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];

            if (depth[j] > depth[u] + 1){
                depth[j] = depth[u] + 1;
                q.push(j);

                //初始化fa数组:
                fa[j][0] = u;       //j节点向上跳一位就是u节点
                for (int k = 1; k <= 15; k ++ )         //预先估计k的上限
                    fa[j][k] = fa[fa[j][k - 1]][k - 1]; //fa[j][k - 1]向上跳2^(k - 1) 就是 fa[j][k]

            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b])
        swap(a, b);

    //第一个操作:将a向上跳到与b同层
    for (int k = 15; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];

    if (a == b)
        return a;

    //第二个操作:将a, b同时向上跳
    for (int k = 15; k >= 0; k -- )
        if (fa[a][k] != fa[b][k]){
            a = fa[a][k];
            b = fa[b][k];
        }

    return fa[a][0];

}


int main()
{
    cin >> n;
    memset (h, -1, sizeof h);
    int root = 0;
    for (int i = 1; i <= n; i ++ ){
        int a, b;
        cin >> a >> b;
        if (b == -1)
            root = a;           //找到根节点
        else{
            add(a, b);
            add(b, a);
        }
    }

    bfs(root);                  //预处理两个数组

    cin >> m;
    while (m -- ){
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        if (p == a)
            puts("1");
        else if (p == b)
            puts("2");
        else
            puts("0");
    }


    return 0;
}