首页 > 代码库 > 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;}