AThousandSuns @ 2018-02-04 18:04:22
如题,下面这个程序wa3,4,5
#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
int to,cap,flow,nxt;
}e[200200];
int n,m,s,t,head[10010],el,dis[10010],cur[10010];
bool vis[10010];
int read(){
char ch;
while((ch=getchar()) && !isdigit(ch));
int sum=ch-'0';
while((ch=getchar()) && isdigit(ch)) sum=sum*10+ch-'0';
return sum;
}
void add(int u,int v,int c){
e[++el]=(edge){v,c,0,head[u]};
head[u]=el;
}
bool bfs(){
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
dis[s]=0;
vis[s]=true;
queue<int> q;
q.push(s);
while(!q.empty()){
int fnode=q.front();
for(int i=head[fnode];i;i=e[i].nxt){
int tnode=e[i].to;
if(!vis[tnode] && e[i].cap>e[i].flow){
dis[tnode]=dis[fnode]+1;
vis[tnode]=true;
q.push(tnode);
}
}
q.pop();
}
return vis[t];
}
int dfs(int fnode,int minres){
if(fnode==t || minres==0) return minres;
int rtf=0,f;
for(int &i=cur[fnode];i;i=e[i].nxt){
int tnode=e[i].to;
if(dis[fnode]+1==dis[tnode] &&(f=dfs(tnode,min(minres,e[i].cap-e[i].flow)))>0){
e[i].flow+=f;
e[i^1].flow-=f;
rtf+=f;
minres-=f;
if(minres==0) break;
}
}
return rtf;
}
int main(){
int i;
n=read();m=read();s=read();t=read();
for(i=1;i<=m;i++){
int u,v,c;
u=read();v=read();c=read();
add(u,v,c);
add(v,u,0);
}
int flow=0;
while(bfs()){
for(i=1;i<=n;i++) cur[i]=head[i];
flow+=dfs(s,2147483647);
}
printf("%d\n",flow);
}
by yyy14159 @ 2018-02-04 18:23:33
DFS里给反边减去流f的时候 i^1不是i的反边吧。 1^1=0 但你编号为1的边的反边是编号为2的边啊
by AThousandSuns @ 2018-02-04 21:18:44
@yyy14159 哇,原来是这里啊,感谢大佬