题目链接: poj 1637
题目大意: 给出既有有向边,又有无向边的图
问该图是否存在欧拉回路
解题思路: 先把无向边任意定向,然后记录每个结点的出度和入度,设X=出度-入度
若X为奇数,就不存在欧拉回路,因为把边反向只会使得X+-2,无论如何也不能得到0
建立超级源点和汇点求最大流:
1.当前顶点的X为偶数并且小于0,源点指向该点,容量为X/2边
2.当前顶点的X为偶数并且大于0,该点指向汇点,容量为X/2边
3.把所有的无向边按原来的指向,建立边,容量为1
若网络流达到满流则存在欧拉回路
最终的结果是要使得所有顶点的出度等于入度,如果存在X不为0的情况,就需要把某些边反向
反向一条边,使X+2或者X-2,若能达到满流则所有会源点或汇点相连的顶点都能使得X=0
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 203 #define Min(a,b) (a<b?a:b) #define INF 0x3f3f3f3f int S,E,visit[MAX],flag[MAX][MAX],Map[MAX][MAX],pre[MAX],Index; int path[MAX],listb[MAX<<1],In[MAX],To[MAX]; struct snode{ int c,to,next; }Edge[MAX*MAX]; int Fabs(int x) { return (x<0)?-x:x; } void Add_edge(int a,int b,int c) { Edge[Index].to=b,Edge[Index].c=c; Edge[Index].next=pre[a]; pre[a]=Index++; } bool BFS() //BFS寻找增广路 { int i,s,e,v,vv; s=e=0; memset(visit,0,sizeof(visit)); memset(flag,0,sizeof(flag)); listb[s++]=S; visit[S]=1; while(s!=e) { v=listb[e++]; if(v==E) return true; for(i=pre[v];i!=-1;i=Edge[i].next) { vv=Edge[i].to; if(!visit[vv]&&Map[v][vv]>=1) { visit[vv]=1; listb[s++]=vv; flag[v][vv]=1; } } } return false; } int DFS(int v,int sum) { int s=sum,i,t,vv; if(v==E||sum==0) return sum; for(i=pre[v];i!=-1;i=Edge[i].next) { vv=Edge[i].to; if(flag[v][vv]) { t=DFS(vv,Min(sum,Map[v][vv])); Map[v][vv]-=t; Map[vv][v]+=t; sum-=t; } } return s-sum; } int Solve() //Dinic { int sum=0; while(BFS()) sum+=DFS(S,INF); return sum; } int main() { int n,m,i,j,a,b,c,sum1,t,temp3; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); Index=sum1=0,S=0,E=n+1; memset(In,0,sizeof(In)); memset(To,0,sizeof(To)); memset(pre,-1,sizeof(pre)); memset(Map,0,sizeof(Map)); for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); To[a]++,In[b]++; if(c==0) //中间建图 { c=1; if(!Map[a][b]) { Add_edge(a,b,c); Add_edge(b,a,-c); } Map[a][b]+=c; } } int pd=0,temp,temp1; for(i=1;i<=n;i++) { temp=In[i]-To[i]; temp1=Fabs(temp); if(temp1!=0&&temp1%2==0) { if(temp<0) //左边 { a=S,b=i,c=temp1/2,sum1+=c; if(!Map[a][b]) { Add_edge(a,b,c); Add_edge(b,a,-c); } Map[a][b]+=c; } else //右边 { a=i,b=E,c=temp1/2; if(!Map[a][b]) { Add_edge(a,b,c); Add_edge(b,a,-c); } Map[a][b]+=c; } } else if(temp1!=0) { pd=1; break; } } if(pd==1) printf("impossible\n"); else { temp3=Solve(); if(sum1==temp3) printf("possible\n"); else printf("impossible\n"); } } }