S-T Mincut [CodeChef][最小割树][Kruskal]

题目

给定矩阵 $a_{i,j}$ ，然后可以让边权+1,求调整后存在一个图满足 $a_{i,j}$ 为 $i,j$ 间的最小割
问最小代价

思路

直接从最小割树考虑就变成构造树的问题
考虑从大到小加边构造树，如果某个时刻加边后形成圈，那么此时加的边就是最小边，但是圈上边权大的边无法变小，就只能它变大
实现就是求出最小割森林后求现在割边和减去给定的

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<cstdio>
#include<queue>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')f=1;c=getchar();}while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define mp make_pair
const int MAXN=1000;
const int INF=0x3f3f3f3f;
const int MAXM=35000;
int a[MAXN+5][MAXN+5];
struct Edge{
    int u,v,w;friend bool operator < (Edge a,Edge b){
    return a.w>b.w;}
}edge[MAXN*MAXN+5];
int fa[MAXN+5];
vector<pair<int,int> > G[MAXN+5];
LL sum1,sum2;
void DFS(int u,int fa,int w){
    if(w!=INF)sum1+=w;for(int i=0;i<(int)G[u].size();i++){
    int v=G[u][i].first,nw=min(w,G[u][i].second);if(v==fa) continue;DFS(v,u,nw);}return ;
}
int Find(int u){
    return fa[u]==u?u:(fa[u]=Find(fa[u]));}
int main(){
    int T=read();while(T--){
    sum1=sum2=0;int n=read(),ecnt=0;for(int i=1;i<=n;i++)G[i].clear(),fa[i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=read(),sum2+=a[i][j],edge[++ecnt]=(Edge){
    i,j,a[i][j]};sort(edge+1,edge+ecnt+1);for(int i=1;i<=ecnt;i++){
    int u=edge[i].u,v=edge[i].v,w=edge[i].w;int fu=Find(u),fv=Find(v);if(fu==fv) continue;G[u].push_back(mp(v,w)),G[v].push_back(mp(u,w));fa[fu]=fv;}for(int i=1;i<=n;i++)DFS(i,0,INF);printf("%lld\n",sum1-sum2);}return 0;
}