http://acm.hdu.edu.cn/showproblem.php?pid=3549赤裸裸的網絡流水題，借此說一下網絡流算法。
算法描述如下：
1.利用殘留網絡尋找增廣路
2.將這一條增廣路在圖中去除，并修改殘留網絡
3.重復1、2步，直到找不到殘留網絡
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20
#define MAX 0xfffffff
int N, M;
int mp[LEN][LEN];
int sum;
int tc[LEN];
int tclen;
int gd[LEN];
int mf;
int hsap;
void traceBack()
{
int i, j;
int f, t;
for(i = 1; i < tclen; i++)
{
f = tc[i - 1];
t = tc[i];
mp[f][t] -= mf;
mp[t][f] += mf;
}
}
void DFS(int n)
{
int i, j;
for(i = 1; i <= N; i++)
{
if(gd[i] == 0 && mp[n][i] > 0)
{
if(i == N)
{
if(mp[n][i] < mf)
mf = mp[n][i];
tc[tclen++] = i;
gd[i] = 1;
traceBack();
sum += mf;
hsap = 1;
return;
}
else
{
if(mp[n][i] < mf)
mf = mp[n][i];
gd[i] = 1;
tc[tclen++] = i;
DFS(i);
tclen--;
}
}
}
}
int main()
{
int i, j;
int x, y, c;
int T;
int count = 0;
scanf("%d", &T);
while(T--)
{
memset(mp, 0, sizeof(mp));
scanf("%d%d", &N, &M);
for(i = 0; i < M; i++)
{
scanf("%d%d%d", &x, &y, &c);
mp[x][y] += c;
}
sum = 0;
while(1)
{
memset(gd, 0, sizeof(gd));
gd[1] = 1;
tc[0] = 1;
tclen = 1;
mf = MAX;
hsap = 0;
DFS(1);
if(hsap == 0)
break;
}
printf("Case %d: %d\n", ++count, sum);
}
//system("pause");
return 0;
}
請參閱：
http://www.shnenglu.com/hoolee/archive/2012/09/07/189860.html
posted on 2012-09-07 22:13
小鼠標 閱讀(326)
評論(0) 編輯 收藏 引用 所屬分類:
圖論