第一次寫(xiě)網(wǎng)絡(luò)最大流算法，居然做對(duì)了。
該算法要用到 Dijkstra 算法。
每次用Dijkstra算法求的一條可通過(guò)的路后，找出該路上面的最小的權(quán)值 MIN，然后將該路徑上的每條邊的權(quán)值 減去 MIN ，反方向的權(quán)值加 MIN （ 例如：e( v1, v2 ) 是路徑上面的一條邊，則Map[v1][v2] -= MIN, Map[v2][v1] += MIN ). 累計(jì)MIN， 其最后的值就是所要求的最大流。
當(dāng)最后 在圖中找不到連接 1, n 兩點(diǎn)的路徑時(shí)，算法完畢。
//2019083 whitesea 1273 Accepted 224K 15MS C++ 1880B 2007-03-22 14:56:03
// PKU 1273 網(wǎng)絡(luò)最大流
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
#include<stdio.h>
#include<string.h>
#define MAX 210
int Map[MAX][MAX];
int n, M, SUM, Path[MAX], distance[MAX], Min;
int IN(){
int i, x, y, d;
if( scanf( "%d %d", &M, &n ) == EOF )return 0; // M 是 邊的數(shù)目， n 是點(diǎn)的數(shù)目
memset( Map, 0, sizeof( Map ) );
for( i = 1; i <= M; i++ ){
scanf( "%d %d %d", &x, &y, &d ); // 點(diǎn)x 到點(diǎn)y流量為 d
Map[x][y] += d;
}
return 1;
}
void Dijkstra(){
int mindis, i, j, u, s[MAX];
for( i = 1; i <= n; i++ ){
distance[i] = Map[1][i];
s[i] = 0;
if( i != 1 && distance[i] > 0 )Path[i] = 1;
else Path[i] = -1;
}
s[1] = 1;
for( i = 2; i <= n; i++ ){
mindis = 0;
for( j = 1; j <= n; j++ ){
if( s[j] == 0 && distance[j] > mindis ){
u = j;
mindis = distance[j];
}
}
if( mindis == 0 )return;
s[u] = 1;
for( j = 1; j <= n; j++ ){
if( s[j] == 0 && Map[u][j] > 0 && distance[u] + Map[u][j] > distance[j] ){
distance[j] = distance[u] + Map[u][j];
Path[j] = u;
}
}
}
}
void Find(){
int s, t;
Min = 2000000000;
s = n;
t = Path[n];
while( t != -1 ){
if( Map[t][s] < Min )Min = Map[t][s];
s = t;
t = Path[t];
}
}
void Change(){
int s, t;
s = n;
t = Path[n];
while( t != -1 ){
Map[t][s] -= Min;
Map[s][t] += Min;
s = t;
t = Path[t];
}
}
void SOLVE(){
int i, j, k;
SUM = 0;
while( 1 ){
Dijkstra();
if( Path[n] == -1 )return;
Find();
SUM += Min;
Change();
}
}
void OUT(){
printf( "%d\n", SUM );
}
int main(){
while( IN() ){
SOLVE();
OUT();
}
return 0;
}