1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6 #include <string>  7 #include <map>  8 #include <stack>  9 #include <vector> 10 #include <set> 11 #include <queue> 12 #pragma comment (linker,"/STACK:102400000,102400000") 13 #define maxn 1005 14 #define MAXN 1000 15 #define mod 1000000009 16 #define INF 0x3f3f3f3f 17 #define pi acos(-1.0) 18 #define eps 1e-6 19 typedef long long ll; 20 using namespace std; 21  22 struct ArcType//弧结构 23 { 24     int c,f;//容量，流量 25 }; 26  27 ArcType Edge[MAXN][MAXN];//邻接矩阵（每个元素为ArcType类型） 28 int n,m;  //顶点的个数和弧数 29 int flag[MAXN];  //顶点状态：-1——未标号，0——已标号未检查，1——已标号已检查 30 int prev[MAXN];  //标号的第一个分量：指明标号是从哪里得到的，以便找到可改尽量 31 int alpha[MAXN];  //标号的第二个分量：可改进量 32 int que[MAXN];  //队列 33 int v;  //从队列中取出来的队列头元素 34 int qs,qe; //队列头位置，队列尾位置 35 int i,j;  //循环变量 36  37 void ford() 38 { 39     while (1)  //标号直到不存在可改进路 40     { 41         //标号前对顶点状态数组初始化为-1 42         memset(flag,-1,sizeof(flag)); 43         memset(prev,-1,sizeof(prev)); 44         memset(alpha,-1,sizeof(alpha)); 45         flag[0]=0;  prev[0]=0;  alpha[0]=INF;  //源点为已标号未检查点 46         qs=qe=0; 47         que[qe]=0;//源点入队 48         qe++;  //qs<qe表示队列非空，flag[n-1]==-1表示汇点未标号 49         while (qs<qe&&flag[n-1]==-1) 50         { 51             v=que[qs];  qs++;  //取出队列头顶点 52             for (i=0;i<n;i++)  //检查顶点v的正向和反向“邻接”顶点 53             { 54                 if (flag[i]==-1) 55                 { 56                     //“正向”且未“满” 57                     if (Edge[v][i].c<INF&&Edge[v][i].f<Edge[v][i].c) 58                     { 59                         flag[i]=0;prev[i]=v;  //给顶点i标号（已标号未检查） 60                         alpha[i]=min(alpha[v],Edge[v][i].c-Edge[v][i].f); 61                         que[qe]=i;  //顶点i入队 62                         qe++; 63                     } 64                     //"反向"且有流量 65                     else if (Edge[i][v].c<INF&&Edge[i][v].f>0) 66                     { 67                         flag[i]=0; prev[i]=-v;  //给顶点i标号（已标号未检查） 68                         alpha[i]=min(alpha[v],Edge[i][v].f); 69                         que[qe]=i;  //顶点i入队 70                         qe++; 71                     } 72                 } 73             } 74             flag[v]=1; 75         }  //end of while (qs<qe&&flag[n-1]==-1) 76         //当汇点没有获得标号，或者汇点的调整量为零，应该退出while循环 77         if (flag[n-1]==-1||alpha[n-1]==0) 78             break; 79         //当汇点有标号时应该进行调整 80         int k1=n-1,k2=abs(prev[k1]); 81         int a=alpha[n-1];//可改进量 82         while (1) 83         { 84             if (Edge[k2][k1].f<INF) 85                 Edge[k2][k1].f=Edge[k2][k1].f+a; 86             else 87                 Edge[k1][k2].f=Edge[k1][k2].f-a; 88             if (k2==0)   //调整一直到源点0 89                 break; 90             k1=k2; 91             k2=abs(prev[k2]); 92         } 93     } 94     //输出各条弧及其流量，以及求得的最大流量 95     int maxFlow=0; 96     for (i=0;i<n;i++) 97     { 98         for (j=0;j<n;j++) 99         {100             if (i==0&&Edge[i][j].f<INF)  //求源点流出量，即最大流101                 maxFlow+=Edge[i][j].f;102             if (Edge[i][j].f<INF)103                 printf("%d->%d:%d\n",i,j,Edge[i][j].f);104         }105     }106     printf("maxFlow:%d\n",maxFlow);107 }108 109 int main()110 {111     int u,v,c,f;  //弧的起点，终点，容量，流量112     while (scanf("%d%d",&n,&m)!=EOF)  //读入顶点个数n和弧数m113     {114         for (i=0;i<n;i++)115             for (j=0;j<n;j++)116                 Edge[i][j].c=Edge[i][j].f=INF;117         for (i=0;i<m;i++)118         {119             scanf("%d%d%d%d",&u,&v,&c,&f);120             Edge[u][v].c=c;121             Edge[u][v].f=f;122         }123         ford();124     }125     return 0;126 }127 /*128 6 10129 0 1 8 2130 0 2 4 3131 1 3 2 2132 1 4 2 2133 2 1 4 2134 2 3 1 1135 2 4 4 0136 3 4 6 0137 3 5 9 3138 4 5 7 2139 */