Posted on 2008-08-15 00:26
Hero 閱讀(125)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
/*
ID: wangzha4
LANG: C++
TASK: milk6
*/
/*
Test 1: TEST OK [0.000 secs, 2740 KB]
Test 2: TEST OK [0.000 secs, 2740 KB]
Test 3: TEST OK [0.011 secs, 2740 KB]
Test 4: TEST OK [0.000 secs, 2740 KB]
Test 5: TEST OK [0.000 secs, 2740 KB]
Test 6: TEST OK [0.000 secs, 2740 KB]
Test 7: TEST OK [0.000 secs, 2736 KB]
Test 8: TEST OK [0.011 secs, 2740 KB]
Test 9: TEST OK [0.000 secs, 2736 KB]
Test 10: TEST OK [0.000 secs, 2740 KB]
Test 11: TEST OK [0.000 secs, 2740 KB]
Test 12: TEST OK [0.000 secs, 2736 KB]
*/
//#define Ndebug
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define llong long long
const int size = 35 ;
int pren[size] ;//點的前驅(qū)
llong ncap[size] ;//每個點的最大流量(流出量)
int visit[size] ;//標(biāo)記該點是否被訪問過
llong flow[size][size] = {0} ;//邊流量
int data[1005][3] ;
int inn, inm ;
llong num_mincut ;//最小割邊的個數(shù)
llong val_mincut ;//最小割的值
llong fmin( llong a, llong b )
{
return a < b ? a : b ;
}
void input()
{
memset( flow, 0, sizeof(flow) ) ;
for( int i=1; i<=inm; i++ )
{
scanf( "%d %d %d", &data[i][0], &data[i][1], &data[i][2] ) ;
flow[data[i][0]][data[i][1]] += data[i][2] * 1001 + 1 ;
}
}
llong findway()
{//尋找增廣路徑，返回路徑容量(瓶頸容量)
memset( visit, 0, sizeof(visit) ) ;
memset( ncap, 0, sizeof (ncap) ) ;
llong maxncap = 0 ;//最大流量點的流量
int maxn = -1 ; //最大流量點的標(biāo)號
ncap[1] = 999999*99999 ;//初始化原點的流量為無窮大，保證從原點開始尋找
while( true )
{
maxncap = 0 ; maxn = -1 ;
for( int i=1; i<=inn; i++ )
{
if( !visit[i] && ncap[i]>maxncap )
{ maxncap = ncap[i] ; maxn = i ; }
}//找到擁有最大流量且沒有被訪問過的點
if( -1 == maxn ) return 0 ;//沒有找到增廣路徑
if( maxn == inn ) break ;//已經(jīng)找到新的增廣路徑
visit[maxn] = 1 ;//標(biāo)記這個點已經(jīng)被訪問過
for( int i=1; i<=inn; i++ )
{//對maxn的相鄰節(jié)點進(jìn)行權(quán)值更新操作
if( flow[maxn][i]>ncap[i] && maxncap>ncap[i] )
{//節(jié)點流量為邊流量和路徑流量的最小值
ncap[i] = fmin( flow[maxn][i], maxncap ) ;
pren[i] = maxn ;//該節(jié)點的前驅(qū)節(jié)點為maxn
}
}
}//while(true)
maxncap = ncap[inn] ;//路徑流量即為匯點的流量
for( int i=inn; i>1; i=pren[i] )
{
flow[pren[i]][i] -= maxncap ;//正向邊 - 路徑容量
flow[i][pren[i]] += maxncap ;//反向邊 + 路徑容量
}
return maxncap ;
}
void DFS_sn( int sn )
{
visit[sn] = 1 ;
for( int i=1; i<=inn; i++ )
{
if( !visit[i] && flow[sn][i]>0 ) DFS_sn( i ) ;
}
}
void process()
{
llong maxflow = 0 ; llong addflow ;
while( ( addflow = findway() ) != 0 )
{//當(dāng)路徑容量不為0
maxflow += addflow ;
}
val_mincut = maxflow/1001 ;
num_mincut = maxflow - (llong)(maxflow/1001)*1001 ;
printf( "%lld %lld\n", val_mincut, num_mincut ) ;
//find_mincut() ;
}
void output()
{
if( 1 == num_mincut )
{
for( int i=1; i<=inm; i++ )
{
if( val_mincut == data[i][2] )
{ printf( "%d\n", i ) ; return ; }
}
}
memset( visit, 0, sizeof(visit) ) ;
DFS_sn( 1 ) ;//
for( int i=1; i<=inm; i++ )
{
if( visit[data[i][0]] && !visit[data[i][1]] ) {
printf( "%d\n", i ) ;
}
}
}
int main()
{
#ifndef Ndebug
freopen( "milk6.in", "r", stdin ) ;
freopen( "milk6.out","w",stdout ) ;
#endif
#ifdef Ndebug
freopen( "in.txt", "r", stdin ) ;
freopen( "out.txt", "w", stdout ) ;
#endif
while( scanf( "%d %d", &inn, &inm ) != EOF )
{
input() ;
process() ;
output() ;
}//while
return 0 ;
}