bzoj 2095 [Poi2010]Bridges 判断欧拉维护，最大流+二分

[Poi2010]Bridges

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1448  Solved: 510
[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

Sample Output

4

HINT

注意：通过桥为欧拉回路

Source

 题解：二分风力值，然后最大流判断欧拉回路是否存在。

 

 #include<queue>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define inf 1000000000

 #define pa pair<int,int>

 #define ll long long

 #define mod 1000000007

 using namespace std;

 ll read()

 {

     ll x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int tot,n,m,cnt,T;

 int mx,mn=inf;

 int u[],v[],c[],d[],de[];

 int last[],q[],h[];

 struct edge{

     int to,next,v;

 }e[];

 void insert(int u,int v,int w)

 {

     e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

     e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=;

 }

 bool bfs()

 {

     int head=,tail=;

     for(int i=;i<=T;i++)h[i]=-;

     q[]=;h[]=;

     while(head!=tail)

     {

         int now=q[head];head++;

         for(int i=last[now];i;i=e[i].next)

             if(e[i].v&&h[e[i].to]==-)

             {

                 h[e[i].to]=h[now]+;

                 q[tail++]=e[i].to;

             }

     }

     return h[T]!=-;

 }

 int dfs(int x,int f)

 {

     if(x==T)return f;

     int w,used=;

     for(int i=last[x];i;i=e[i].next)

         if(h[e[i].to]==h[x]+)

         {

             w=dfs(e[i].to,min(e[i].v,f-used));

             e[i].v-=w,e[i^].v+=w;

             used+=w;if(used==f)return f;

         }

     if(!used)h[x]=-;

     return used;

 }

 void build(int mid)

 {

     memset(last,,sizeof(last));cnt=;

     memset(de,,sizeof(de));

     tot=;

     for(int i=;i<=m;i++)

     {

         if(c[i]<=mid)de[u[i]]--,de[v[i]]++;

         if(d[i]<=mid)insert(v[i],u[i],);

     }

     for(int i=;i<=n;i++)

         if(de[i]>)tot+=de[i]/,insert(,i,de[i]/);

         else insert(i,T,-de[i]/);

 }

 int dinic()

 {

     for(int i=;i<=n;i++)

         if(de[i]&)return -;

     int ans=;

     while(bfs())ans+=dfs(,inf);

     return ans;

 }

 int main()

 {

     n=read();m=read();T=n+;

     for(int i=;i<=m;i++)

     {

         u[i]=read(),v[i]=read(),c[i]=read(),d[i]=read();

         if(c[i]>d[i])swap(c[i],d[i]),swap(u[i],v[i]);

         mn=min(mn,c[i]);

         mx=max(mx,d[i]);

     }

     int l=mn,r=mx;

     while(l<=r)

     {

         int mid=(l+r)>>;

         build(mid);

         if(dinic()==tot) r=mid-;

         else l=mid+;

     }

     if(l==mx+)puts("NIE");

     else printf("%d\n",l);

 }