这组数据我的代码输出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;
}
求加强数据