Bridges

题目描述

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

输入

输入:第一行为两个用空格隔开的整数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。

输出

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

样例输入

4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4

样例输出

4

提示

Bridges-LMLPHP

solution

题目不怎么严谨。。。

反正求一条欧拉回路,要求最大边权最小。

欧拉回路

无向图:所有点度数均为偶数且图联通。 

有向图:所有点入度等于出度且图联通。

因为答案有单调性首先二分出mid,把大于mid的边拎出来。

这是一张混合图,我们给无向边先随便定一个向。

统计点的入度和出度,如果abs(in-out)&1  那么一定不合法。

因为翻转一条无向边会带来+-2的收益。

我们想怎么去维护欧拉回路。

若in[i]>out[i],则lj(S,i,(in[i]-out[i])/2)

否则lj(i,T,(out[i]-in[i])/2)。

判断最大流是否等于所有(in-out)/2(in>out)即可。

反向边流量我赋值成t3。。真是傻

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 1005
#define inf 1e9
using namespace std;
int n,m,l,r,Max,tot,S,T,head[maxn];
int in[maxn],out[maxn],d[maxn],flag[maxn],cur[maxn];
queue<int>q;
struct node{
int a,b,c,d;
}s[2002];
struct no{
int v,nex,cap;
}e[200005];
void lj(int t1,int t2,int t3){
e[++tot].v=t2,e[tot].cap=t3;e[tot].nex=head[t1];head[t1]=tot;
e[++tot].v=t1,e[tot].cap=0;e[tot].nex=head[t2];head[t2]=tot;
}
bool BFS(){ for(int i=1;i<=T;i++)d[i]=inf;
d[S]=0;q.push(S);
while(!q.empty()){
int x=q.front();q.pop();
cur[x]=head[x];
for(int i=head[x];i;i=e[i].nex){
if(d[e[i].v]>d[x]+1&&e[i].cap>0){
d[e[i].v]=d[x]+1;
if(!flag[e[i].v]){
flag[e[i].v]=1;q.push(e[i].v);
}
}
}
flag[x]=0;
}
return d[T]!=inf;
}
int lian(int k,int a){
if(k==T||!a)return a;
int f,flow=0;
for(int &i=cur[k];i;i=e[i].nex){
if(d[e[i].v]==d[k]+1&&(f=lian(e[i].v,min(e[i].cap,a)))>0){
e[i].cap-=f;e[i^1].cap+=f;
a-=f;flow+=f;
if(!a)break;
}
}
return flow;
} bool pd(int mid)
{
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(head,0,sizeof(head));
tot=1;
for(int i=1;i<=m;++i)
{
if(s[i].c<=mid&&s[i].d<=mid){in[s[i].a]++,out[s[i].b]++,lj(s[i].a,s[i].b,1);continue;}
if(s[i].c<=mid)out[s[i].a]++,in[s[i].b]++;
else if(s[i].d<=mid)out[s[i].b]++,in[s[i].a]++;
else return false;
}
S=0;T=n+1;int sum=0,ans=0;
for(int i=1;i<=n;++i)
{
if((in[i]-out[i])%2)return false;
if(in[i]>out[i])lj(S,i,(in[i]-out[i])/2),sum+=(in[i]-out[i])/2;
else lj(i,T,(out[i]-in[i])/2);
}
while(BFS())ans+=lian(S,1e9);
return ans==sum;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&s[i].a,&s[i].b,&s[i].c,&s[i].d);
}
l=0,r=1005;
while(l<r){
int mid=(l+r)/2;
if(pd(mid))r=mid;
else l=mid+1;
}
if(r==1005)puts("NIE");
else cout<<r<<endl;
return 0;
}

假设定向(u,v)

那么就在网络流的图中连(v,u,1)

有流表示反向

05-28 22:43