64求助

P3376 【模板】网络最大流

ynxynx @ 2022-05-28 21:50:38

//64pt
#include<bits/stdc++.h>
using namespace std;
const int N=10000001;
int n,m,head[N],cnt=1,rad[N],f[N],s,t,vip[N];
struct node{
    int to,nxt,w;
}tr[N];
void add(int u,int v,int w){
    tr[++cnt].to=v;
    tr[cnt].w=w;
    tr[cnt].nxt=head[u];
    head[u]=cnt;
}
queue<int> que;
bool bfs() {//分层 
    for(int i=0;i<=n;i++) f[i]=0;
    que.push(s);
    f[s]=1;
    while (!que.empty()) {
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=tr[i].nxt) {
            int v=tr[i].to;
            if (f[v] || tr[i].w<=0) continue;//??? 
            f[v]=f[now]+1;//分层 
            que.push(v);
//          if(v==t) return 1;
        }
    }
    return f[t]!=0;
}
int dfs(int now,int a) {
    if (now==t) {
        return a;
    }
    int tmp=a;//流过这段的流量 
    for (int i=head[now];i;i=tr[i].nxt) {
        int v=tr[i].to;
        if (f[v]==f[now]+1 && tr[i].w>=0) {//可以走 
            int k=min(tmp,tr[i].w);//流 
            int dlt=dfs(v,k);//最小 
//          dlt=min(dlt,tmp);
            tr[i].w-=dlt;
            tr[i^1].w+=dlt;//残量 
            tmp-=dlt;
            if (tmp<=0) break;// 0
        }
    }
    return a-tmp;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    for (int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);//反边 
    }
    int ans=0,dlt=114514;
    while (bfs()) {
        ans+=dfs(s,1e9);//增广 
    }
    cout<<ans;
    return 0;
}
/*
5 6 1 5
1 5 1
2 5 1
1 2 99
2 3 99
3 4 99
4 5 99
*/

弱弱不会当前弧,求助!!


by Gao_yc @ 2022-05-28 22:35:09

答案没开long long啊。


by YBaggio @ 2022-05-31 21:19:00

没开longlong见祖宗


|