kuangbin把这道题的难度设置为 crazy …… 搞得我都不太敢刷……
题意：
混合图中欧拉回路的判定
思路：
这道题是真的不好想，最后还是去看了题解，因为比较典型 好吧是我菜
混合图欧拉回路无法用普通的定理去判定，不行可以试试……网络流建模给出的思想是将无向边任意转化成有向边，再去通过变换无向边的方向来实现欧拉回路。
建图方式：
- 对无向边建立你所设定的方向，容量为1
- 对于每个点，如果入度与出度差的绝对值为奇数，则不存在欧拉回路。 （ 因为反转一条边，则两个点的入度出度差各自变化 2 ）
- 否则 ，对于每个点如果 入度>出度 则为 汇点，与超级汇点容量为 ( 入度 – 出度 ) / 2 ，反之则为源点，与超级源点容量为 ( 出度 – 入度 ) / 2 。
跑一遍dinic即可。
残余网络中流量不为0的边即为反转边。这样求出欧拉路径也不算什么难事了。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;
const int maxn = 410;
const int inf = 0x3f3f3f3f;
int n, m, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
int indegree[maxn], outdegree[maxn], subdegree[maxn];
struct node {
int flow;
int to;
int nxt;
} edges[20005];
void addEdge(int u, int v, int f)
{
edges[idx].to = v;
edges[idx].flow = f;
edges[idx].nxt = head[u];
head[u] = idx++;
edges[idx].to = u;
edges[idx].flow = 0;
edges[idx].nxt = head[v];
head[v] = idx++;
}
bool bfs()
{
memset(level, -1, sizeof level);
que[0] = st;
level[st] = 0;
int l = 0, r = 1, u;
while (l < r) {
u = que[l++];
for (int id = head[u]; ~id; id = edges[id].nxt) {
int v = edges[id].to;
if (edges[id].flow && level[v] == -1) {
level[v] = level[u] + 1;
que[r++] = v;
}
}
}
return level[en] != -1;
}
int dfs(int u, int low)
{
int cflow;
if (u == en)
return low;
for (int& id = cur[u]; ~id; id = edges[id].nxt) {
int v = edges[id].to;
if (edges[id].flow > 0 && level[v] == level[u] + 1
&& (cflow = dfs(v, min(low, edges[id].flow)))) {
edges[id].flow -= cflow;
edges[id ^ 1].flow += cflow;
return cflow;
}
}
return 0;
}
int dinic()
{
int ans = 0, cflow;
while (bfs()) {
for (int i = 0; i <= 2 * n; i++)
cur[i] = head[i];
while ((cflow = dfs(st, inf)))
ans += cflow;
}
return ans;
}
int main()
{
int T, u, v, op;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
memset(head, -1, sizeof head);
memset(indegree, 0, sizeof indegree);
memset(outdegree, 0, sizeof outdegree);
idx = 0;
st = 0, en = n + 1;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &op);
if (u == v)
continue;
outdegree[u]++;
indegree[v]++;
if (!op)
addEdge(u, v, 1);
}
bool flag = true;
int sum = 0;
for (int i = 1; i <= n; i++) {
if (outdegree[i] > indegree[i]) {
if ((outdegree[i] - indegree[i]) & 1) {
flag = false;
break;
} else {
addEdge(0, i, (outdegree[i] - indegree[i]) / 2);
sum += (outdegree[i] - indegree[i]);
}
} else if (outdegree[i] < indegree[i]) {
if ((indegree[i] - outdegree[i]) & 1) {
flag = false;
break;
} else
addEdge(i, n + 1, (indegree[i] - outdegree[i]) / 2);
}
}
if (!flag)
puts("impossible");
else {
if (dinic() == sum / 2)
puts("possible");
else
puts("impossible");
}
}
return 0;
}