介绍神马的是抄来的……我也不知道是转自哪里的
题意：在一个城市中观光旅游，给出这个城市的一些街道，街道有单项和双向的。问是否能找到一条方案可以从某点出发经过每一条街道仅且一次而终回到起点。
题解：欧拉回路+网络流。
欧拉通路 (Euler tour)——通过图中每条边仅一次，并且过所有顶点的通路。
欧拉回路 (Euler circuit)——通过图中每条边仅一次，并且过每一顶点的回路。也就是有欧拉通路的回路。
欧拉图——存在欧拉回路的图。
判定无向图是否具有欧拉通路或回路的方法
图 G有欧拉通路的充分必要条件为：图 G 连通，图 G中只有两个奇度数顶点。它们肯定是欧拉通路的两个端点。
图 G有欧拉回路(图 G为欧拉图)的判定方法：图 G连通，图 G中均为偶度顶点。
判定有向图是否具有欧拉通路或回路的方法
有向图 G有欧拉通路：有向图 G连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。
有向图 G有欧拉回路(有向图 G为欧拉图)：有向图 G连通，有向图 G中所有顶点的入度等于出度。
混合图欧拉回路
把图的无向边随意定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
假如每个点入度和出度之差均为偶数。将这个偶数除以2，得x。即是说，对于每一个点，只要将x条边反向（出就是变入，入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
个人理解：说白了，就是看看有没有一种方法使得所有点的入度等于出度，用网络流来进行判定而已。
Sample Input
4
5 8
2 1 0
1 3 0
4 1 1
1 5 0
5 4 1
3 4 0
4 2 1
2 2 0
4 4
1 2 1
2 3 0
3 4 0
1 4 1
3 3
1 2 0
2 3 0
3 2 0
3 4
1 2 0
2 3 1
1 2 0
3 2 0
Sample Output
possible
impossible
impossible
possible
1 #include <cstdio>
2 #include <cstdlib>
3 #include <queue>
4 #include <iostream>
5 #include <memory.h>
6 #define maxn 1005
7 #define maxm 10005
8 using namespace std;
9
10 int first[maxn], work[maxn], deg[maxn], d[maxn], M, N, T, top, S, num, full;
11 int min(int x, int y) {return x < y ? x : y;}
12 struct edge
13 {
14 int v, f, next;
15 }edge[maxm];
16
17 void addedge(int u, int v, int f)
18 {
19 edge[top].v = v;
20 edge[top].f = f;
21 edge[top].next = first[u];
22 first[u] = top++;
23 }
24
25 void add(int u, int v, int f)
26 {
27 addedge(u, v, f);
28 addedge(v, u, 0);
29 }
30
31 bool BFS()
32 {
33 for (int i = 0; i < maxn; i++) d[i] = (i == S) ? 0 : -1;
34 queue<int> q;
35 q.push(S);
36 while (!q.empty())
37 {
38 int u = q.front(); q.pop();
39 for (int e = first[u]; e != -1; e = edge[e].next)
40 {
41 int v = edge[e].v;
42 if (d[v] == -1 && edge[e].f)
43 {
44 d[v] = d[u] + 1;
45 q.push(v);
46 if (v == T)
47 return true;
48 }
49 }
50 }
51 return false;
52 }
53
54 int DFS(int u, int f)
55 {
56 if (u == T || f == 0)
57 return f;
58 int ans = 0;
59 for (int &e = work[u]; e != -1; e = edge[e].next)
60 {
61 int v = edge[e].v, flow;
62 if (d[v] == d[u] + 1 && (flow = DFS(v, min(f, edge[e].f))))
63 {
64 edge[e].f -= flow;
65 edge[e ^ 1].f += flow;
66 ans += flow;
67 f -= flow;
68 if (f == 0)
69 break;
70 }
71 }
72 return ans;
73 }
74
75 int Dinic()
76 {
77 int ans = 0;
78 while (BFS())
79 {
80 memcpy(work, first, sizeof(first));
81 ans += DFS(S, 2100000000);
82 }
83 return ans;
84 }
85
86 bool input()
87 {
88 top = 0;
89 full = 0;
90 memset(first, -1, sizeof(first));
91 memset(deg, 0, sizeof(deg));
92 cin >> N >> M;
93 S = 0;
94 T = 2 * N + 1;
95 for (int k = 0; k < M; k++)
96 {
97 int a, b, c;
98 cin >> a >> b >> c;
99 deg[a]++;
100 deg[b]--;
101 if (c == 0)
102 add(a, b, 1);
103 }
104 for (int i = 1; i <= N; i++)
105 if (deg[i] % 2 == 1)
106 return false;
107 else
108 if (deg[i] > 0)
109 {
110 add(S, i, deg[i] / 2);
111 full += deg[i] / 2;
112 }
113 else
114 if (deg[i] < 0)
115 add(i, T, -deg[i] / 2);
116 return true;
117 }
118
119 int main()
120 {
121 cin >> num;
122 while (num--)
123 {
124 if (input())
125 if (Dinic() == full)
126 cout << "possible" << endl;
127 else
128 cout << "impossible" << endl;
129 else
130 cout << "impossible" << endl;
131 }
132 return 0;
133 }
134
中间的Dinic算法也是套的模板