http://poj.org/problem?id=1637
题意：
给出一张混合图，判断是否存在欧拉回路
原理：
1、存在欧拉回路的充要条件：所有点入度=出度
2、给无向边随便定向不会影响点的|出度-入度|的奇偶性
3、有向图存在欧拉回路径的必要条件：不存在|出度-入度|为奇数的点
将所有的无向边随便定向，计算d[i]=点i的出度-入度，如果有d[i]为奇数，一定不存在欧拉回路
接下来的问题，就是判断是否可以通过改变某些无向边的方向，使所有点的出度=入度（度数平衡）
这可以联想到网络流的流量平衡
点i只需要改变|d[i]|/2条边，便可以达到度数平衡
所以若i的入度>出度，由点i向汇点连流量为|d[i]/2|的边
若i的入度<出度，由源点向i连流量为|d[i]/2|的边
无向边怎么定的向，就在网络中怎么连边，流量为1
若可以满流，则原图存在欧拉回路
因为若源点向i有x的流量，表示与i相连的边中，要改变x条边的方向，才能使点i的度数平衡
增广路走哪条边，表示哪条边需要改变方向（因为开始时是对无向边随意定向）
所以当满流的时候，找到了所有需要改变方向的边
则原图的欧拉回路就是 原先的有向边+网络流中流量为1的边（没有增广路经过的边+有增广路经过的边的反向边）
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define N 205 #define M 3001 int n,m; struct node { int u,v; bool ty; }e[M]; int d[N]; int front[N],nxt[M],to[M],cap[M],tot; int src,decc; int lev[N],cur[N]; queue<int>q; template<typename T> void read(T &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar();} } void add(int u,int v,int w) { to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w; to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=0; } bool bfs() { int now,t; for(int i=0;i<=decc;++i) lev[i]=-1,cur[i]=front[i]; lev[src]=0; q.push(src); while(!q.empty()) { now=q.front(); q.pop(); for(int i=front[now];i;i=nxt[i]) { t=to[i]; if(lev[t]==-1 && cap[i]) { lev[t]=lev[now]+1; q.push(t); } } } return lev[decc]!=-1; } int dinic(int now,int flow) { if(now==decc) return flow; int rest=0; int delta,t; for(int &i=cur[now];i;i=nxt[i]) { t=to[i]; if(lev[t]==lev[now]+1 && cap[i]) { delta=dinic(t,min(cap[i],flow-rest)); if(delta) { rest+=delta; cap[i]-=delta; cap[i^1]+=delta; if(rest==flow) break; } } } if(rest!=flow) lev[now]=-1; return rest; } bool judge() { memset(d,0,sizeof(d)); for(int i=1;i<=m;++i) d[e[i].u]++,d[e[i].v]--; for(int i=1;i<=n;++i) if(d[i]&1) return false; src=0; decc=n+1; int sum=0; tot=1; memset(front,0,sizeof(front)); for(int i=1;i<=n;++i) if(d[i]>0) add(src,i,d[i]/2),sum+=d[i]/2; else if(d[i]<0) add(i,decc,-d[i]/2); for(int i=1;i<=m;++i) if(!e[i].ty) add(e[i].u,e[i].v,1); int max_flow=0; while(bfs()) max_flow+=dinic(src,1e8); return max_flow==sum; } int main() { int T; read(T); while(T--) { read(n); read(m); for(int i=1;i<=m;++i) { read(e[i].u); read(e[i].v); read(e[i].ty); } puts(judge()?"possible":"impossible"); } }