求助,WA三个点

P3376 【模板】网络最大流

hllh @ 2019-06-01 20:20:17

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct xx{
    int from,to,data,nxt;
}e[200005];
queue<int>q;
int inf=100000007;
int n,m,s,T,tot=1,v[10005],level[10005];
void add(int a,int b,int c)
{

    e[++tot].from=a;
    e[tot].to=b;
    e[tot].data=c;
    e[tot].nxt=v[a];
    v[a]=tot;
}

bool bfs()
{
    memset(level,-1,sizeof(level));
    q.push(s);level[s]=0;
    while(!q.empty())
    {
        int k=q.front();q.pop();
        for(int j=v[k];j;j=e[j].nxt)
        {
            int t=e[j].to;
            if(e[j].data!=0&&level[t]==-1)
            {
                level[t]=level[k]+1;
                q.push(t);
            }
        }
    }
    if(level[T]!=-1) return true;
    else return false;  
}
int dfs(int u,int flow)
{
    if(u==T) return flow;
    int ret=flow;
    for(int j=v[u];j;j=e[j].nxt)
    {
        if(ret<=0) break;
        int t=e[j].to;
        if(e[j].data!=0&&level[t]==level[u]+1)
        {
            int k=dfs(t,min(e[j].data,ret));
            ret-=k;e[j].data-=k;e[j^1].data+=k;
        }
    }
    return flow-ret;
}
void dinic()
{
    int maxflow=0;
    while(bfs()==true)
    {
        maxflow+=dfs(s,inf);
    }
    printf("%d\n",maxflow);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&T);
    for(int i=1;i<=m;++i)
    {
        int ui,vi,wi;
        scanf("%d%d%d",&ui,&vi,&wi);
        add(ui,vi,wi);add(vi,wi,0);
    }
    dinic();
    return 0;   
}

by hllh @ 2019-06-01 20:25:47

数据。。。。。。

这都能过7个点

add(ui,vi,wi);add(vi,wi,0);

by oxbby @ 2019-07-22 11:53:24

怎么这么巧,我也是这个错误,看了好久都看不出来,直到看到这篇讨论……


|