http://poj.org/problem?id=1273題意描述：給N個(gè)下水道和每條下水道的最大流量，M個(gè)節(jié)點(diǎn)，要求求出從節(jié)點(diǎn)1到節(jié)點(diǎn)M的最大流量。
最赤裸的網(wǎng)絡(luò)流，不斷找出增廣路增廣即可。找增廣路時(shí)，這里用的深度優(yōu)先搜索。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 210
#define MAX 1000000000
int mp[LEN][LEN];
int tc[LEN];//記錄dfs的路徑
int tclen;
int gd[LEN];//記錄某個(gè)節(jié)點(diǎn)是否訪問過(guò)
int endDFS;//記錄是否找到新的增廣路
int sum;//當(dāng)前流
int mf;//增廣路上最小的那條邊的大小
int N, M;
void traceBack()//找到增廣路后，用該函數(shù)修改mp[][]
{
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 m)
{
int i, j;
if(endDFS)
return;
for(i = 1; i <= M; i++)
{
if(gd[i] == 0 && mp[m][i] > 0)
{
if(i == M)
{
if(mp[m][i] < mf)
mf = mp[m][i];
tc[tclen++] = i;
gd[i] = 1;
endDFS = 1;
traceBack();
sum += mf;
return;
}
else
{
if(mp[m][i] < mf)
mf = mp[m][i];
tc[tclen++] = i;
gd[i] = 1;
DFS(i);
tclen--;
}
}
}
}
int main()
{
int i, j;
int s, e, c;
while(scanf("%d%d", &N, &M) != EOF)
{
memset(mp, 0, sizeof(mp));
for(i = 0; i < N; i++)//read data
{
scanf("%d%d%d", &s, &e, &c);
mp[s][e] += c;
}
sum = 0;//init sum
while(1)//find Augmenting Path
{
memset(gd, 0, sizeof(gd));
mf = MAX;
gd[1] = 1;
tc[0] = 1;
tclen = 1;
endDFS = 0;
DFS(1);
if(endDFS == 0)
break;
}
printf("%d\n", sum);
}
//system("pause");
return 0;
}
posted on 2012-09-07 21:29
小鼠標(biāo) 閱讀(305)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
圖論