Poj 1637 Sightseeing tour (混合图的欧拉回路判定)

╰+哭是因爲堅強的太久メ 2022-08-25 12:58 48阅读 0赞

题意：给出一个混合图，要求判定欧拉回路是否存在，输入 x y d，如果d为0则为无向边，为1则为有向边。

关于有向图和无向图的欧拉回路可以参考我的另一篇博文[ 欧拉通路 欧拉回路的判定 Hdu 1878 欧拉回路][_ _ Hdu 1878]

以下内容参考了：[ZOJ 1992 & POJ 1637 (混合图欧拉回路) | 翅膀~][ZOJ 1992 _ POJ 1637 _ _]

首先应该判定图的连通性！本题所给图均是连通的，所以没有判断。

对所有的无向边随便定向，之后再进行调整。

统计每个点的出入度，如果有某个点出入度之差为奇数，则不存在欧拉回路，因为相差为奇数的话，无论如果调整边，都不能使得每个点的出入度相等。

现在每个点的出入度之差为偶数了，把这个偶数除以2,得x。则对每个顶点改变与之相连的x条边的方向就可以使得该点出入度相等。如果每个点都能达到出入度相等，自然就存在欧拉回路了。

现在问题就变成了改变哪些边的方向能让每个点出入度相等了，构造网络流模型。

有向边不能改变方向，所以不添加有向边。对于在开始的时候任意定向的无向边，按所定的方向加边，容量为1。

对于刚才提到的x，如果x大于0，则建一条s（源点）到当前点容量为x的边，如果x小于0，建一条从当前点到 t（汇点）容量为|x|的边。

这时与原点相连的都是缺少入度的点，与汇点相连的都是缺少出度的点，

建图完成了，求解最大流，如果能满流分配，则存在欧拉回路。那么哪些边改变方向才能得到欧拉回路呢？查看流量分配，所有流量非0的边就是要改变方向的边。

