Weights on Vertices and Edges [Test, Atcoder]

$WeightsonVerticesandEdges$Weights on Vertices and Edges

$Description$Description

有 $N$N 个点, $M$M 条边的无向图, 有 边权, <stron>, 请在 每一个联通块 中 $点权和$点权和 大于 $联通块中每条边权$联通块中每条边权 的前提下使得 边数 最大, 求 “最小割”. (雾</stron>

$N,M\&lt;=10^5$N,M<=105

$Solution$Solution

把每条边按 从小到大 排序, 依次加入图中, 相当于不断合并 联通块 .

每个联通块记录该联通块中 $不合法边数量:num$不合法边数量:num ,

设当前加入的边权为 $w$w, 合并时有 $2$2 种情况 :

1. $总点权\&gt;=w:$总点权>=w:
   将 新的联通块 $num$num 置为 $0$0.
2. $总点权\&lt;w:$总点权<w:
   将 新的联通块 $num$num 置为 $nu{m}_1+nu{m}_2+1$num1​+num2​+1.

若 边所连的两个点 为同一联通块时, 同样按上述方法处理.

num_1,num_2为要合并的联通块的不合法边的数量

$Code$Code

#include<bits/stdc++.h>
#define reg register

int read(){
        int s = 0, flag = 1;
        char c;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ c = getchar(); flag = -1; break; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

typedef long long ll;
const int maxn = 100005;

int N;
int M;
int F[maxn];
int X[maxn];
int num[maxn];

struct Edge_2{ int a, b; ll w; } E[maxn];

int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }

bool cmp(Edge_2 a, Edge_2 b){ return a.w < b.w; }

int main(){
        freopen("bridge.in", "r", stdin);
        freopen("bridge.out", "w", stdout);
        N = read(), M = read();
        for(reg int i = 1; i <= N; i ++) X[i] = read(), F[i] = i, num[i] = 0;
        for(reg int i = 1; i <= M; i ++){
                int u = read(), v = read(), w = read();
                E[i] = (Edge_2){ u, v, w };
        }
        std::sort(E+1, E+M+1, cmp);
        for(reg int i = 1; i <= M; i ++){
                int a = E[i].a, b = E[i].b, w = E[i].w;
                a = Find(a), b = Find(b);
                if(a != b){
                        if(X[a] + X[b] >= w) num[b] = 0;
                        else num[b] += num[a] + 1;
                        F[a] = b, X[b] += X[a];
                }else if(X[a] < w) num[a] ++;
        }
        int Ans = 0;
        for(reg int i = 1; i <= N; i ++){
                int t = Find(i);
                Ans += num[t];
                num[t] = 0;
        }
        printf("%d\n", Ans);
        return 0;
}

$Test\_5,16$Test_5,16