Weights on Vertices and Edges [Test, Atcoder]

$mathcal{Description}$

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

$N, M<=10^5$

$mathcal{Solution}$

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

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

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

$总点权 >= w:$
将 新的联通块 $num$ 置为 $0$ .
$总点权 < w:$
将 新的联通块 $num$ 置为 $num_1+num_2+1$ .

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

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

$mathcal{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
", Ans);
        return 0;
}

$Test\_5,16$