2095: [Poi2010]Bridges
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 604 Solved: 218
[Submit][Status][Discuss]
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
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
Sample Output
HINT
注意：通过桥为欧拉回路
Source
Solution
最大风力最小，典型的二分，那么二分风力，作为最大风力即可
混合图欧拉回路，第一次见，大体上就是：
欧拉回路是图G中的一个回路，经过每条边有且仅一次，称该回路为欧拉回路。具有欧拉回路的图称为欧拉图，简称E图。
无向图中存在欧拉回路的条件：每个点的度数均为偶数。
有向图中存在欧拉回路的条件：每个点的入度 = 出度。
混合图就是一个含有有向边和无向边的图，混合图判欧拉回路时用的是最大流，原理及证明？我也不是很晓得...
下面是大体的模型：
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 2010
#define maxm 1000100
int n,m,minwind,maxwind,l,r,tot;
struct Bridgenode{int a,b,c,d;}bridge[maxn];
struct Edgenode{int to,next,cap;}edge[maxm];
int head[maxn],cnt=;
void add(int u,int v,int w)
{cnt++;edge[cnt].to=v;edge[cnt].cap=w;edge[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v,int w)
{add(u,v,w);add(v,u,);}
//
#define inf 0x7fffffff
int dis[maxn],cur[maxn],S,T,q[maxn<<],du[maxn];
bool bfs()
{
for (int i=S; i<=T; i++) dis[i]=-;
q[]=S; dis[S]=; int he=,ta=;
while (he<ta)
{
int now=q[he++];
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].cap && dis[edge[i].to]==-)
dis[edge[i].to]=dis[now]+,q[ta++]=edge[i].to;
}
return dis[T]!=-;
}
int dfs(int loc,int low)
{
if (loc==T) return low;
int w,used=;
for (int i=cur[loc]; i; i=edge[i].next)
if (edge[i].cap && dis[edge[i].to]==dis[loc]+)
{
w=dfs(edge[i].to,min(low-used,edge[i].cap));
edge[i].cap-=w; edge[i^].cap+=w;
used+=w; if (edge[i].cap) cur[loc]=i;
if (used==low) return low;
}
if (!used) dis[loc]=-;
return used;
}
int dinic()
{
int tmp=;
for (int i=; i<=n; i++) if (du[i]&) return -;
while (bfs())
{
for (int i=S; i<=T; i++) cur[i]=head[i];
tmp+=dfs(S,inf);
}
return tmp;
}
//
inline void make(int x)
{
S=,T=n+;
memset(head,,sizeof(head)); cnt=;
memset(du,,sizeof(du)); tot=;
for (int i=; i<=m; i++)
{
if(bridge[i].c<=x) du[bridge[i].a]--,du[bridge[i].b]++;
if(bridge[i].d<=x) insert(bridge[i].b,bridge[i].a,);
}
for (int i=; i<=n; i++)
if (du[i]>) tot+=du[i]/,insert(S,i,du[i]/);
else insert(i,T,-du[i]/);
}
int main()
{
n=read(),m=read(); minwind=inf; maxwind=-inf;
for (int a,b,c,d,i=; i<=m; i++)
{
a=read(),b=read(),c=read(),d=read();
if (c>d) swap(a,b),swap(c,d);
bridge[i].a=a,bridge[i].b=b,bridge[i].c=c,bridge[i].d=d;
minwind=min(c,minwind); maxwind=max(d,maxwind);
}
l=minwind; r=maxwind;
while (l<=r)
{
int mid=(l+r)>>;
make(mid);
int maxflow=dinic();
if (maxflow==tot) r=mid-;
else l=mid+;
}
if (l==maxwind+) {puts("NIE");return ;}
printf("%d\n",l);
return ;
}
好厉害的东西QAQ...以前只听说过，没见过QAQ...