Posted on 2008-08-01 14:35
Hero 閱讀(96)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
/*
ID: wangzha4
LANG: C++
TASK: ditch
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
double fmax( double a, double b )
{
if( a - b > 0 ) return a ;
else return b ;
}
double fmin( double a, double b )
{
if( a - b < 0 ) return a ;
else return b ;
}
int fmax( int a, int b )
{
if( a > b ) return a ;
else return b ;
}
int fmin( int a, int b )
{
if( a < b ) return a ;
else return b ;
}
int fpow( int a, int b )
{
int reval = 1 ;
for( int i=1; i<=b; i++ )
reval *= a ;
return reval ;
}
const int INF = 1000000 ;
const int size = 210 ;
int inn ;//邊的數量
int inm ;//點的數量
int pren[size] ;//點的前驅節點
int ncap[size] ;//每個點的最大流量(流出量)
int visit[size] ;//標記該點是否被訪問過
int flow[size][size] = {0} ;//邊的流量
int agument()
{//尋找增廣路徑,返回路徑容量(瓶頸容量)
memset( visit, 0, sizeof(visit) ) ;
memset( ncap, 0, sizeof( ncap ) ) ;
int maxncap = 0 ;//最大流量點的流量
int maxn = -1 ;//最大流量點的標號
ncap[1] = INF ;//初始化原點的流量為無窮大,保證從原點開始尋找
while( true ) {
maxncap = 0 ; maxn = -1 ;
for( int i=1; i<=inm; i++ ) {
if( !visit[i] && ncap[i] > maxncap ) {
maxncap = ncap[i] ; maxn = i ;
}
}//找到擁有最大流量且沒有被訪問過的點
if( -1 == maxn ) return 0 ;//沒有找到新的增廣路徑
if( maxn == inm ) break ;//已經找到一條新的增廣路徑
visit[maxn] = 1 ;//標記這個點已經被訪問過
for( int i=1; i<=inm; i++ ) {//對maxn的相鄰節點進行更新操作
if( flow[maxn][i]>ncap[i] && maxncap>ncap[i] ) {
//節點的流量為邊流量和路徑流量的最小值
ncap[i] = fmin( flow[maxn][i], maxncap ) ;
pren[i] = maxn ;//節點i的前驅節點為maxn
}
}
}//while( true )
maxncap = ncap[inm] ;//路徑容量即為匯點的流量
for( int i=inm; i>1; i=pren[i] ) {
int curnode = pren[i] ;//i的前驅節點
flow[curnode][i] -= maxncap ;//正向邊+路徑容量
flow[i][curnode] += maxncap ;//反向邊-路徑容量
}
return maxncap ;//返回路徑容量
}
int main()
{
freopen( "ditch.in", "r", stdin ) ;
freopen( "ditch.out","w",stdout ) ;
memset( flow, 0, sizeof(flow) ) ;
scanf( "%d %d",&inn, &inm ) ;
int sn, en, f ;
for( int i=1; i<=inn; i++ ) {
scanf( "%d %d %d", &sn, &en, &f ) ;
flow[sn][en] += f ;
}//data input
int maxflow = 0 ; int addflow ;
while( ( addflow = agument() ) ) {//當路徑容量不為0
maxflow += addflow ;
}
printf( "%d\n",maxflow ) ;
return 0 ;
}