3月31日 EK模板 在奋战了一个中午之后终于........
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 2000
#define maxx 9999999
#define min(x,y) x<y?x:y //**这里是不用return的
int n,m,capacities[maxn][maxn],pre[maxn];
queue<int> Q;
void clear()
{
memset(capacities,0,sizeof(int));
memset(pre,0,sizeof(int));
}
int bfs(int src,int des)
{
int flag=0;
int increasement=maxx;
while(!Q.empty()) Q.pop();
for(int i=1;i<=n;i++) pre[i]=-1;
pre[src]=0;
Q.push(src);
while(!Q.empty())
{
int now=Q.front();//注意啊这里是front而不是pop
Q.pop();
if(now==des) break;//这里漏写了一句导致死循环QAQ
for(int i=1;i<=n;i++)
if(capacities[now][i]>0&&i!=now&&pre[i]==-1)
{
increasement=min(increasement,capacities[now][i]);
pre[i]=now;
Q.push(i);
}
}
if(pre[des]==-1) return 0;
return increasement;
}
int maxflow(int src,int des)
{
int total=0;
int increasement=0;
//对于下面的代码：我刚才居然用的是if语句：“标程用的是循环，其实src和des没有改变的情况下好像是一样的吧 ”
//吃枣药丸，不用循环你怎么使用反向流啊傻
//虽然说src和des没有改变，但是capacities改变会使bfs的结果改变的
while(increasement=bfs(src,des)!=0)
{
int last=des,k;
while(last!=src&&last!=0)
{
k=pre[last];//**就是这里写错了，这里记得注意前后顺序啊
capacities[k][last]-=increasement;
capacities[last][k]+=increasement;
last=k;
}
total+=increasement;//这里不确定是不是这样加的 ,但标程是这么写的，这么暴力啊
}
return total;
}
int main()
{
int temp1,temp2,x;
scanf("%d%d",&n,&m);
clear();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&temp1,&temp2,&x);
if(temp1==temp2) continue; //这里要提前判断起点和终点是否相同
capacities[temp1][temp2]+=x;//有可能重复
}
printf("%d \n",maxflow(1,n));
}
评论