蒟蒻刚学网络流,求大佬查错

P3376 【模板】网络最大流

wubaiting2020 @ 2019-05-03 16:14:18

RT,我用的Dinic

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n,m,ss,tt;
int h[200005],cnt=0;
int num[200005];//num记录点的层 
struct node{int nx,to,v;}w[200005];
void AddEdge(int x,int y,int z){w[++cnt].to=y;w[cnt].v=z;w[cnt].nx=h[x];h[x]=cnt;}
int BFS(int s,int t)
{
    queue<int>q;
    memset(num,-1,sizeof(num));
    num[s]=0;//初始化
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        if(x==t)return 1;
        for(int i=h[x];i;i=w[i].nx)
        {
            int y=w[i].to;
            if(num[y]==-1&&w[i].v>0){num[y]=num[x]+1;q.push(y);}
        }
    }
    return 0;
}
int DFS(int x,int t,int maxx)
{
    int ans=0,d=0;
    if(x==t)return maxx;
    for(int i=h[x];i;i=w[i].nx)
    {
        int y=w[i].to;
        if(w[i].v>0&&num[y]==num[x]+1)//必须按层序走才能保证最短路
        {
            d=DFS(y,min(w[i].v,maxx),t);
            w[i].v-=d;
            w[i^1].v+=d;//更新正向弧和反向弧的容量
            ans+=d;
            maxx-=d;
            if(maxx==0)return ans;
        }
    }
    return ans;
}
void Dinic()
{
    int ans=0;
    while(BFS(ss,tt))ans+=DFS(ss,tt,0x3f3f3f3f);
    printf("%d",ans);
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&ss,&tt);
    for(int i=1;i<=m;i++)
    {
        int xx,yy,zz;
        scanf("%d %d %d",&xx,&yy,&zz);
        AddEdge(xx,yy,zz);
        AddEdge(yy,xx,0);
    }
    Dinic();
    return 0;
}

by wubaiting2020 @ 2019-05-03 16:56:03

Orz @zyzzyzzyzzyz


by liuyifan @ 2019-05-03 16:58:04

@zyzzyzzyzzyz 可以看看我的吗 谢了 奆佬 讨论地址


by zyzzyzzyzzyz @ 2019-05-03 17:24:02

@liuyifan 我是蒟蒻QAQ


上一页 |