[ZOJ] 2760 How Many Shortest Path

題目網址: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1760

題意: 給定一個帶權有向圖，且指定起點、終點，問從起點至終點最多能有幾條不重疊的最短路徑。



解法: 先用floyd warshall算出任兩點間的最短路徑，接著判斷原圖中的每條邊(a,b)是否滿足"(s,a)的最短距離+(a,b)的權重+(b,t)的最短距離==(s,t)的最短距離"，若滿足則代表此邊是最短路徑的邊，將此邊加入新的網路圖中且容量為一，最後只需要在新建的網路圖中找出最大流即可。

TAG: Flow Network, Floyd Warshall, MaxFlow, Ford-Fulkerson

注意: 測資輸入的 adjacency matrix 中，對自己走到自己竟然會包含非0的值，所以必須給定edge[i][j] = 0, i == j。

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	using namespace std;
	#define N 500
	#define INF 1e7
	struct Edge {
	int u, v;
	int c;
	int next;
	Edge( int _u = -1, int _v = -1, int _c = 0, int _next = -1 ):
	u(_u), v(_v), c(_c), next(_next) {}
	};
	int n;
	int e[N][N], d[N][N];
	Edge edge[N*N];
	int head[N];
	int eCnt;
	int s, t;
	void floydWarshall( void )
	{
	static int i, j, k;
	for( k = 0; k < n; ++k ) for( i = 0; i < n; ++i ) for( j = 0; j < n; ++j )
	d[i][j] = min( d[i][j], d[i][k]+d[k][j] );
	}
	void init( void )
	{
	static int i, j;
	for( i = 0; i < n; ++i ) for( j = 0; j < n; ++j ) {
	scanf( "%d", &e[i][j] );
	if( e[i][j] < 0 ) e[i][j] = INF;
	if( i == j ) e[i][j] = 0;
	}
	memcpy( d, e, sizeof(d) );
	scanf( "%d%d", &s, &t );
	memset( head, -1, sizeof(head) );
	}
	int dinic( void )
	{
	static int i, now, hd, tl, top, flow, nxt, ne, minf;
	static int cur[N], dep[N], que[N];
	flow = 0;
	while( 1 ) {
	memset( dep, -1, sizeof(dep) );
	dep[s] = 0; que[0] = s;
	for( hd=tl=0; hd <= tl && dep[t] == -1; ++hd ) {
	for( now = que[hd], ne = head[now]; ne != -1; ne = edge[ne].next ) {
	if( !edge[ne].c || dep[nxt=edge[ne].v] != -1 ) continue;
	dep[nxt] = dep[now]+1;
	que[++tl] = nxt;
	if( nxt == t ) break;
	}
	}
	if( dep[t] == -1 ) break;
	memcpy( cur, head, sizeof(cur) );
	now = s; top = 0;
	while( 1 ) {
	if( now == t ) {
	for( minf=INF, i=1; i <= top; ++i ) if( minf > edge[que[i]].c )
	minf = edge[que[tl=i]].c;
	for( i = 1; i <= top; ++i ) {
	edge[que[i]].c -= minf;
	edge[que[i]^1].c += minf;
	}
	now = edge[que[(top=tl)--]].u;
	flow += minf;
	}
	for( ne=cur[now]; ne != -1; ne=cur[now]=edge[ne].next )
	if( edge[ne].c && dep[now]+1 == dep[edge[ne].v] ) break;
	if( cur[now] != -1 ) {
	que[++top] = cur[now];
	now = edge[cur[now]].v;
	} else {
	if( !top ) break;
	dep[now] = -1;
	now = edge[que[top--]].u;
	}
	}
	}
	return flow;
	}
	int solve( void )
	{
	static int i, j;
	floydWarshall();
	eCnt = 0;
	for( i = 0; i < n; ++i ) {
	if( d[s][i] == INF ) continue;
	for( j = 0; j < n; ++j ) {
	if( i == j || e[i][j] == INF || d[j][t] == INF ) continue;
	if( d[s][i]+e[i][j]+d[j][t] == d[s][t] ) {
	edge[eCnt] = Edge( i, j, 1, head[i] );
	head[i] = eCnt++;
	edge[eCnt] = Edge( j, i, 0, head[j] );
	head[j] = eCnt++;
	}
	}
	}
	return dinic();
	}
	int main( void )
	{
	int i, j;
	while( scanf( "%d", &n ) == 1 ) {
	init();
	if( s == t ) puts("inf");
	else printf( "%d\n", solve() );
	}
	return 0;
	}

view raw How Many Shortest Path.cpp hosted with ❤ by GitHub