A new Graph Game

A new Graph Game

點擊打開鏈接

題意：給你一張N個節點的無向圖，然後給出M條邊，給出第 I 條邊到第J條邊的距離。然後問你是否存在子環，如果存在，則輸出最成環的最短距離和

解析：構圖：選定源點及匯點，然後將源點至個點流量置為1，花費置為0.然後使用最小費用流，當返回值流量和，即flow < n 時，則輸出NO，因為所有邊成環最少邊數為N。

其余和tour一樣求法，處理一下某兩點距離為最短距離即可。

#include
#include
#include
#include

using namespace std;

const int maxn = 10000;
const int maxm = 100000;
const int INF = 0xfffffff;

struct Edge{
	int to, next, cap, flow, cost;
}edge[ maxm ];

int head[ maxn ], tol;
int pre[ maxn ], dis[ maxn ];
bool vis[ maxn ];

int N;

void init( int n ){
	N = n;
	tol = 0;
	memset( head, -1, sizeof( head ) );
}

void addedge( int u, int v, int cap, int cost ){
	edge[ tol ].to = v;
	edge[ tol ].cap = cap;
	edge[ tol ].cost = cost;
	edge[ tol ].flow = 0;
	edge[ tol ].next = head[ u ];
	head[ u ] = tol++;
	edge[ tol ].to = u;
	edge[ tol ].cap = 0;
	edge[ tol ].cost = -cost;
	edge[ tol ].flow = 0;
	edge[ tol ].next = head[ v ];
	head[ v ] = tol++;
}

bool spfa( int s, int t ){
	queue< int > q;
	for( int i = 0; i < N; ++i ){
		dis[ i ] = INF;
		vis[ i ] = false;
		pre[ i ] = -1;
	}
	dis[ s ] = 0;
	vis[ s ] = true;
	q.push( s );
	while( !q.empty( ) ){
		int u = q.front();
		q.pop();
		vis[ u ] = false;
		for( int i = head[ u ]; i != - 1; i = edge[ i ].next ){
			int v = edge[ i ].to;
			if( edge[ i ].cap > edge[ i ].flow && dis[ v ] > dis[ u ] + edge[ i ].cost ){
				dis[ v ] = dis[ u ] + edge[ i ].cost;
				pre[ v ] = i;
				if( !vis[ v ] ){
					vis[ v ] = true;
					q.push( v );
				}
			}
		}
	}
	if( pre[ t ] == -1 ) 
		return false;
	else
		return true;
}

struct node{
	int f, c;
};

//node a;
node minCostMaxflow( int s, int t, int &cost ){
	int flow = 0;
	cost = 0;
	while( spfa( s, t ) ){
		int Min = INF;
		for( int i = pre[ t ]; i != - 1; i = pre[ edge[ i ^ 1 ].to ] ){
			if( Min > edge[ i ].cap - edge[ i ].flow )
				Min = edge[ i ].cap - edge[ i ].flow;
		}
		for( int i = pre[ t ]; i  != -1; i = pre[ edge[ i ^ 1 ].to ] ){
			edge[ i ].flow += Min;
			edge[ i ^ 1 ].flow -= Min;
			cost += edge[ i ].cost * Min;
		}
		flow += Min;
	}
	node ans;
	ans.f = flow;
	ans.c = cost;
	return ans;
}

#define INF 0xfffffff
int mapp[ maxn ][ maxn ];

int main(){
	int Case;
	int n, m;
	scanf( "%d", &Case );
	for( int k = 1; k <= Case; ++k ){
		scanf( "%d%d", &n, &m );
		for( int i = 0; i <= n; ++i ){
			for( int j = 0; j <= n; ++j ){
				mapp[ i ][ j ] = INF;
			}
		}
		int start = 0, end = 2 * n + 1, N = 2 * n + 2;
		init( N );
		int x, y, value;
		for( int i = 1; i <= n; ++i ){
			addedge( 0, i, 1, 0 );
			addedge( n + i, end, 1, 0 );
		}
		int Max = 0;
		for( int i = 0; i < m; ++i ){
			scanf( "%d%d%d", &x, &y, &value );
			int temp = max( x, y );
			if( Max < temp ){
				Max = temp;
			}
			if( mapp[ x ][ y ] > value ){
				mapp[ x ][ y ] = mapp[ y ][ x ] = value;
			}
		}
		
		for( int i = 1; i <= n ; ++i ){
			for( int j = 1; j <= n; ++j ){
				if( mapp[ i ][ j ] != INF ){
					addedge( i, n + j, 1, mapp[ i ][ j ] );
				}
			}
		}
		int cost;
		node ans = minCostMaxflow( start, end, cost );
		printf( "Case %d: ", k );
		if( ans.f >= n ){	
			printf( "%d\n", ans.c );
		}
		else{
			puts( "NO" );
		}
	} 
	return 0;
}