预备知识
1、欧拉回路是图G中的一个回路，经过每条边有且仅一次，称该回路为欧拉回路。具有欧拉回路的图称为欧拉图，简称E图。
2、 无向图中存在欧拉回路的条件：每个点的度数均为偶数。
3、有向图中存在欧拉回路的条件：每个点的入度 = 出度。
4、欧拉路径比欧拉回路要求少一点：无向图中存在欧拉路径的条件：每个点的度数均为偶数或者有且仅有2个度数为奇数的点。
5、有向图中存在欧拉路径的条件：除了2个点外，其余的点入度=出度，且在这2个点中，一个点的入度比出度大1，另一个出度比入度大1。
6、欧拉路径的输出：经典的套圈算法。
求解一般图欧拉回路的基本算法
对于欧拉回路，有一个基本的算法：对于无向图，每个点的度都是偶数，则图中有欧拉回路存在；对于有向图，只要每个点的出度等于入度，则图中有欧拉回路存在。
求解混合图欧拉回路的一般方法
1、随意定向
在混合图中，对于双向边的处理除了拆边之外，还有任意定向。先对全图的双向边进行任意定向，接着使用上文的欧拉回路算法，很显然，无法得到结果。但是通过这一步，至少可以确定这样一件事实，如果一个点的出度加入度一定是奇数的话，那么这个图一定没有欧拉回路。
而随意定向是没有依据的，但是可以使用这样的随机化处理方法，再使用恰当的调整方法构造出解。
2、自调整方法
所谓的自调整方法就是将其中的一些边的方向调整回来，使所有的点的出度等于入度。但是有一条边的方向改变后，可能会改变一个点的出度的同时改变另一个点的入度，相当于一条边制约着两个点。同时有些点的出度大于入度，迫切希望它的某些点出边转向；而有些点的入度大于出度，迫切希望它的某些入边转向。这两条边虽然需求不同，但是他们之间往往一条边转向就能同时满足二者。
具体步骤：
1、另x = |入度-出度|/2；对于不同的点有不同的x值，这个x值代表它们在邻接表中相应调整x条就能让出度等于入度。
2、以把图中的点转换为一个二分图，每个点的x值就是它们的点权。
3、置源点S向所有出度>入度的点连边；设置汇点T，所有入度大于出度的点连边，将各自的点权转换为边权。
4、最后将原图中所有暂时定向的无向边加上一个1的容量，方向不变，而有向边不能改变方向，不需连边。
可以发现，从源点S出发的一个单位流将会一个“无向边”的容量变为0，使得两端的点权各自减1，其实这就是在模拟一次对无向边方向的调整。当把图建好后，依靠最大流性质可以最大可能地无冲突调整边的方向，并最终使得每个点的点容量都达到满流。
最后，还要对那些图中出度等于入度的点做适当分析，它们作为一个“中间点”，由于流平衡性质，不会留下任何流量值，对于那些真正需要调整的点不会带来任何影响。
最后，如何得到答案？那就是检查从源点出发的每条边是否都满流，如果有一条边没有满流，说明有一个点没有调整到入度等于出度，于是整个图不存在欧拉回路。
具体的题目有: POJ 1637、 Hdu 3472
附POJ 1637 代码：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int MAXN = 1010;
const int MAXM = 50010;
const int INF = 0x3f3f3f3f;
struct Edge
{
int v, f;
int next;
}edge[MAXM];
int n, m;
int cnt;
int s, t;
int first[MAXN], level[MAXN];
int q[MAXN];
int ind[MAXN], outd[MAXN];
int totFlow;
void init()
{
cnt = 0;
totFlow = 0;
memset(first, -1, sizeof(first));
memset(ind, 0, sizeof(ind));
memset(outd, 0, sizeof(outd));
}
void read(int u, int v, int f)
{
edge[cnt].v = v, edge[cnt].f = f;
edge[cnt].next = first[u], first[u] = cnt++;
}
void read_graph(int u, int v, int f)
{
read(u, v, f);
read(v, u, 0);
}
int bfs(int s, int t)
{
memset(level, 0, sizeof(level));
level[s] = 1;
int front = 0, rear = 1;
q[front] = s;
while(front < rear)
{
int x = q[front++];
if(x == t) return 1;
for(int e = first[x]; e != -1; e = edge[e].next)
{
int v = edge[e].v, f = edge[e].f;
if(!level[v] && f)
{
level[v] = level[x] + 1;
q[rear++] = v;
}
}
}
return 0;
}
int dfs(int u, int maxf, int t)
{
if(u == t) return maxf;
int ret = 0;
for(int e = first[u]; e != -1; e = edge[e].next)
{
int v = edge[e].v, f = edge[e].f;
if(level[v] == level[u] + 1 && f)
{
int Min = min(maxf-ret, f);
f = dfs(v, Min, t);
edge[e].f -= f;
edge[e^1].f += f;
ret += f;
if(ret == maxf) return ret;
}
}
return ret;
}
int Dinic(int s, int t)
{
int ans = 0;
while(bfs(s, t)) ans += dfs(s, INF, t);
return ans;
}
void read_case()
{
init();
scanf("%d%d", &n, &m);
while(m--)
{
int u, v, flag;
scanf("%d%d%d", &u, &v, &flag);
outd[u]++, ind[v]++;
if(u != v)
{
if(!flag) read_graph(u, v, 1);
}
}
}
int build()
{
int flag = 1;
s = 0, t = n+1;
for(int i = 1; i <= n; i++)
{
if((ind[i]+outd[i]) & 1) //出度加入度是奇数
{
return 0;
}
else if(outd[i] > ind[i]) //出度大于入度
{
int dif = outd[i]-ind[i];
read_graph(s, i, dif/2);
totFlow += dif/2;
} //可能有入度等于出度的情况,连不连无所谓
else
{
int dif = ind[i]-outd[i];
read_graph(i, t, dif/2);
}
}
return 1;
}
void solve()
{
read_case();
int flag = build();
int ans = Dinic(s, t);
if(!flag) printf("impossible\n");
else if(ans >= totFlow) printf("possible\n");
else printf("impossible\n");
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
solve();
}
return 0;
}