RT，

Record

Code:

#include <bits/stdc++.h>
#define ll long long
#define fe(x) (x&1?x+1:x-1)
#define pii pair<int,int>
#define mkp(x,y) make_pair(x,y)
using namespace std;
const int maxn=2e3+1;
const int maxm=2e3+1;
const int inf=0x3f3f3f3f;
struct edge{
    int to,next,ef;
}e[maxm*2];
int n,m,s,t,tot,h[maxn];
int height[maxn],flow[maxn],gap[maxn*4];
bool inq[maxn];
queue <int> q;
priority_queue <pii> pq;
inline void addEdge(int x,int y,int z){
    e[++tot]=(edge){y,h[x],z};
    h[x]=tot;
}
inline bool check(){
    memset(height,inf,sizeof(height));
    height[t]=0;
    q.push(t);
    while (!q.empty()){
        int now=q.front();
        q.pop();
        for (int i=h[now];i;i=e[i].next){
            int v=e[i].to;
            if (e[fe(i)].ef && height[v]>height[now]+1){
                height[v]=height[now]+1;
                q.push(v);
            }
        }
    }
    return height[s]!=inf;
}
inline void push(int x){
    for (int i=h[x];i;i=e[i].next){
        int v=e[i].to;
        if (e[i].ef && height[v]+1==height[x]){
            int d=min(flow[x],e[i].ef);
            e[i].ef-=d,e[fe(i)].ef+=d;
            flow[x]-=d,flow[v]+=d;
            if (v!=s && v!=t && !inq[v]){
                inq[v]=true;
                pq.push(mkp(height[v],v));
            }
            if (!flow[x]) break;
        }
    }
}
inline void relabel(int x){
    height[x]=inf;
    for (int i=h[x];i;i=e[i].next){
        int v=e[i].to;
        if (e[i].ef && height[v]+1<height[x]) height[x]=height[v]+1;
    }
}
inline int HLPP(){
    if (!check()) return 0;
    height[s]=n;
    for (int i=1;i<=n;i++) if (height[i]<inf) gap[height[i]]++;
    for (int i=h[s];i;i=e[i].next){
        int v=e[i].to;
        int f=e[i].ef;
        if (!f) continue;
        e[i].ef-=f,e[fe(i)].ef+=f;
        flow[s]-=f,flow[v]+=f;
        if (v!=s && v!=t && !inq[v]){
            inq[v]=true;
            pq.push(mkp(height[v],v));
        }
    }
    while (!pq.empty()){
        int now=pq.top().second;
        inq[now]=false;
        pq.pop();
        push(now);
        if (!flow[now]) continue;
        if (!(--gap[height[now]])) for (int i=1;i<=n;i++) if (i!=s && i!=t && height[i]>height[now] && height[i]<=n) height[i]=n+1;
        relabel(now);
        gap[height[now]]++;
        inq[now]=true;
        pq.push(mkp(height[now],now));
    }
    return flow[t];
}
int main(){
    scanf("%d%d",&m,&n);
    for (int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addEdge(x,y,z);
        addEdge(y,x,0);
    }
    s=1,t=n;
    printf("%d\n",HLPP());
    return 0;
}

悬赏一个关注