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