[POJ] 2391 Ombrophobic Bovines

題目網址: http://poj.org/problem?id=2391

題意: 農場有F個區塊，每個區塊會有A隻牛B個避雨棚，且有P條無向的路連接某兩個區塊且給定此路徑所需時間，問所有的牛都能避雨最快所需時間，或無法全部避雨。



解法: 可以當成給定時間，確定此時間內是否可行，若行，則代表大於此時間的都行，所以答案有單調性值，可以使用二分查找來找答案，可以先使用Floyd找出所有任兩點間最短路徑，用二分查找最長路徑與0間最小符合最大流等於牛總數，建圖方式從S到每個區塊i增加一條有向邊容量為此區塊的牛數量，再建立每個區塊i至區塊i'一條有向邊容量為無窮大，最後再增加區塊i至區塊j'一條容量為無窮的有向邊，若區塊i至區塊j的最短路徑小於當前查找的時間。

TAG: Floyd Warshall, Binary Search, Flow Network, MaxFlow, Dinic

注意:

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	#define N 420
	#define M N*N*3
	#define INF 1e7
	#define LLINF (1LL<<50)
	#define clr(x,v) memset( x, v, sizeof(x) )
	typedef long long LL;
	struct Edge {
	int u, v;
	int c;
	int next;
	Edge( int _u = 0, int _v = 0, int _c = 0, int _next = 0 ):
	u(_u), v(_v), c(_c), next(_next) {}
	};
	int f, p;
	LL d[N][N];
	int s, t;
	int ttl;
	int eCnt;
	int eHead[N];
	Edge edge[M];
	int cows[N];
	int shelter[N];
	void addEdge( int u, int v, int c )
	{
	edge[eCnt] = Edge( u, v, c, eHead[u] );
	eHead[u] = eCnt++;
	edge[eCnt] = Edge( v, u, 0, eHead[v] );
	eHead[v] = eCnt++;
	}
	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 ) {
	clr( dep, -1 );
	dep[s] = 0; que[0] = s;
	for( hd=tl=0; hd <= tl && dep[t] == -1; ++hd ) {
	for( now = que[hd], ne = eHead[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, eHead, 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;
	}
	void init( void )
	{
	static int i, j, k, u, v;
	static LL val;
	ttl = 0;
	for( i = 1; i <= f; ++i ) {
	scanf( "%d%d", &cows[i], &shelter[i] );
	ttl += cows[i];
	}
	for( i = 1; i <= f; ++i ) for( j = 1; j <= f; ++j ) {
	if( i == j ) d[i][j] = 0LL;
	else d[i][j] = LLINF;
	}
	for( i = 1; i <= p; ++i ) {
	scanf( "%d%d%lld", &u, &v, &val );
	d[u][v] = d[v][u] = min( val, d[u][v] );
	}
	s = 0; t = 2*f+1;
	for( k = 1; k <= f; ++k ) for( i = 1; i <= f; ++i ) for( j = 1; j <= f; ++j )
	if( d[i][j] > d[i][k]+d[k][j] ) d[i][j] = d[i][k]+d[k][j];
	}
	void solve( void )
	{
	static int i, j, flow;
	static LL l, r, mid, ans;
	l = r = 0LL;
	for( i = 1; i <= f; ++i ) for( j = 1; j <= f; ++j ) if( d[i][j] != LLINF ) r = max( r, d[i][j] );
	ans = -1LL;
	while( l <= r ) {
	mid = (l+r)>>1;
	clr( eHead, -1 );
	eCnt = 0;
	for( i = 1; i <= f; ++i ) {
	addEdge( s, i, cows[i] );
	addEdge( i, i+f, INF );
	addEdge( i+f, t, shelter[i] );
	for( j = 1; j <= f; ++j ) if( d[i][j] <= mid && i != j ) addEdge( i, j+f, INF );
	}
	flow = dinic();
	if( flow == ttl ) { ans = mid; r = mid-1; }
	else l = mid+1;
	}
	printf( "%lld\n", ans );
	}
	int main( void )
	{
	int i;
	while( scanf( "%d%d", &f, &p ) == 2 ) {
	init();
	solve();
	}
	return 0;
	}

view raw Ombrophobic Bovines.cpp hosted with ❤ by GitHub