Posted on 2008-08-15 00:26
Hero 阅读(106)
评论(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] ;//点的前驱
llong ncap[size] ;//每个点的最大流量(流出量)
int visit[size] ;//标记该点是否被访问过
llong flow[size][size] = {0} ;//边流量
int data[1005][3] ;
int inn, inm ;
llong num_mincut ;//最小割边的个数
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 ; //最大流量点的标号
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 ;//已经找到新的增广路径
visit[maxn] = 1 ;//标记这个点已经被访问过
for( int i=1; i<=inn; i++ )
{//对maxn的相邻节点进行权值更新操作
if( flow[maxn][i]>ncap[i] && maxncap>ncap[i] )
{//节点流量为边流量和路径流量的最小值
ncap[i] = fmin( flow[maxn][i], maxncap ) ;
pren[i] = maxn ;//该节点的前驱节点为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 )
{//当路径容量不为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 ;
}