混合图欧拉回路（hdoj3472 HS BDC）

清疚 2022-08-05 12:26 119阅读 0赞

欧拉回路基础知识[戳这里][Link 1]

混合图：就是图里面有的边是有向边，有的边是无向边，组成的图叫做混合图。  
要判混合图是否满足欧拉回路，首先必须满足欧拉图的条件  
1：欧拉回路要求所有点的度数必须都为偶数，欧拉道路要求所有点的度数两个奇数。  
2：给无向的边定向，首先任意定向，这些便之间网络流建边from到to容量为1，然后对于当前入度大于出度的点y，说明有d = （入度-出度）/2的边需要变成相反方向，我们这里不进行变向，而是用一个网络流的超级汇点T，给其建边y到T，容量为d。  
然后对于当前出度大于入度的点x，说明有d = （出度-入度）/2的边需要变成相反方向，我们这里不进行变向，而是用一个网络流的超级源点S，给其建边S到x，容量为d。  
这样，跑一次网络流，如果满流flow，则说明把入度大于出度和出度大于入度之间的flow个边变成相反方向之后，就是一个欧拉图。

比如题目：[hdoj3472 HS BDC][]

就是判混合图欧拉回路，但是这个图还要判图连通性。  
简化只判联通性版本可以看[nyoj99单词拼接][nyoj99]也比较考验代码

AC代码：

#include <iostream>
    #include <string.h>
    #include <math.h>
    #include <queue>
    #include <algorithm>
    #include <stdlib.h>
    #include <map>
    #include <set>
    #include <stdio.h>
    #include <vector>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 1020;
    const int inf = 0x3f3f3f3f;
    
    struct Edge
    {
        int from,to,cap,flow;
    };
    struct Dinic
    {
        int n,m,s,t;
        vector<Edge> edges;
        vector<int> G[N];
        bool vis[N];
        int d[N],cur[N];
         void init(int n)
        {
            this->n=n;
            for(int i=0;i<=n;i++)G[i].clear();
            edges.clear();
        }
        void AddEdge(int from,int to,int cap){  //建边
            edges.push_back((Edge){from,to,cap,0});
            edges.push_back((Edge){to,from,0,0});
            m=edges.size();
            G[from].push_back(m-2);
            G[to].push_back(m-1);
        }
        bool BFS()
        {
            Del(vis,0);
            queue<int> q;
            q.push(s);
            d[s]=0;
            vis[s]=1;
            while(!q.empty())
            {
                int x=q.front();q.pop();
                for(int i=0;i<G[x].size();i++)
                {
                    Edge &e =edges[G[x][i]];
                    if(!vis[e.to] && e.cap>e.flow)
                    {
                        vis[e.to]=1;
                        d[e.to]=d[x]+1;
                        q.push(e.to);
                    }
                }
            }
            return vis[t];
        }
        int DFS(int x,int a)
        {
            if(x==t || a==0)
                return a;
            int flow=0,f;
            for(int& i=cur[x];i<G[x].size();i++)
            {
                Edge & e = edges[G[x][i]];
                if(d[x]+1 == d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0)
                {
                    e.flow+=f;
                    edges[G[x][i]^1].flow -= f;
                    flow+=f;
                    a-=f;
                    if(a==0)
                        break;
                }
            }
            return flow;
        }
        int max_flow(int s,int t)
        {
            this->s=s;this->t=t;
            int flow=0;
            while(BFS())
            {
                Del(cur,0);
                flow+=DFS(s,inf);
            }
            return flow;
        }
        void print()
        {
            for(int i=0;i<edges.size();i++)
                printf("%c %c %d\n",edges[i].from+'a',edges[i].to+'a',edges[i].cap);
        }
    };
    Dinic solve;
    int in[30];
    bool ok[30];
    bool mp[30][30];
    void dfs(int x)
    {
        for(int i=0;i<26;i++)
            if(ok[i]==true && mp[x][i])
            {
                ok[i] = false;
                dfs(i);
            }
    }
    int S,TT,ans;
    bool yougth()
    {
        Del(in,0),Del(ok,false),Del(mp,false);
        solve.init(28);
        int n;
        scanf("%d",&n);
        int ss = 0,tt = 0,cnt = 0;
        S = 27,TT = 28,ans = 0;
        for(int i=0; i<n; i++)
        {
            string s;
            int z;
            cin>>s>>z;
            int one = s[0]-'a',two = s[ s.size()-1 ]-'a';
            in[one]--;
            in[two]++;
            ok[one] = ok[two] = true;
            mp[one][two] = true;
            ss = one;
            if(z==1){
                mp[two][one] = true;
                solve.AddEdge(one,two,1);
            }
        }
        for(int i=0;i<26;i++)
        {
            if(in[i]%2)
            {
                cnt++;
                if(in[i]<0){
                    ss = i;
                }
                else if(in[i]>0)
                    tt = i;
            }
        }
        if(cnt==0 || cnt==2)
        {
            dfs(ss);
            ok[ss] = false;
            for(int i=0;i<26;i++)
                if(ok[i]==true)
                    return false;
            if(cnt==2)
            {
                in[ss]++;in[tt]--;
                solve.AddEdge(tt,ss,1);  ///注意见反向边
            }
        }
        else
            return false;
        for(int i=0;i<26;i++)
        {
            if(in[i]<0)
            {
                solve.AddEdge(S,i,-in[i]/2);
            }
            else if(in[i]>0)
            {
                solve.AddEdge(i,TT,in[i]/2);
                ans+=in[i]/2;
            }
        }
        return true;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        for(int cas = 1;cas<=T;cas++)
        {
            printf("Case %d: ",cas);
            if(yougth())
            {
                int flow = solve.max_flow(S,TT);
                if(flow == ans)
                    puts("Well done!");
                else
                    puts("1Poor boy!");
            }
            else
                puts("Poor boy!");
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/y990041769/article/details/9371591
[hdoj3472 HS BDC]: http://acm.hdu.edu.cn/showproblem.php?pid=3472
[nyoj99]: http://acm.nyist.net/JudgeOnline/problem.php?pid=99