題目大意：求混合圖歐拉回路。 題目分析：最大流。竟然用網絡流求混合圖的歐拉回路，漲姿勢了啊啊。。 其實仔細一想也是那麼回事。歐拉回路是遍歷所有邊一次又回到起點的回路。雙向圖只要每個點度數為偶數即可，有向圖要保證所有點入度等於出度。求路徑的話，dfs即可。 混合圖的話，就比較復雜。首先將有向邊定向，求出所有點的入度和出度，如果某個點入度和出度之差為奇數，則一定不存在歐拉回路，因為對於混合圖，無向邊可以任意指定方向，但是無論指定哪個方向，如果取反向的話，只會影響端點的一個出度和一個入度，所以無論無向邊如何定向，是不影響節點入度和出度之差的奇偶性的。無向邊定向後轉化成一張有向圖，那麼所有的頂點就分成3類： 1：入度= 出度的點，已經是平衡點了，不管； 2：入度>出度的點，向匯點建一條邊，邊權為(入度- 出度)/2； 3：入度<出度的點，源點與之建一條邊，邊權為(出度- 入度)/2； 這樣跑一遍最大流，看是否為滿流。如果是滿流，就存在歐拉回路。 因為如果跑出來一個滿流，那麼對於每個入度>出度的點，都有x條邊進來，那麼這x條邊反向，那麼該節點入度=出度，平衡了，對於每個出度>入度的點也是同理。對於出度=入度的點，因為建圖的時候沒有管他們，也就是說他們本來就是平衡點，所以源點和匯點與之沒有直接邊，但並不代表這些點就不在圖中，因為非平衡點會與之有邊相連。如果要求一條具體的歐拉回路的話，只要看具體的網絡流，對於流量為1的邊，取反便是歐拉回路中一條邊了。所謂取反只是對無向邊而言的，說明一開始對無向邊定向定反了。 詳情請見代碼：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 205;
const int M = 40000;
const int inf = 0x3f3f3f3f;
int n,m,num,sum;
int head[N],sta[N],que[N],cnt[N],dis[N],rpath[N];
int in[N],out[N];
struct node
{
int to,c,next,pre;
}arc[M];
void build(int s,int e,int cap)
{
arc[num].to = e;
arc[num].c = cap;
arc[num].next = head[s];
head[s] = num ++;
arc[num - 1].pre = num;
arc[num].pre = num - 1;
arc[num].to = s;
arc[num].c = 0;
arc[num].next = head[e];
head[e] = num ++;
}
void init()
{
int i,a,b,d;
scanf("%d%d",&n,&m);
for(i = 1;i <= n;i ++)
in[i] = out[i] = 0;
memset(head,-1,sizeof(head));
num = 0;
while(m --)
{
scanf("%d%d%d",&a,&b,&d);
if(d == 0)
build(a,b,1);
out[a] ++;
in[b] ++;
}
}
void re_Bfs()
{
int i,front,rear;
for(i = 0;i <= n + 1;i ++)
{
dis[i] = n + 2;
cnt[i] = 0;
}
dis[n + 1] = 0;
cnt[0] = 1;
front = rear = 0;
que[rear ++] = n + 1;
while(front != rear)
{
int u = que[front ++];
for(i = head[u];i != -1;i = arc[i].next)
{
if(arc[arc[i].pre].c == 0 || dis[arc[i].to] < n + 2)
continue;
dis[arc[i].to] = dis[u] + 1;
cnt[dis[arc[i].to]] ++;
que[rear ++] = arc[i].to;
}
}
}
int ISAP()
{
re_Bfs();
int i,u,maxflow = 0;
for(i = 0;i <= n + 1;i ++)
sta[i] = head[i];
u = 0;
while(dis[0] < n + 2)
{
if(u == n + 1)
{
int curflow = inf;
for(i = 0;i != n + 1;i = arc[sta[i]].to)
curflow = min(curflow,arc[sta[i]].c);
for(i = 0;i != n + 1;i = arc[sta[i]].to)
{
arc[sta[i]].c -= curflow;
arc[arc[sta[i]].pre].c += curflow;
}
maxflow += curflow;
u = 0;
}
for(i = sta[u];i != -1;i = arc[i].next)
if(arc[i].c > 0 && dis[arc[i].to] + 1 == dis[u])
break;
if(i != -1)
{
sta[u] = i;
rpath[arc[i].to] = arc[i].pre;
u = arc[i].to;
}
else
{
if((-- cnt[dis[u]]) == 0)
break;
int Min = n + 2;
sta[u] = head[u];
for(i = head[u];i != -1;i = arc[i].next)
if(arc[i].c > 0)
Min = min(Min,dis[arc[i].to]);
dis[u] = Min + 1;
cnt[dis[u]] ++;
if(u != 0)
u = arc[rpath[u]].to;
}
}
return maxflow;
}
bool solve()
{
int i;
sum = 0;
for(i = 1;i <= n;i ++)
{
if(in[i] > out[i])
{
if((in[i] - out[i])&1)
return false;
build(i,n + 1,(in[i] - out[i])>>1);
}
if(in[i] < out[i])
{
if((out[i] - in[i])&1)
return false;
build(0,i,(out[i] - in[i])>>1);
sum += (out[i] - in[i])>>1;
}
}
return ISAP() == sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t --)
{
init();
if(solve())
puts("possible");
else
puts("impossible");
}
return 0;
}
//200K 0MS
