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 impuk @ 2020-06-26 22:46:30

@—只爬行者


by Alan_Zhao @ 2020-06-26 22:48:54

@Alan_Zhao


by CCCloud @ 2020-06-26 22:51:07

@宿宇·弦歌


by 7919_144_5237 @ 2020-06-26 23:25:45

@4elkc1707


by AMIRIOX無暝 @ 2020-06-26 23:27:13

@AMIRIOX無暝


by k3v1n070828 @ 2020-06-26 23:32:17

@M652


by RK_INF @ 2020-06-26 23:32:20

@✨蒟蒻小M_qwq✨


by t162 @ 2020-06-27 10:27:28

@Bambusoideae


by mrchen116 @ 2020-06-28 21:39:22

滑稽@mrchen116


by derta @ 2020-06-29 08:59:15

@wang_yue_xi


上一页 |