Isprime @ 2019-08-16 16:14:25
#include<cstdio>
#include<queue>
#include<algorithm>
#define MAXN 10001
#define MAXM 200001
#define ri register int
#define INF 0x7ffffff
using namespace std;
queue<int> q;
int n,m,s,t,edge_sum,maxflow;
int head[MAXM],pre[MAXN],flow[MAXN];
struct Edge{
int next,to,dis;
}edge[MAXM];
inline void addedge(int from,int to,int dis){
edge[++edge_sum].next=head[from];
edge[edge_sum].to=to;
edge[edge_sum].dis=dis;
head[from]=edge_sum;
}
inline int bfs(int s,int t){
while(!q.empty()) q.pop();
for(ri i=1;i<=n;i++) pre[i]=-1;
pre[s]=0;
q.push(s);
flow[s]=INF;
while(!q.empty()){
int x=q.front();
q.pop();
if(x==t) break;
for(ri i=head[x];i;i=edge[i].next){
if(pre[edge[i].to]==-1){
pre[edge[i].to]=x;
flow[edge[i].to]=min(flow[x],edge[i].dis);
q.push(edge[i].to);
}
}
}
if(pre[t]==-1) return -1;
else return flow[t];
}
inline void EK(int s,int t){
int increase=0;
while((increase=bfs(s,t))!=-1){
int k=t;
while(k!=s){
int last=pre[k];
for(ri i=head[last];i;i=edge[i].next){
if(edge[i].to==k){
edge[i].dis-=increase;
break;
}
}
for(ri i=head[k];i;i=edge[i].next){
if(edge[i].to==last){
edge[i].dis+=increase;
break;
}
}
k=last;
}
maxflow+=increase;
}
}
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(ri x,y,z,i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,0);
}
EK(s,t);
printf("%d\n",maxflow);
return 0;
}
为什么程序运行到
pre[edge[i].to]=x;
的时候死循环了?
by lvneg1 @ 2019-08-16 16:15:55
orz