第一次遇见混合欧拉回路,不懂。查看了解题报告才了解此类问题的解法。
以下摘自:http://zhyu.me/acm/zoj-1992-and-poj-1637.html
题意:给出一个混合图(有的边有向,有的边无向),问此图是否存在欧拉回路。
先说说欧拉回路吧,起点和终点相同,经过图G的每条边一次,且只经过一次的路径称为欧拉回路。
按照图的不同分为:无向图欧拉回路、有向图欧拉回路和混合图欧拉回路。
判断一个图是否存在欧拉回路:
1.无向图:图连通,且图中均为偶度顶点。
2.有向图:图连通,且图中所有顶点出入度相等。
3.混合图:混合图欧拉回路的判断是用网络流,实现方法:
首先对所有的无向边随便定向,之后会进行调整。然后统计每个点的出入度,如果有某个点出入度之差为奇数,则不存在欧拉回路,因为相差为奇数的话,无论如果调整边,都不能使得每个点的出入度相等。
现在每个点的出入度之差为偶数了,把这个偶数除以2,得x。则对每个顶点改变与之相连的x条边的方向就可以使得该点出入度相等。如果每个点都能达到出入度相等,自然就存在欧拉回路了。
现在问题就变成了改变哪些边的方向能让每个点出入度相等了,构造网络流模型。
有向边不能改变方向,所以不添加有向边。对于在开始的时候任意定向的无向边,按所定的方向加边,容量为1。源点向所有出>入的点连边,容量为该点的x值;所有入>出的点向汇点连边,容量为该点的x值。
建图完成了,求解最大流,如果能满流分配,则存在欧拉回路。那么哪些边改变方向才能得到欧拉回路呢?查看流量分配,所有流量非0的边就是要改变方向的边。
原理是因为满流分配,所以和源点相连的点一定都有x条边流入,将这些边反向这些点就出入度相等了,和汇点相连的亦然。没有和源、汇相连的已经出入度相等了,当然不用修改,至此欧拉回路求解完毕。
关于这题:边数应该开到4000以上。刚开始开2000WA了,原因,每加一条边都有正向边和反向边所以最大为2000条,加上src点和des汇点的2000.
//208 KB 16 ms #include <stdio.h> #include <string.h> #include <stdlib.h> const int VM = 205; const int EM = 4005; const int inf = 0x3f3f3f3f; struct Edge { int frm,to,next,cap; }edge[EM]; int head[VM],in[VM],out[VM]; int ep,n,m,src,des; int dep[VM]; void addedge (int cu,int cv,int cw) { edge[ep].frm = cu; edge[ep].to = cv; edge[ep].cap = cw; edge[ep].next = head[cu]; head[cu] = ep ++; edge[ep].frm = cv; edge[ep].to = cu; edge[ep].cap = 0; edge[ep].next = head[cv]; head[cv] = ep ++; } int BFS () { int que[VM],i,front = 0,rear = 0; memset (dep,-1,sizeof(dep)); que[rear++] = src; dep[src] = 0; while (front != rear) { int u = que[front++]; front = front%VM; for (i = head[u];i != -1;i = edge[i].next) { int v = edge[i].to; if (edge[i].cap > 0&&dep[v] == -1) { dep[v] = dep[u] + 1; que[rear ++] = v; rear = rear % VM; if (v == des) return 1; } } } return 0; } int dinic () { int i,res = 0,top; int stack[VM]; int cur[VM]; while (BFS()) { memcpy (cur,head,sizeof (head)); int u = src; top = 0; while (1) { if (u == des) { int min = inf,loc ; for (i = 0;i < top;i ++) if (min > edge[stack[i]].cap) { min = edge[stack[i]].cap; loc = i; } for (i = 0;i < top;i ++) { edge[stack[i]].cap -= min; edge[stack[i]^1].cap += min; } res += min; top = loc; u = edge[stack[top]].frm; } for (i = cur[u];i != -1;cur[u] = i = edge[i].next) if (edge[i].cap != 0&&dep[u] + 1 == dep[edge[i].to]) break; if (cur[u] != -1) { stack[top ++] = cur[u]; u = edge[cur[u]].to; } else { if (top == 0) break; dep[u] = -1; u = edge[stack[--top]].frm; } } } return res; } int main () { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int T,i,u,v,ops; scanf ("%d",&T); while (T --) { scanf ("%d%d",&n,&m); memset (head,-1,sizeof(head)); memset (in,0,sizeof(in)); memset (out,0,sizeof(out)); ep = 0,src = 0,des = n + 1; while (m --) { scanf ("%d%d%d",&u,&v,&ops); out[u] ++; in[v] ++; if (!ops) addedge (u,v,1); } bool flag = true; for (i = 1;i <= n;i ++) if (abs(in[i] - out[i])&1){ flag = false; break; } int sum = 0; if (!flag) printf ("impossible\n"); else { for (i = 1;i <= n;i ++) { int w = (out[i] - in[i]) /2; if (w > 0){ sum += w; addedge (src,i,w); } else addedge (i,des,-w); } if (sum == dinic()) printf ("possible\n"); else printf ("impossible\n"); } } return 0; }