题目大意

　　有一张$n$个结点，$m$条混合边的图（$1 \leq n \leq 200$，$1 \leq m \leq 1000$），求这张图是否存在欧拉回路。

题解

　　因为有混合边，所以我们要先给无向边随机定向，然后再调整方向。

　　随机定向之后，我们就得到一张有向图。

　　我们记录每个结点的入度$ind[i]$和出度$outd[i]$，根据欧拉路的性质可以得到，当$ind[i] + outd[i]$为奇数时，一定不存在欧拉路。

　　对于建边过程，因为原有的有向边不能变向，所以我们可以忽略，只需要将读入的无向边随机定向成有向边即，设容量为$1$即可（每条边只能走一次）。

　　对于每一个$ind[i] \leq outd[i]$的结点$i$，我们都从源点$s$向$i$连一条有向边，容量为$\frac{outd[i] - ind[i]}{2}$；对于$ind[i] > outd[i]$的结点$i$，从$i$向$t$连一条有向边，容量为$\frac{ind[i] - outd[i]}{2}$。这两种边的含义是连接结点$i$的边中，需要变向的边数。

　　显然，我们从$s$开始跑一次最大流，最后判断与$s$或$t$相连的边是否满流即可。

#include
#include
#include
#include

#define MAX_N (200 + 5)
#define MAX_M (1000 + 5)

using namespace std;

struct Edge
{
int to;
int weight;
int next;
};

int T;
int n, m;
int s, t;
int h[MAX_N], tot = ;
Edge e[MAX_N + MAX_M << ]; int ind[MAX_N], outd[MAX_N]; int dep[MAX_N]; int cur[MAX_N]; queue q;
int maxflow;

inline void AddEdge(int u, int v, int w)
{
e[++tot].to = v;
e[tot].weight = w;
e[tot].next = h[u];
h[u] = tot;
return;
};

bool BFS()
{
memset(dep, 0x7f, sizeof dep);
memcpy(cur, h, sizeof cur);
q.push(s);
dep[s] = ;
int u, v, w;
while(!q.empty())
{
u = q.front();
q.pop();
for(int i = h[u]; i; i = e[i].next)
{
v = e[i].to;
w = e[i].weight;
if(dep[v] > dep[u] + && w)
{
dep[v] = dep[u] + ;
q.push(v);
}
}
}
return dep[t] != 0x7f7f7f7f;
}

int DFS(int u, int flow)
{
if(u == t)
{
maxflow += flow;
return flow;
}
int v, w;
int tmp, sum = ;
for(int i = cur[u]; i && flow; i = e[i].next)
{
cur[u] = i;
v = e[i].to;
w = e[i].weight;
if(dep[v] == dep[u] + && w && (tmp = DFS(v, min(flow, w))))
{
e[i].weight -= tmp;
e[i ^ ].weight += tmp;
sum += tmp;
flow -= tmp;
}
}
return sum;
}

void Dinic()
{
while(BFS()) DFS(s, 0x7f7f7f7f);
return;
}

int main()
{
scanf("%d", &T);
while(T--)
{
memset(h, , sizeof h);
memset(ind, , sizeof ind);
memset(outd, , sizeof outd);
tot = ;
maxflow = ;
scanf("%d%d", &n, &m);
s = ;
t = n + ;
int u, v, d;
for(int i = ; i <= m; ++i) { scanf("%d%d%d", &u, &v, &d); ++outd[u]; ++ind[v]; if(!d) { AddEdge(u, v, ); AddEdge(v, u, ); } } bool isEuler = true; for(int i = ; i <= n; ++i) { if(ind[i] + outd[i] & ) { isEuler = false; break; } } if(!isEuler) { printf("impossible\n"); continue; } int tmp = tot; for(int i = ; i <= n; ++i) { if(ind[i] <= outd[i]) { AddEdge(s, i, outd[i] - ind[i] >> );
AddEdge(i, s, );
}
else
{
AddEdge(i, t, ind[i] - outd[i] >> );
AddEdge(t, i, );
}
}
Dinic();
for(int i = tmp + ; i <= tot; i += )
{
if(e[i].weight)
{
isEuler = false;
break;
}
}
if(!isEuler) printf("impossible\n");
else printf("possible\n");
}
return ;
}

参考程序