测试数据 6 10 0 1 8 2 0 2 4 3 1 3 2 2 1 4 2 2 2 1 4 2 2 3 1 1 2 4 4 0 3 4 6 0 3 5 9 3 4 5 7 2
0->1:4 0->2:4 1->3:2 1->4:2 2->1:0 2->3:1 2->4:3 3->4:0 3->5:3 4->5:5 max_flow=8
代码
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; //标号法求矩阵网络最大流 const int maxn=100;//顶点数量 const int INF=0x3f3f3f3f; struct node { int c;//容量 int f;//流量 } map[maxn][maxn]; int flag[maxn];//未访问标记为-1，已访问未检查邻接顶点标记为0，已访问已检查邻接顶点标记为1 int prev[maxn];//i号顶点从prev[i]号顶点来 int alpha[maxn];//当star指向i,alpha[i]=min(alpha[star],map[star][i].c-map[star][i].f) //当i指向star，alpha[i]=min(alpha[star],map[i][star].f); int queue[maxn];//模拟队列 int N;//顶点 int M;//弧数 int q_star,q_end;//队列头尾指针 void ford() { while(1)//标号法可以在有限次标号调整后使求得最大流 { for(int i=0; i<N; i++) //初始化三个辅助数组 { flag[i]=-1; prev[i]=-1; alpha[i]=-1; } flag[0]=0;//源点标记为已访问未检查的点 prev[0]=0;//源点的上一个点还是源点 alpha[0]=INF;//源点可以无限流出 q_star=q_end=0; queue[q_end++]=0;//源点入队 while(q_star<q_end&&flag[N-1]==-1)//队列内有元素或者还没标记到汇点时进入循环接着标记 { int star=queue[q_star++];//去除队列元素 for(int i=0; i<N; i++) //检查star的邻接顶点，由于是有向图，所以需要检查正向邻接和反向邻接 { if(flag[i]==-1)//只检查尚未访问过的点，因为已访问未检查的点都在队列中 { //检查正向邻接，存在此弧且流量未满 if(map[star][i].c<INF&&map[star][i].f<map[star][i].c) { flag[i]=0;//标记为已访问未检查 prev[i]=star;//记录增广路径 alpha[i]=min(alpha[star],map[star][i].c-map[star][i].f);//可调整量 queue[q_end++]=i;//顶点i入队 } //检查反向邻接，存在弧且有流量 if(map[i][star].c<INF&&map[i][star].f>0) { flag[i]=0;//标记为已访问未检查 prev[i]=-star;//加个负号表示反向邻接 alpha[i]=min(alpha[star],map[i][star].f);//可调整量 queue[q_end++]=i;//入队 } } } flag[star]=1;//标记为已访问已检查 } if(flag[N-1]==-1||alpha[N-1]==0)//如果找不到去汇点的增广路径或者可调整量为0 break;//结束标号法 //下面这一步可能有问题 int alpha_num=alpha[N-1];//可调整量 int k1=N-1; int k2=abs(prev[k1]); while(1) { if(map[k2][k1].f<INF) map[k2][k1].f+=alpha_num; else map[k1][k2].f-=alpha_num; if(k2==0)//当调整到源点时跳出循环 break; k1=k2; k2=abs(prev[k2]);//不要忘了取绝对值 } } //下面输出各弧边最大流并累加 int max_flow=0;//累加各弧最大流 for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { if(i==0&&map[i][j].f<INF) max_flow+=map[i][j].f; if(map[i][j].f<INF) printf("%d->%d:%d\n",i,j,map[i][j].f); } } printf("max_flow=%d\n",max_flow); } int main() { scanf("%d%d",&N,&M); for(int i=0; i<N; i++) for(int j=0; j<N; j++) map[i][j].c=map[j][i].f=INF;//网络流都是有向图 int u,v,c,f; for(int i=0; i<M; i++) { scanf("%d%d%d%d",&u,&v,&c,&f); map[u][v].c=c; map[u][v].f=f; } ford(); return 0; }