求助!Wa四个点~~~

P3376 【模板】网络最大流

starusc @ 2018-06-02 09:23:18

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define N 4000010
#define INF (long long )200000000000000
struct edge{
    int v,next;long long c;
}e[2*N];
int n,m,s,t,dis[N];//层数 
int first[N]={0},cnt=1,cur[N];
void add(int u,int v,long long c){
    e[++cnt].v=v;e[cnt].c=c;
    e[cnt].next=first[u];first[u]=cnt;
}
int bfs(){//编写层数 
    queue<int>q;
    q.push(s);
    memset(dis,-1,sizeof(dis));
    dis[s]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=first[u];i;i=e[i].next){//
            int v=e[i].v;//
            if(e[i].c>0&&dis[v]==-1){
                dis[v]=dis[u]+1;
                q.push(v);
                if(v==t)return 1;//到终点结束 
            }
        }
    }
    return 0;
}
int dfs(int x,long long  f){//当前点  最小残量 
    if(x==t||f==0)return f;//到终点或死路 
    long long used=0;//当前点已流出流量
    for(int &i=cur[x];i;i=e[i].next){
        if(e[i].c&&dis[e[i].v]==dis[x]+1){//有流量且满足层数要求 
            long long  w=dfs(e[i].v,min(f,(long long)e[i].c));
            if(!w)continue;//死路 
            used+=w;
            e[i].c-=w;e[i^1].c+=w;//正反边 x^1=比x大1大奇数或比x小1的偶数
            if(f==used)break; //用完所有流量不必再跑 
        }
    }
    if(!used)dis[x]=-1;//优化:无用的省略
    return used; 
}
long long  dinic(){
    long long  flow=0;
    while(bfs()){//终点有层数——>还有路 
        memcpy(cur,first,sizeof(first));
        flow+=dfs(s,INF);//增广路 
    }
    return flow;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s>>t;
    int u,v,c;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>c;
        add(u,v,c);//正 
        add(v,u,0);//反 
    }
    int r=dinic();
    cout<<r;//最大流 
    return 0;
} 

|