E-水没城市

https://ac.nowcoder.com/acm/contest/11247/E

#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
struct node{
    int a,b,c;
    bool operator<(const node&p)const{
        return c<p.c;
    }
};
int f[3010];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
constexpr int N = 2e4+10 ;
int e[N<<1],ne[N<<1],h[N<<1],w[N<<1],k=1;
void add(int a,int b,int c){
    e[++k]=b,ne[k]=h[a],h[a]=k;
    w[k]=c;
}
int dep[3001];
bool bfs(int S,int T){
    memset(dep,-1,sizeof dep);
    dep[S]=1;
    queue<int>q;
    q.push(S);
    while(!q.empty()){
        int t=q.front();q.pop();
        for(int i=h[t];i;i=ne[i]){
            int j=e[i];
            if(w[i]&&dep[j]==-1){
                dep[j]=dep[t]+1;
                q.push(j);
            }
        }
    }
    return dep[T]!=-1;
}
ll dfs(int s,int t,ll in){
    if(s==t)return in;
    ll out=0;
    for(int i=h[s];i;i=ne[i]){
        int j=e[i];
        if(w[i]&&dep[j]==dep[s]+1){
            ll x=dfs(j,t,min((ll)w[i],in-out));
            out+=x;
            w[i]-=x;
            w[i^1]+=x;
        }
    }
    if(!out)dep[s]=-1;
    return out;
}
ll dinic(int s,int t){
    ll ans=0;
    while(bfs(s,t))ans+=dfs(s,t,1e18);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<node>a(m);
    for(auto &[x,y,z]:a)cin>>x>>y>>z;
    sort(a.begin(),a.end());
    int lim=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(auto [a,b,c]:a){
        a=find(a),b=find(b);
        if(a==b)continue;
        f[a]=b;
        lim=c;
    }
    for(auto [a,b,c]:a)if(c<lim){
        add(a,b,lim-c);
        add(b,a,lim-c);
    }
    cout<<dinic(1,n);
}