首页 > 代码库 > POJ1273 最大流 EK算法
POJ1273 最大流 EK算法
套了个EK的模板
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <climits>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long longusing namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 220;queue <int> que;int n, m, max_flow; //max_flow是最大流int map[MAXN][MAXN], flow[MAXN][MAXN]; // map[i][j]是每条边的容量,flow[i][j]是每条边的流量int res[MAXN], pre[MAXN]; //res[]是每个点的剩余流量,pre[]是每个点的父亲void init(){ memset(map,0,sizeof(map)); memset(pre,0,sizeof(pre));}bool bfs(int src, int des){ int index; memset(pre, -1, sizeof(pre)); while(!que.empty()) que.pop(); //残余流量得变0,一开始所有点都没流入对吧 pre[src] = 0; //源点嘛,父亲为0 que.push(src); //从源点开始进行BFS找增广路 while(!que.empty()){ index = que.front(); que.pop(); for(int i = 1; i <= n; ++i){ //遍历所有点,找可行边 if(pre[i] == -1 && map[index][i] > 0){ //该点剩余流量为0 且 容量大于流量,也就是找到了新的结点 pre[i] = index; //找到新结点,父节点得记录一下吧 if(i == des) return true; que.push(i); } } } return false;}int MaxFlow(int src, int des){ int i, maxflow = 0; while(bfs(src, des)){ int minflow = INF; for(i = des; i != src; i = pre[i]) minflow = min(minflow, map[pre[i]][i]); //如果u的剩余流量能填满uv就填满,不能的话就把u这点的流量全部流向uv for(i = des; i != src; i = pre[i]){ //如果还能增广,那么回溯,从汇点往回更新每条走过的边的流量 map[pre[i]][i] -= minflow; //更新正向流量 (注意这里更新的是流量,而不是容量) map[i][pre[i]] += minflow; //更新反向流量 } maxflow += minflow; } return maxflow;}int main(){ int x, y, val; while(EOF != scanf("%d%d",&m,&n)){ init(); while(m--){ scanf("%d%d%d",&x,&y,&val); map[x][y] += val; //有重边 } printf("%d\n",MaxFlow(1, n)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。