原理是因为满流分配，所以和源点相连的点一定都有x条边流入，将这些边反向这些点就出入度相等了，和汇点相连的亦然。没有和源、汇相连的已经出入度相等了，当然不用修改，至此欧拉回路求解完毕。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    
    const int INF = 0x3fffffff ;   //权值上限
    const int MAXPT = 205 ;     //顶点数上限
    const int MAXEG = 5005 ;    //边数上限
    const int MAXQUE = 10005 ;	   // 队列长度
    
    /*
        s = 1 ; // 源点
    	t 根据初始化函数的不同改变
    */
    template<typename Type>
    class MNF_SAP
    {
    private:
        int s,t;
        int dis[MAXPT];   //距离标号
        int pre[MAXPT];   //前置顶点
        Type flow[MAXPT];  //到当前点为止，所有弧的最小值
        int curedge[MAXPT];   //当前弧cur
        int cnt[MAXPT];   //k标号出现次数
        int queue[MAXQUE],front,rear;
        bool vis[MAXPT];
    
        void BFS ()
        {
            int i,u;
            memset(vis,false,sizeof(vis));
            front=rear=0;
            dis[t]=0;
            vis[t]=true;
            queue[++rear]=t;
            while (front!=rear)
            {
                u=queue[(++front)%MAXQUE];
                for (i=head[u];i!=0;i=edges[i].next)
                    if (vis[edges[i].v]==false && !edges[i].cap)
                    {
                        dis[edges[i].v]=dis[u]+1;
                        vis[edges[i].v]=true;
                        queue[(++rear)%MAXQUE]=edges[i].v;
                    }
            }
    		for (i=1;i<=n;i++)
    			cnt[dis[i]]++;
        }
    public:
    
        struct Node
        {
            int v,next;
    		Type cap;
    		Node(){}
    		Node (int _v,Type _cap,int _next)
    		{
    			v=_v;
    			cap=_cap;
    			next=_next;
    		}
        }edges[MAXEG];
        int n;      //总节点数
    	int e;
        int head[MAXPT];
    
    	void Init (int _n)    //算法初始化
    	{
    		s=1,t=_n;   //源点1汇点n
    		n=_n;
    		e=2;
    		memset (head,0,sizeof(head));
    	}
    
    	void Init (int _s,int _t) //算法初始化,后续需要对n赋值
    	{
    		s=1;   //源点1,汇点指定
    		t=_t;
    		e=2;
    		memset (head,0,sizeof(head));
    	}
    
    	void Add (int u,int v,Type cap)   //始,终,量
    	{
    		edges[e]=Node(v,cap,head[u]);
    		head[u]=e++;
    		edges[e]=Node(u,0,head[v]);
    		head[v]=e++;
    	}
    
        Type SAP ()
        {
            int u,v,i;
    		Type maxflow=0;   //总最大流
            u=s;
            flow[s]=INF;
            for (i=1;i<=n;i++)
    			curedge[i]=head[i];     //当前弧初始化
            BFS ();
            cnt[0]=n;
            while (dis[s]<n)
            {
                for (i=curedge[u];i!=0;i=edges[i].next)        //找允许弧
                    if (edges[i].cap>0 && dis[edges[i].v]+1==dis[u])          //
    					break;
                if (i!=0)      //存在允许弧
                {
                    curedge[u]=i;         //设置当前弧
                    v=edges[i].v;
                    if (edges[i].cap<flow[u])
    					flow[v]=edges[i].cap;
                    else
    					flow[v]=flow[u];  //标记当前顶点为止经过的最小弧
                    u=v;
                    pre[v]=i;  //前置顶点边号
                    if (u==t)
                    {
                        do
                        {
                            edges[pre[u]].cap-=flow[t];          //正向弧减a[t]
                            edges[pre[u]^1].cap+=flow[t];        //通过异或操作找反向弧
                            u=edges[pre[u]^1].v;
                        }
                        while (u!=s);
                        maxflow+=flow[t];
                        //memset(flow,0,sizeof(flow));
                        flow[s]=INF;
                    }
                }
                else   //不存在允许弧
                {
                    if (--cnt[dis[u]]==0)
    					break;     //间隙优化
                    dis[u]=n;
                    curedge[u]=head[u];
                    for (i=head[u];i!=0;i=edges[i].next)
                        if (edges[i].cap && dis[edges[i].v]+1<dis[u])
                            dis[u]=dis[edges[i].v]+1;       //修改距离标号为 最小的非允许弧加1
                    cnt[dis[u]]++;
                    if (u!=s)
    					u=edges[pre[u]^1].v;
                }
            }
            return maxflow;
        }
    };
    
    MNF_SAP<int> ob;
    int n,degree[210];  //不足的入度
    
    bool Judge (int n)
    {
    	int sum=0;
    	for (int i=1;i<=n;i++)
    		if (degree[i]%2==1) //为奇数不可能存在
    			return false;
    		else
    		{
    			if (degree[i]>0)
    			{	
    				ob.Add (1,1+i,degree[i]/2);
    				sum+=degree[i]/2;
    			}
    			else
    				ob.Add(1+i,n+2,-degree[i]/2);  //连向汇点
    		}		
    	if (ob.SAP()==sum)
    		return true;
    	else
    		return false;
    }
    
    int main ()
    {
    	int T,m;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d%d",&n,&m);
    		ob.Init(n+2);
    		memset(degree,0,sizeof(degree));
    		for (int i=1;i<=m;i++)
    		{
    			int x,y,d;
    			scanf("%d%d%d",&x,&y,&d);
    			degree[x]++;
    			degree[y]--;
    			if (d==0)  //无向图
    				ob.Add (1+x,1+y,1);
    		}
    		if (Judge(n))
    			printf("possible\n");
    		else
    			printf("impossible\n");
    	}
    	return 0;
    }

[_ _ Hdu 1878]: http://blog.csdn.net/whyorwhnt/article/details/20079377
[ZOJ 1992 _ POJ 1637 _ _]: http://zhyu.me/acm/zoj-1992-and-poj-1637.html