2020/6/26 甚至没有用反向弧也能过

P3376 【模板】网络最大流

mrchen116 @ 2020-06-26 22:26:49

这组数据我的代码输出1,实际答案是2,但我的代码AC了

6 7 1 6
1 2 1
2 4 1
4 6 1
1 3 1
3 4 1
2 5 1
5 6 1

我的AC代码(无反向弧

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct Eg
{
    int from,to,c;
    Eg(int u,int v,int cc):from(u),to(v),c(cc){}
};
vector<Eg> edge;
vector<int> g[10001];
int n,m,s,t,maxf[10001],pass[10001];
long long ans=0;
void maxflow()
{
    while(1)
    {
        memset(maxf,0,sizeof(maxf));
        memset(pass,0,sizeof(pass));
        queue<int>Q;
        Q.push(s);
        maxf[s]=0x3f3f3f;
        while(!Q.empty())
        {
            int u=Q.front();
            Q.pop();
            for(int i=0;i<g[u].size();i++)
            {
                Eg& e=edge[g[u][i]];
                if(maxf[e.to]==0&&e.c>0)
                {
                    pass[e.to]=g[u][i];
                    maxf[e.to]=min(maxf[u],e.c);
                    Q.push(e.to);
                }
                if(maxf[t])break;
            }   
        }
        if(!maxf[t])break;
        for(int i=t;i!=s;i=edge[pass[i]].from)
        {
            edge[pass[i]].c-=maxf[t];
        //  edge[pass[i]^1].c+=maxf[t];
        }
        ans+=maxf[t];
    }
}
int main()
{
    //freopen("sb.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        edge.push_back(Eg(u,v,w));
        //edge.push_back(Eg(v,u,0));
        int len=edge.size();
        g[u].push_back(len-1);
        //g[v].push_back(len-1);
    }
    maxflow();
    printf("%lld",ans);
    return 0;
}

求加强数据


by mrchen116 @ 2020-06-26 22:27:54

数据的图是这个


by FZzzz @ 2020-06-26 22:30:33

@一扶苏一


by David_H_ @ 2020-06-26 22:31:21

盲猜请求加强数据


by ezoixx130 @ 2020-06-26 22:32:17

@ezoixx130


by deep_in_the_blue @ 2020-06-26 22:34:35

ezoi@自己珂海星(


by zhy137036 @ 2020-06-26 22:37:06

我 at 我 自 己


by zhy137036 @ 2020-06-26 22:37:15

@zhy137036


by ezoixx130 @ 2020-06-26 22:38:32

@mrchen116 感谢您的贡献!已添加 hack 数据。


by zztqwq @ 2020-06-26 22:43:44

@zzt_


by SisconHL @ 2020-06-26 22:44:16

@hepta_lhd


| 下一页