poj1273 最大流-白红宇

poj1273 最大流

阅读量：4153 次

发布时间：2019-05-25

本文共 1938 字，大约阅读时间需要 6 分钟。

用的是EdmondsKarp

程序可以再优化的，懒得优化了

EdmondsKarp

#include 
   
    #include
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxNode = 202;int N = 201;//edgeint M = 201;//nodeconst int maxInt = numeric_limits
        
         ::max();int g[maxNode][maxNode];int f[maxNode][maxNode];int residual[maxNode][maxNode];int pre[maxNode];bool BFS(){ queue
         
           q; q.push(1); memset(pre,0,sizeof(int)*(M+1)); int used[maxNode]; memset(used,0,sizeof(int)*(M+1)); used[1] = 1; while (!q.empty()) { int curr = q.front(); q.pop(); for (int i=1;i<=M;++i) { if(residual[curr][i]>0 && !used[i]) { pre[i] = curr; if(i==M) return true; q.push(i); used[i] = 1; } } } return false;}void EdmondsKarp(){ while (BFS()) { int minF = maxInt; int curr = M; int beg=0,end = 0; while (curr!=1) { int preNode = pre[curr]; if(minF > residual[preNode][curr]) { minF = residual[preNode][curr]; beg = preNode; end = curr; } curr = preNode; } curr = M; while (curr != 1) { int preNode = pre[curr]; f[preNode][curr] +=minF; residual[preNode][curr] -=minF; residual[curr][preNode] = f[preNode][curr]; curr = preNode; } } int sum=0; for (int i=1;i

下面是别人优化的比较好的

#include
   
    #include
    
     #include
     
      using namespace std;#define inf INT_MAXint n,m,a[205][205],pre[205];int bfs(){    queue
      
       Q;    Q.push(1);    pre[1]=0;    memset(pre,-1,sizeof(pre));    int t,i;    while(!Q.empty())    {       t=Q.front();       Q.pop();       for(i=2;i<=n;i++)       if(pre[i]==-1&&a[t][i]>0)       {          pre[i]=t;          Q.push(i);          if(i==n)   return 1;       }    }    return -1;}int maxflow(){    int res=0,ans,t;    while(bfs()==1)    {       t=n;       ans=inf;       while(t!=1)       {           if(a[pre[t]][t]