题目链接：http://poj.org/problem?id=1637 题目大意： 给你一个混合图，问你能不能经过每条边一次，遍历所有的节点。 思路：刚开始直接做发现第一个样例推不出来，但是发现的确是可以有欧拉回路的，后来纸上画了画，发现，这个能不能找到欧拉回路与双向边的遍历方向有关，其实可以这样考虑，把这个图当做一个有向图来做，其中有几条边的方向可以自己确定，但是要保证每个点的入度等于出度（有向图存在欧拉回路的条件）。
1.为任意一条无向边选择一个方向。如果存在欧拉回路的话，那么可以得到每个点入度于出度差至少应满足为偶数。否则一定不能够构成欧拉回路。
2.在满足上述条件的基础上，我们需要对我们假定的边进行修正，如果最后能够修正成所有点的入度等于出度那么就能够得出这个混合图的欧拉回路（通过正确的化无向边为有向边）。如何修正呢，这时就可以转化为网络流问题求解：
可以定义对于入度大于出度的节点需要流出一些流量，出度大于入度的点需要接收一些流量，然后建立超级源点和超级汇点保持流平衡即可。具体这样构边：
A.某节点 i 入度大于出度，就从源点S连一条流量为(in[i] - out[i]) / 2的边到 i 。 B.某节点 i 出度大于入度，就从 i 连一条流量为(out[i] - in[i]) / 2的边到汇点T。 C.遍历 <i, j> 若假定 i, j 之间连接了mp[i][j] 条无向边，那么连接一条从 j 到 i 流量为mp[i][j]的边。为什么反过来，因为这是我们假设的，意味着我们有多少反悔的资本。
还有这个图的基图必须连通，若不连通则一定不存在欧拉环或欧拉路径（不考虑度数为0的点）。好像题目保证了连通。
最大流必须满流：所有点的入度都等于出度
对于 1 3 4 1 2 0 2 3 1 1 2 0 3 2 0 双向边默认方向u->v#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; int d[maxn], start, tend; struct node { int to, cap, next; } edge[maxn << 1]; int head[maxn]; int cnt; int in[maxn], out[maxn]; int mp[500][500]; int n, m, u, v, w; void init() { cnt = 0; memset(head, -1, sizeof(head)); memset(in ,0, sizeof(in)); memset(out, 0, sizeof(out)); memset(mp, 0, sizeof(mp)); } void addedge(int start, int to, int cap) { edge[cnt].to = to; edge[cnt].cap = cap; edge[cnt].next = head[start]; head[start] = cnt++; } bool BFS() { //memset(vis,false,sizeof(vis)); memset(d, -1, sizeof(d)); int Q[maxn * 2]; int Thead, Ttail; Thead = Ttail = 0; Q[Ttail++] = start;; d[start] = 0; //vis[start]=1; while (Thead<Ttail) { int x = Q[Thead]; if (x == tend) return true; for (int i = head[x]; i != -1; i = edge[i].next) { int temp = edge[i].to; if (d[temp] == -1 && edge[i].cap>0)//没有标记,且可行流大于0 { //vis[temp.to]=true; d[temp] = d[x] + 1; Q[Ttail++] = temp; } } Thead++; } return false;//汇点是否成功标号,也就是说是否找到增广路 } int DFS(int x, int cap) { if (x == tend) return cap; //vis[start]=true; int flow = 0, f; for (int i = head[x]; i != -1; i = edge[i].next) { int temp = edge[i].to; //if(temp.cap<=0||vis[temp.to])continue; if (d[temp] == d[x] + 1 && edge[i].cap) { f = DFS(temp, min(cap - flow, edge[i].cap)); edge[i].cap -= f; edge[i ^ 1].cap += f; flow += f; if (flow == cap) break; } } if (!flow) d[x] = -2;//防止重搜 return flow; } int maxflow() { int flow = 0, f; while (BFS()) { //memset(vis,false,sizeof(vis)); while ((f = DFS(start, INF))>0) flow += f; } return flow; } int Text() { int sum=0; for(int i=1;i<=n;i++) { if(in[i]-out[i]>0) { sum+=(in[i]-out[i])/2; addedge(0, i, (in[i]-out[i])/2); addedge(i, 0, 0); } if(in[i]-out[i]<0) { addedge(i, n+1, (out[i]-in[i])/2); addedge(n+1, i, 0); } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(mp[i][j]) { addedge(j, i, mp[i][j]); addedge(i, j, 0); } } } start=0; tend=n+1; return sum!=maxflow(); } int HS() { for(int i=1;i<=n;i++) { if(abs(in[i]-out[i])%2!=0) { return 0; } } return 1; } int main() { int t; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); in[v]++, out[u]++; if(w==0) { mp[u][v]++; } } if(HS()==0) { printf("impossible\n"); continue; } if(Text()) { printf("impossible\n"); } else { printf("possible\n"); } } return 0; }
