2095: [Poi2010]Bridges
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 1187 Solved: 408
[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
4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
![[BZOJ2095][Poi2010]Bridges 二分+网络流-LMLPHP]( "[BZOJ2095][Poi2010]Bridges 二分+网络流-LMLPHP")
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
Sample Output
4
HINT
注意：通过桥为欧拉回路
首先我们二分答案，之后我们用可行边建图，发现是混合图的欧拉回路问题，用网络流解决。
对于无向边，我们给它随意定向，之后看每个点的入度出度之差的绝对值tmp是否为2的倍数。
对于入度大于出度的点，我们从这个点向汇点连一条容量为tmp/2的边。
对于入度小于出度的点，我们从源点向这个点连一条容量为tmp/2的边。
对于每一条无向边，我们沿定的向连一条容量为1的边。
查询是否满流。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int head[],cnt;
struct data {
int to,next,w;
}e[];
void add(int u,int v,int c){e[cnt].to=v;e[cnt].next=head[u];e[cnt].w=c;head[u]=cnt++;}
struct data1 {
int a,b,c,d;
}t[];
int ru[],cu[];
int q[];
bool vis[];
int dis[];
bool bfs() {
memset(dis,-,sizeof(dis));
int h=,t=;
q[h]=;
vis[]=;
dis[]=;
while(h!=t) {
int now=q[h];h++;vis[now]=;if(h==) h=;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(e[i].w>&&dis[to]<) {
dis[to]=dis[now]+;
if(!vis[to]){
vis[to]=;
q[t++]=to;if(t==)t=;
}
}
}
}
return dis[n+]!=-;
}
int dfs(int now,int a) {
if(now==n+||a==) return a;
int flow=,f;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(dis[to]==dis[now]+&&e[i].w>) {
f=dfs(to,min(a,e[i].w));
e[i].w-=f;
e[i^].w+=f;
flow+=f;
a-=f;
if(a==) break;
}
}
if(!flow) dis[now]=-;
return flow;
}
bool check(int mid) {
cnt=;
memset(head,-,sizeof(head));
memset(ru,,sizeof(ru));
memset(cu,,sizeof(cu));
for(int i=;i<=m;i++) {
if(t[i].c<=mid) {
if(t[i].d<=mid) {
add(t[i].a,t[i].b,);
add(t[i].b,t[i].a,);
cu[t[i].a]++;ru[t[i].b]++;
}
else {cu[t[i].a]++;ru[t[i].b]++;}
}
else if(t[i].d<=mid) {ru[t[i].a]++;cu[t[i].b]++;}
else return ;
}
int sum=;
for(int i=;i<=n;i++) {
if(abs(ru[i]-cu[i])&) return ;
int tmp=abs(ru[i]-cu[i]);
if(ru[i]<cu[i]) {add(,i,tmp/);add(i,,);}
else if(ru[i]>cu[i]) {sum+=tmp/;add(i,n+,tmp/);add(n+,i,);}
}
int ans=;
while(bfs()){ans+=dfs(,);}
return ans==sum;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++) {
scanf("%d%d%d%d",&t[i].a,&t[i].b,&t[i].c,&t[i].d);
}
int l=,r=;
while(l<=r) {
int mid=(l+r)>>;
if(check(mid)) r=mid-;
else l=mid+;
}
if(r==) printf("NIE");
else printf("%d",r+);
}