題目大意：判定一個混合圖是否是歐拉圖。
過程：開始用EK算法來求解，用鄰接矩陣存貯網絡，但由於有重邊的原因，一直是過不去，最後沒辦法，改用Dinic算法求解。
解題思路：無向邊隨意定向，將混合圖轉為有向圖，利用網絡流求解。
網絡構造思路：在讀入的時候遇到無向邊的時候，將該無向邊隨意定向加入代建網絡中，容量為1。讀入完後，用每個點的入度減去出度得到x，若x為奇數，則肯定不存在歐拉回路。若所點的入度與初度之差（x）都為偶數，則用網絡流解。
x>0，則在源點（s）與該點之間建立一條容量為 x/2 的邊；
x<0，則在該點與匯點（t）之間建立一條容量為 -x/2 的邊；
若該網絡為滿流網絡（最大流 == 與源點相連的邊容量之和），則該混合圖是歐拉圖，否則不是。
代碼：
[cpp]
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXN 205
#define INF 0x7fffffff
struct Node
{
int v;
int cap;
int next;
}node[4050];
int in[MAXN],out[MAXN];
int level[MAXN],head[MAXN];
int que[MAXN];
int tot;
int min(int x,int y)
{
return x < y ? x : y ;
}
void init()
{
tot = 2;
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(head,-1,sizeof(head));
memset(node,'/0',sizeof(node));
}
void add(int s,int t,int cap)
{
node[tot].v=t;
node[tot].cap=cap;
node[tot].next = head[s];
head[s] = tot++;
node[tot].v=s;
node[tot].cap=0;
node[tot].next = head[t];
head[t]=tot++;
}
int BFS(int s,int t)
{
int head1=0,tail=0;
int u;
memset(level,-1,sizeof(level));
que[tail++]=s;
level[s]=0;
while(head1 != tail)
{
u = que[head1];
head1++;
int T=head[u];
while(T!=-1)
{
int v=node[T].v;
int cap=node[T].cap;
if(cap > 0 && level[v] == -1)
{
level[v] = level[u]+1;
que[tail++]=v;
}
T=node[T].next;
}
}
return level[t] != -1;
}
int DFS(int s,int mint,int t)
{
int temp;
if(s == t)
return mint;
int T = head[s];
while(T!=-1)
{
int v=node[T].v;
int cap=node[T].cap;
if(cap > 0 && level[v] == level[s]+1 && (temp = DFS(v,min(cap,mint),t))>0)
{
node[T].cap -= temp;
node[T^1].cap += temp;
return temp;
}
T=node[T].next;
}
return 0;
}
int dinic(int s,int t)
{
int res=0;
while(BFS(s,t))
{
while(1)
{
int a = DFS(s,INF,t);
if(a == 0)
break;
res += a;
}
}
return res;
}
int main()
{
int T,n,m;
int u,v,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
while(m--)
{
scanf("%d%d%d",&u,&v,&d);
if(u == v)
continue;
out[u]++;
in[v]++;
if(!d)
{
add(u,v,1);
}
}
int flag=0;
int sum=0;
for(int i=1;i<=n;i++)
{
if(abs(in[i]-out[i])%2 == 1)
{
flag=1;
break;
}
if(in[i]<out[i])
{
add(0,i,(out[i]-in[i])/2);
sum += (out[i]-in[i])/2;
}
else
{
add(i,n+1,(in[i]-out[i])/2);
}
}
if(flag)
{
printf("impossible\n");
continue;
}
int ans = dinic(0,n+1);
if(sum == ans)
printf("possible\n");
else
printf("impossible\n");
}
return 0;
}
作者：kath_y
