网络流最经典的入门题各种网络流算法都能AC。 poj 1273 Drainage Ditches-白红宇

网络流最经典的入门题各种网络流算法都能AC。 poj 1273 Drainage Ditches

阅读量：5908 次

发布时间：2019-06-19

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

题目抽象：给你m条边u,v,c。 n个定点，源点1，汇点n.求最大流。最好的入门题，各种算法都可以拿来练习

（1）：一般增广路算法 ford()

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
              10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   14 using namespace std; 15 typedef long long LL; 16 const int INF = 0x4fffffff; 17 const double EXP = 1e-5; 18 const int MS = 10005; 19 const int SIZE = 10005; 20 21 struct edge 22 { 23 int c, f; 24 }edges[MS][MS]; 25 26 int n, m; 27 28 int flag[MS]; 29 int pre[MS]; 30 int alpha[MS]; 31 32 int que[SIZE]; 33 34 int u; 35 int qs, qe; 36 int i, j; 37 38 void ford() 39 { 40 while (1) 41 { 42 // label method 43 memset(flag, 0xff, sizeof(flag)); 44 memset(pre, 0xff, sizeof(pre)); 45 memset(alpha, 0xff, sizeof(alpha)); 46 flag[1] = 0; 47 pre[1] = 0; 48 alpha[1] = INF; 49 qs = qe = 0; 50 que[qe++] = 1; 51 52 while (qs < qe&&flag[n ] == -1) 53 { 54 u = que[qs++]; 55 for (int i = 1; i <= n; i++) 56 { 57 if (flag[i] == -1) 58 { 59 if (edges[u][i].c >0&&edges[u][i].f < edges[u][i].c) 60 { 61 flag[i] = 0; pre[i] = u; 62 alpha[i] = min(alpha[u], edges[u][i].c - edges[u][i].f); 63 que[qe++] = i; 64 } 65 else if (edges[i][u].c>0&&edges[i][u].f>0) 66 { 67 flag[i] = 0; pre[i] = -u; 68 alpha[i] = min(alpha[u], edges[i][u].f); 69 que[qe++] = i; 70 } 71 } 72 } 73 flag[u] = 1; 74 } // END OF WHILE 75 if (flag[n ] == -1 || alpha[n ] == 0) 76 break; // END OF WHILE 77 78 int k1 = n , k2 = abs(pre[k1]); 79 int a = alpha[n ]; 80 while (1) 81 { 82 if (edges[k2][k1].c>0) //用f是否==INF来判断正向 83 edges[k2][k1].f += a; 84 else 85 edges[k1][k2].f -= a; 86 if (k2 == 1) 87 break; 88 k1 = k2; 89 k2 = abs(pre[k1]); 90 } // END OF WHILE 91 } // END OF WHILE 92 93 int max_flow = 0; 94 for (int i = 1; i <=n; i++) 95 { 96 for (int j = 1; j <=n; j++) 97 { 98 if (i == 1 && edges[i][j].f >0) 99 max_flow += edges[i][j].f;100 // if (edges[i][j].f > 0)101 // printf("%d-->%d: %d\n", i, j, edges[i][j].f);102 }103 }104 printf("%d\n", max_flow);105 }106 107 int main()108 {109 int u, v, c, f;110 while(scanf("%d%d",&m,&n)!=EOF)111 {112 for (int i = 0; i <= n; i++)113 for (int j = 0; j <= n; j++)114 // edges[i][j].c = edges[i][j].f = INF;115 edges[i][j].c=edges[i][j].f=0;116 for (int i = 0; i < m; i++)117 {118 //scanf("%d%d%d%d", &u, &v, &c, &f);119 scanf("%d%d%d",&u,&v,&c); // 这里是零流120 edges[u][v].c +=c; // 可能有重边121 // edges[u][v].f = f;122 }123 ford();124 }125 return 0;126 }

(2): dinic()

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 using namespace std;17 typedef long long LL;18 const int INF=0x5fffffff;19 const double EXP=1e-6;20 const int MS=1005;21 22 int edges[MS][MS];23 int level[MS];24 int que[MS],qs,qe;25 int n,m,ans;26 27 int BFS() // BFS求level28 {29 memset(level,0xff,sizeof(level));30 level[1]=0;31 qs=qe=0;32 que[qe++]=1;33 while(qs
                    
                     0)39 {40 level[v]=level[u]+1;41 que[qe++]=v;42 }43 }44 }45 if(level[n]>0) // 汇点在残留网络中，存在增广路46 return 1;47 else48 return 0;49 }50 51 int DFS(int u,int minv)52 {53 if(u==n)54 return minv;55 int t;56 for(int v=1;v<=n;v++)57 if(edges[u][v]>0&&level[v]==level[u]+1&&(t=DFS(v,min(minv,edges[u][v]))))58 {59 edges[u][v]-=t;60 edges[v][u]+=t;61 return t;62 }63 return 0;64 }65 66 int main()67 {68 int u,v,c;69 while(scanf("%d%d",&m,&n)!=EOF)70 {71 memset(edges,0,sizeof(edges));72 for(int i=1;i<=m;i++)73 {74 scanf("%d%d%d",&u,&v,&c);75 edges[u][v]+=c;76 }77 ans=0;78 int t;79 // DINIC()80 while(BFS()) //还存在增广路81 {82 while(t=DFS(1,INF)) //DFS找出残留网络中的所有增广路83 {84 ans+=t;85 }86 }87 printf("%d\n",ans);88 }89 return 0;90 }