网络流之--混合图的欧拉回路

基础知识

    欧拉回路是图G中的一个回路，经过每条边有且仅一次，称该回路为欧拉回路。具有欧拉回路的图称为欧拉图，简称E图。

    无向图中存在欧拉回路的条件：每个点的度数均为偶数。

    有向图中存在欧拉回路的条件：每个点的入度=出度。

    欧拉路径比欧拉回路要求少一点：

    无向图中存在欧拉路径的条件：每个点的度数均为偶数或者有且仅有2个度数为奇数的点。

    有向图中存在欧拉路径的条件：除了2个点外，其余的点入度=出度，且在这2个点中，一个点的入度比出度大1，另一个出度比入度大1。

     欧拉路径的输出：经典的套圈算法。

 

    下面来重点讲讲混合图的欧拉回路问题。

    混合图就是边集中有有向边和无向边同时存在。这时候需要用网络流建模求解。

    建模：

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

    好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以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连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
    所以，就这样，混合图欧拉回路问题，解了。

 

例：HDU3472

题意：给出一些单词，其中有些单词反转之后也是有意义的单词，问是否能将所有单词首尾相连，每个单词用1次且仅用1次。

解：这题是混合路的欧拉路径问题。

    1.首先判断图的连通性，若不连通，无解。

    2.然后任意定向无向边，计算每个点i的入度和出度之差deg[i]。若deg[i]为奇数，无解。

    3.设立源点s和汇点t，若某点i入度<出度，连边(s,i,-deg[i]/2)，若入度>出度，连边(i,t,deg[i]/2)；对于任意定向的无向边(i,j,1)。

    4.若有两个度数为奇数的点，假设存在欧拉路径，添加一条容量为1的边，构成欧拉回路，不影响结果。若全为偶数，直接最大流。

    5.若从S发出的边全部满流，证明存在欧拉回路(路径)，否则不存在。

    ps：若要求输出路径，将网络中有(无)流量的边反向，加上原图的有向边，用套圈算法即可。

 

/*
混合图的欧拉回路
    建模：将有向边删除，给无向边任意定向，计算每个点的入度与出入之差，若为奇数，肯定无解；
    若为偶数，若图中存在边(i,j)，那么设容量为1；对于每个点i，若deg[i]<0，从s连边道i，容量为-deg[i]/2，若>0，连边(i,t,deg[i]/2)
    求最大流，如果所有从s出发的弧都满载，则存在欧拉回路，否则不存在。
    把图中所有有(无)流量的弧都反向，把原图中的有向边加上，就构成了一个欧拉回路。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int maxv = 30;
const int maxe = 5000;
int n;
struct Edge
{
    int v;
    int next;
    int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
int deg[30];
bool used[30];
int p[30],rank[30];

void addEdge(int a,int b,int c)
{
    e[edgeNum].v = b;
    e[edgeNum].flow = c;
    e[edgeNum].next = head[a];
    head[a] = edgeNum++;
    e[edgeNum].v = a;
    e[edgeNum].flow = 0;
    e[edgeNum].next = head[b];
    head[b] = edgeNum++;
}

void Init()
{
    edgeNum = 0;
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
}

int sap(int s,int t,int n)       //源点，汇点，结点总数
{
    int i,x,y;
    int f,ans = 0;
    for(i = 0; i < n; i++)
        now[i] = head[i];
    vh[0] = n;
    x = s;
    while(d[s] < n)
    {
        for(i = now[x]; i != -1; i = e[i].next)
            if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
                break;
            if(i != -1)
            {
                now[x] = preh[y] = i;
                pre[y] = x;
                if((x=y) == t)
                {
                    for(f = INF,i=t; i != s; i = pre[i])
                        if(e[preh[i]].flow < f)
                            f = e[preh[i]].flow;
                    ans += f;
                    do
                    {
                        e[preh[x]].flow -= f;
                        e[preh[x]^1].flow += f;
                        x = pre[x];
                    }while(x!=s);
                }
            }
            else
            {
                if(!--vh[d[x]])
                    break;
                d[x] = n;
                for(i=now[x]=head[x]; i != -1; i = e[i].next)
                {
                    if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
                    {
                        now[x] = i;
                        d[x] = d[e[i].v] + 1;
                    }
                }
                ++vh[d[x]];
                if(x != s)
                    x = pre[x];
            }
    }
    return ans;
}

void makeSet()
{
    for(int i = 0; i < 26; i++)
    {
        p[i] = i;
        rank[i] = 0;
    }
}

int findSet(int x)
{
    if(x != p[x])
        p[x] = findSet(p[x]);
    return p[x];
}

void Union(int x, int y)
{
    x = findSet(x);
    y = findSet(y);
    if(x == y)
        return;
    if(rank[x] > rank[y])
        p[y] = x;
    else
    {
        p[x] = y;
        if(rank[x] == rank[y])
            rank[y]++;
    }
}

int main()
{
    int i,j,k;
    int t,T;
    char wd[22];
    scanf("%d",&T);
    for(t = 1; t <= T; t++)
    {
        scanf("%d",&n);
        Init();
        makeSet();
        memset(deg,0,sizeof(deg));
        memset(used,0,sizeof(used));
        bool flag = true;
        for(i = 1; i <= n; i++)
        {
            scanf("%s %d",wd,&k);
            int len = strlen(wd);
            int a = wd[0]-'a';
            int b = wd[len-1]-'a';
            used[a] = true;
            used[b] = true;
            deg[a]--;
            deg[b]++;
            if(k == 1)
                addEdge(a,b,1);
            Union(a,b);
        }
        int start = 26;
        int end = 27;
        for(i = 0; i < 26 && flag; i++)                 //连通性
        {
            for(j = i+1; j < 26 && flag; j++)
            {
                if(used[i] && used[j] && findSet(i)!=findSet(j))
                    flag = false;
            }
        }
        int tmpt = 0;
        int v1=-1,v2=-1;
        for(i = 0; i < 26 && flag; i++)                 //度数为奇数的点为0个或者2个
        {
            if(deg[i]%2 == 1 || deg[i]%2 == -1)
            {
                tmpt++;
                if(deg[i] < 0)  //起点
                    v1 = i;
                if(deg[i] > 0)  //终点
                    v2 = i;
            }
        }
        if(tmpt==0 || (tmpt==2&&v1!=-1&&v2!=-1))
        {
            if(tmpt == 2)
                addEdge(v2,v1,1);
        }
        else
            flag = false;
        int sum = 0;
        for(i = 0; i < 26 && flag; i++)
        {
            if(deg[i] < 0)
            {
                addEdge(start,i,-deg[i]/2);
                sum += -deg[i]/2;
            }
            else
                addEdge(i,end,deg[i]/2);
        }
        if(!flag || sum != sap(start,end,end+1))
            printf("Case %d: Poor boy!\n",t);
        else
            printf("Case %d: Well done!\n",t);
    }
    return 0;
}