算法复习——欧拉回路混合图（bzoj2095二分+网络流）

题目：

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

HINT

注意：通过桥为欧拉回路

题解：

在二分答案后的图一定是个无向边+单向边的混合图，混合图的欧拉回路具体求法如下：

把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。

好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。

现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。

首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。
之后，察看从S发出的所有边是否满流。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。

代码：

md因为边的数量初始化为0一直没检查出来错在哪·····下次要注意细节了····

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N=;

const int M=;

struct node

{

  int from,go;

  int val1,val2;

}edge[M];

int n,m,tot,father[N],size[N],chu[N],ru[N],src,des,maxx,temp;

int first[N],go[M*],next[M*],rest[M*],lev[N],cur[N],totl;

inline int getfa(int a)

{

  if(father[a]==a)  return a;

  father[a]=getfa(father[a]);

  return father[a];

}

inline void combfa(int a,int b)

{

  int fa=getfa(a);

  int fb=getfa(b);

  if(fa!=fb)

    father[fa]=fb,size[fb]+=size[fa];

}

inline void comb(int a,int b,int c)

{

  next[++totl]=first[a],first[a]=totl,go[totl]=b,rest[totl]=c;

  next[++totl]=first[b],first[b]=totl,go[totl]=a,rest[totl]=;

}

inline bool bfs()

{

  for(int i=src;i<=des;i++)  cur[i]=first[i],lev[i]=-;

  static int que[N],tail,u,v;

  que[tail=]=src;

  lev[src]=;

  for(int head=;head<=tail;head++)

  {

    u=que[head];

    for(int e=first[u];e;e=next[e])

    {

      if(lev[v=go[e]]==-&&rest[e])

      {

        lev[v]=lev[u]+;

        que[++tail]=v;

        if(v==des)  return true;

      }

    }

  }

  return false;

}

inline int dinic(int u,int flow)

{

  if(u==des)

    return flow;

  int res=,delta,v;

  for(int &e=cur[u];e;e=next[e])

  {

    if(lev[v=go[e]]>lev[u]&&rest[e])

    {

      delta=dinic(v,min(flow-res,rest[e]));

      if(delta)

      {

        rest[e]-=delta;

        rest[e^]+=delta;

        res+=delta;

        if(res==flow)  break;

      }

    }

  }

  if(flow!=res)  lev[u]=-;

  return res;

}

inline void maxflow()

{

  while(bfs())

    temp+=dinic(src,);

}

inline bool check(int limit)

{

  memset(chu,,sizeof(chu));

  memset(ru,,sizeof(ru));

  memset(first,,sizeof(first));

  src=,des=n+,maxx=,temp=,totl=;

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

    father[i]=i,size[i]=;

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

  {

    if(edge[i].val1<=limit&&edge[i].val2<=limit)//无向边定向

    {

      comb(edge[i].from,edge[i].go,);

      chu[edge[i].from]++;

      ru[edge[i].go]++;

      combfa(edge[i].go,edge[i].from);

     }

    else

      if(edge[i].val1<=limit)

      {

        chu[edge[i].from]++;

        ru[edge[i].go]++;

        combfa(edge[i].from,edge[i].go);

       }

      else

        if(edge[i].val2<=limit)

        {

          chu[edge[i].go]++;

          ru[edge[i].from]++;

          combfa(edge[i].from,edge[i].go);

        }

        else return false;

  }

  if(size[getfa()]!=n)  return false;

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

  {

    if(chu[i]==ru[i])  continue;

    if(ru[i]<chu[i])

    {

      if((chu[i]-ru[i])%==)  return false;

      else  comb(src,i,(chu[i]-ru[i])/),maxx+=((chu[i]-ru[i])/);

    }

    else

    {

      if((ru[i]-chu[i])%==)  return false;

      else comb(i,des,(ru[i]-chu[i])/);

    }

  }

  maxflow();

  if(temp!=maxx)  return false;

  else return true;

}

inline bool cmp(node a,node b)

{

  return a.val1<b.val1;

}

int main()

{

  //freopen("a.in","r",stdin);

  scanf("%d%d",&n,&m);

  int a,b,c,d,ans=;

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

  {

    scanf("%d%d%d%d",&a,&b,&c,&d);

    edge[i].from=a;

    edge[i].go=b;

    edge[i].val1=c;

    edge[i].val2=d;

  }

  int left=,right=;

  while(left<=right)

  {

    int mid=(left+right)/;

    if(check(mid))  right=mid-,ans=mid;

    else left=mid+;

  }

  if(!ans)  cout<<"NIE"<<endl;

  else cout<<ans<<endl;

  return ;

}

巴特西