1. 题目

传送门=￣ω￣=

题目大意：

给定一张混合图（就是有的边是无向边有的边是有向边），若这个混合图存在欧拉回路则输出”possible”，若不存在则输出”impossible”。

点数在 $200$以内，边数在 $1000$以内。

2. 题解

emmm…

对于一个混合图来说，若它存在欧拉回路，那么一定可以把它的一些无向边变成有向边使得这个新的无向图包含和混合图完全相同的欧拉回路。

于是很容易想出暴力做法：枚举每条无向边的方向。

复杂度 $O(TLE)$

然后我们可以考虑用随机化，随机指定无向边的方向。

复杂度依然 $O(TLE)$

想一想暴力的检测答案是否正确的方法：

每个点的出度=入度

emmm…

我也很好奇那些 Dalao 是怎么把上面两点想到最大流上的。

正解是：

首先随机指定无向边的方向

这样很可能会有点的入度不等于出度。

此时如果我们改变一条与它相连的无向边的方向，那么它的入度与出度之差会改变 2（其中一个+1，另一个-1）

所以如果存在某个点入度出度之差为奇数，那一定无法调整边使得它的入度等于出度，这样欧拉路径一定不存在。

如果不存在上面那样的点。。。

若某点入度为 $a$，出度为 $b$，设 $|a-b|=c$

那么我们需要更改 $c\div 2$条无向边的方向使得该点入度等于出度。

我们把点分成两类，一类是入度大于出度，一类是出度大于入度。

1. 对于出度大于入度的，从源点连一条容量为 $c\div 2$的边。
2. 对于入度大于出度的，从它连一条容量为 $c\div 2$的边到汇点。
3. 对于一条随机成 $a->b$的无向边，从 $a$连一条容量为 1 的边到 $b$。

跑最大流，如果从源点出发的所有边都满流则存在欧拉回路，否则不存在。

怎么理解呢？

可以把上面 3. 中的一条边看成一次 “反悔机会”。

另外对于一个点，若它到源点/汇点的边满流了，则说明它的出入度通过一些反悔弄得 “相同” 了。若有未满流的，则说明有的点入度始终无法等于出度，就不存在欧拉回路了。

至于为什么只要检查与源点相连的边是否满流——这是因为有向图中所有点的入度之和必定等于出度之和。所以如果源点满流了汇点也一定满流。反之亦然。

因此我们就能愉♂快地写代码了：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <queue>
#include <algorithm>
#include <cmath>

#define NS (205)
#define MS (3005)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct graph
{
    int head[NS], nxt[MS], to[MS], f[MS], sz;
    void init() {memset(head, -1, sizeof(head)), sz = 0;}
    graph() {init();}
    void push(int a, int b, int c)
    {
        nxt[sz] = head[a], to[sz] = b, f[sz] = c, head[a] = sz++;
    }
    void add(int a, int b, int c)
    {
        push(a, b, c), push(b, a, 0);
    }
    int operator [] (const int a) const {return to[a];}
} g;

int Ca, n, m, T, in[NS], ou[NS], cur[MS], rem, dep[NS];

queue<int> que;

bool bfs()
{
    memset(dep, 0, sizeof(dep)), dep[0] = 1, que.push(0);
    while (!que.empty())
    {
        int F = que.front(); que.pop();
        for (int i = g.head[F]; ~i; i = g.nxt[i])
            if (g.f[i] && !dep[g[i]])
                dep[g[i]] = dep[F] + 1, que.push(g[i]);
    }
    return (dep[T] != 0);
}

int dfs(int a, int f)
{
    if (a == T) return f;
    for (int& i = cur[a]; ~i; i = g.nxt[i])
        if (dep[g[i]] == dep[a] + 1 && g.f[i])
        {
            int tmp = dfs(g[i], min(f, g.f[i]));
            if (tmp)
            {
                g.f[i] -= tmp, g.f[i ^ 1] += tmp;
                return tmp;
            }
        }
    return 0;
}

int main(int argc, char const* argv[])
{
    IN(Ca);
    while (Ca--)
    {
        IN(n), IN(m), srand(n * m), T = n + 1;
        for (int i = 1, a, b, c; i <= m; i += 1)
            if (IN(a), IN(b), IN(c), c == 1) ou[a]++, in[b]++;
            else if (rand() & 1) ou[a]++, in[b]++, g.add(a, b, 1);
            else ou[b]++, in[a]++, g.add(b, a, 1);
        for (int i = 1; i <= n; i += 1)
        {
            if (abs(in[i] - ou[i]) & 1) {puts("impossible"); goto end;}
            if (in[i] > ou[i]) g.add(i, T, (in[i] - ou[i]) >> 1);
            else g.add(0, i, (ou[i] - in[i]) >> 1), rem += (ou[i] - in[i]) >> 1;
        }
        while (bfs())
        {
            memmove(cur, g.head, sizeof(cur));
            int tmp;
            while (tmp = dfs(0, 1e8)) rem -= tmp;
        }
        if (!rem) puts("possible");
        else puts("impossible");
        end : g.init(), rem = 0;
        memset(in, 0, sizeof(in)), memset(ou, 0, sizeof(ou));
    }
    return 0;
}