bzoj2095 [Poi2010]Bridges_综合

bzoj [Poi2010]Bridges

Description
YYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。

Input
输入：第一行为两个用空格隔开的整数n（2<=n<=1000），m(1<=m<=2000)，接下来读入m行由空格隔开的4个整数a，b（1<=a,b<=n,a<>b），c，d(1<=c,d<=1000)，表示第i+1行第i座桥连接小岛a和b，从a到b承受的风力为c，从b到a承受的风力为d。

Output
输出：如果无法完成减肥计划，则输出NIE，否则第一行输出承受风力的最大值（要使它最小)

Sample Input
4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4

Sample Output
4

HINT
注意：通过桥为欧拉回路

题目要求最大承受风力的最小值，那很明显是二分答案啦

那么二分答案后这个图就会变成一个混合图（也就是既有单向边也有双向边的）.. 然后只需要判断这个混合图是否为欧拉回路即可

关于欧拉回路的百度百科：http://baike.baidu.com/view/566040.htm

混合图存在欧拉回路条件
要判断一个混合图 $G（V,E）$ （既有有向边又有无向边）是欧拉图，方法如下：
假设有一张图有向图 $G'$ ，在不论方向的情况下它与 $G$ 同构。并且 $G'$ 包含了 $G$ 的所有有向边。那么如果存在一个图 $G'$ 使得 $G'$ 存在欧拉回路，那么 $G$ 就存在欧拉回路。
其思路就将混合图转换成有向图判断。实现的时候，我们使用网络流的模型。现任意构造一个 $G'$ 。用 $I_i$ 表示第 $i$ 个点的入度， $O_i$ 表示第 $i$ 个点的出度。如果存在一个点 $k$ ， $|O_k-I_k|mod\ 2=1$ ，那么G不存在欧拉回路。接下来则对于所有 $I_i>O_i$ 的点从源点连到i一条容量为 $(I_i-O_i)/2$ 的边，对于所有 $I_i<O_i$ 的点从 $i$ 连到汇点一条容量为 $(O_i-I_i)/2$ 的边。如果对于节点 $U$ 和 $V$ ，无向边 $（U，V）∈E$ ，那么 $U$ 和 $V$ 之间互相建立容量为无限大的边。如果此网络的最大流等于 $\sum|Ii-Oi|/2$ ，那么就存在欧拉回路。

那么就这样就行了..

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int Maxn = 1100;
const int Maxm = 2100;
struct node {int x, y, next, c, opp;
}a[Maxm*10]; int first[Maxn], len;
int _max ( int x, int y ){ return x > y ? x : y; }
int _min ( int x, int y ){ return x < y ? x : y; }
void ins ( int x, int y, int c ){len ++; int k1 = len;a[len].x = x; a[len].y = y; a[len].c = c;a[len].next = first[x]; first[x] = len;len ++; int k2 = len;a[len].x = y; a[len].y = x; a[len].c = 0;a[len].next = first[y]; first[y] = len;a[k1].opp = k2;a[k2].opp = k1;
}
int n, m;
struct lnode {int x, y, c, d;
}list[Maxm];
int st, ed, h[Maxn];
int de[Maxn];
bool bfs (){queue <int> q;memset ( h, -1, sizeof (h) );q.push (st); h[st] = 0;while ( !q.empty () ){int x = q.front (); q.pop ();for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( h[y] == -1 && a[k].c > 0 ){h[y] = h[x]+1;q.push (y);}}}return h[ed] > 0;
}
int dfs ( int x, int flow ){if ( x == ed ) return flow;int delta = 0;for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( h[y] == h[x]+1 && a[k].c > 0 && flow-delta > 0 ){int minf = dfs ( y, _min ( a[k].c, flow-delta ) );delta += minf;a[k].c -= minf;a[a[k].opp].c += minf;}}if ( delta == 0 ) h[x] = -1;return delta;
}
int main (){int i, j, k;scanf ( "%d%d", &n, &m );int l, r, mid, ret;l = 9999; r = 0;memset ( de, 0, sizeof (de) );for ( i = 1; i <= m; i ++ ){scanf ( "%d%d%d%d", &list[i].x, &list[i].y, &list[i].c, &list[i].d );if ( list[i].c > list[i].d ){ swap ( list[i].x, list[i].y ); swap ( list[i].c, list[i].d ); }l = _min ( l, list[i].c ); r = _max ( r, list[i].d );de[list[i].x] ++; de[list[i].y] ++;}bool bk = false;for ( i = 1; i <= n; i ++ ){if ( de[i] % 2 == 1 ){ bk = true; break; }}if ( bk == true ){ printf ( "NIE\n" ); return 0; }ret = -1;while ( l <= r ){mid = ( l + r ) >> 1;len = 0; memset ( first, 0, sizeof (first) );st = 0; ed = n+1;memset ( de, 0, sizeof (de) );for ( i = 1; i <= m; i ++ ){if ( mid >= list[i].c ){de[list[i].x] --;de[list[i].y] ++;}if ( mid >= list[i].d ){ins ( list[i].y, list[i].x, 1 );}}int sum = 0;bk = false;for ( i = 1; i <= n; i ++ ){if ( de[i] & 1 ){ bk = true; break; }if ( de[i] > 0 ){ ins ( st, i, de[i]/2 ); sum += de[i]/2; }else ins ( i, ed, -de[i]/2 );}int ans = 0, delta;while ( bfs () ){while ( delta = dfs ( st, 0x7fffffff ) ) ans += delta;}if ( ans == sum && bk == false ){ ret = mid; r = mid-1; }else l = mid+1;}if ( ret == -1 ) printf ( "NIE\n" );else printf ( "%d\n", ret ); return 0;
}