題意：給出一個混合圖（有的邊有向，有的邊無向），問此圖是否存在歐拉回路。
先說說歐拉回路吧，起點和終點相同，經過圖G的每條邊一次，且只經過一次的路徑稱為歐拉回路。
按照圖的不同分為：無向圖歐拉回路、有向圖歐拉回路和混合圖歐拉回路。
判斷一個圖是否存在歐拉回路：
1.無向圖：圖連通，且圖中均為偶度頂點。
2.有向圖：圖連通，且圖中所有頂點出入度相等。
3.混合圖：混合圖歐拉回路的判斷是用網絡流，實現方法：
首先對所有的無向邊隨便定向，之後會進行調整。然後統計每個點的出入度，如果有某個點出入度之差為奇數，則不存在歐拉回路，因為相差為奇數的話，無論如果調整邊，都不能使得每個點的出入度相等。
現在每個點的出入度之差為偶數了，把這個偶數除以2,得x。則對每個頂點改變與之相連的x條邊的方向就可以使得該點出入度相等。如果每個點都能達到出入度相等，自然就存在歐拉回路了。
現在問題就變成了改變哪些邊的方向能讓每個點出入度相等了，構造網絡流模型。
有向邊不能改變方向，所以不添加有向邊。對於在開始的時候任意定向的無向邊，按所定的方向加邊，容量為1。源點向所有出>入的點連邊，容量為該點的x值；所有入>出的點向匯點連邊，容量為該點的x值。
建圖完成了，求解最大流，如果能滿流分配，則存在歐拉回路。那麼哪些邊改變方向才能得到歐拉回路呢？查看流量分配，所有流量非0的邊就是要改變方向的邊。
原理是因為滿流分配，所以和源點相連的點一定都有x條邊流入，將這些邊反向這些點就出入度相等了，和匯點相連的亦然。沒有和源、匯相連的已經出入度相等了，當然不用修改，至此歐拉回路求解完畢。
我個人的理解： 首先 上面紅色的 是由於 在歐拉回路中每個點的出度都等於入度。 那麼當一個點的出度增加1 那麼入度一定減少1 那麼他們的差依舊保持為偶數 如果不是 說明這個圖不會是歐拉回路
我們把無向邊隨意變成有向邊後 會存在有些點的入度不等於出度 ，那麼我們需要改變以前的那些無向邊中的部分邊 使得每個點都能夠出度等於入度。
如何修改那 ？ 按照上面的方式連接各個邊之後 形成的圖的意思 就是： 從s到所有邊中找出部分邊修改使得與s相連的每個點的入度等於出度 同時使得與t相連的每個點的出度等於入度
DINIC算法
#include <stdio.h>
#include <string.h>
#define VM 222
#define EM 20550
#define inf 0x3f3f3f3f
struct Edge
{
int frm,to,cap,next;
}edge[EM];
int head[VM],dep[VM],ep; //dep為點的層次
void addedge (int cu,int cv,int cw) //第一條邊下標必須為偶數
{
edge[ep].frm = cu;
edge[ep].to = cv;
edge[ep].cap = cw;
edge[ep].next = head[cu];
head[cu] = ep;
ep ++;
edge[ep].frm = cv;
edge[ep].to = cu;
edge[ep].cap = 0;
edge[ep].next = head[cv];
head[cv] = ep;
ep ++;
}
int BFS (int src,int des) //求出層次圖
{
int que[VM],i,front = 0,rear = 0;
memset (dep,-1,sizeof(dep));
que[rear++] = src;
dep[src] = 0;
while (front != rear)
{
int u = que[front++];
front = front%VM;
for (i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap > 0&&dep[v] == -1) //容量大於0&&未在dep中
{
dep[v] = dep[u] + 1; //建立層次圖
que[rear ++] = v;
rear = rear % VM;
if (v == des) //找到匯點 返回
return 1;
}
}
}
return 0;
}
int dinic (int src,int des)
{
int i,res = 0,top;
int stack[VM]; //stack為棧，存儲當前增廣路
int cur[VM]; //存儲當前點的後繼 跟head是一樣的
while (BFS(src,des)) //if BFS找到增廣路
{
memcpy (cur,head,sizeof (head));
int u = src; //u為當前結點
top = 0;
while (1)
{
if (u == des) //增廣路已全部進棧
{
int min = inf,loc ;
for (i = 0;i < top;i ++) //找最小的增廣跟並loc記錄其在stack中位置
if (min > edge[stack[i]].cap) //以便退回該邊繼續DFS
{
min = edge[stack[i]].cap;
loc = i;
}
for (i = 0;i < top;i ++) //偶數^1 相當加1 奇數^1相當減1 當正向邊 = 0&&路徑不合適時，正加負減
{ //偶數是正向邊，奇數是負向邊，邊從0開始
edge[stack[i]].cap -= min;
edge[stack[i]^1].cap += min;
} //將增廣路中的所有邊修改
res += min;
top = loc;
u = edge[stack[top]].frm; //當前結點修改為最小邊的起點
}
for (i = cur[u];i != -1;cur[u] = i = edge[i].next) //找到當前結點對應的下一條邊
if (edge[i].cap != 0&&dep[u] + 1 == dep[edge[i].to])//不滿足條件時，修改cur值（去掉不合適的占）eg：1-->2 1-->3 1-->4 有邊 但只有
break; // 1-->4 這條邊滿足條件 就把1到2、3的邊給去掉
if (cur[u] != -1) //當前結點的下一條邊存在
{
stack[top ++] = cur[u]; //把該邊放入棧中
u = edge[cur[u]].to; //再從下個點開始找
}
else
{
if (top == 0) //當前結點無未遍歷的下一條邊且棧空，DFS找不到下一條增廣路
break;
dep[u] = -1; //當前結點不在增廣路中，剔除該點
u = edge[stack[--top]].frm; //退棧 回朔，繼續查找
}
}
}
return res;
}
int in[VM],out[VM];
int abs(int qa)
{
if(qa>0) return qa;
return -qa;
}
int main()
{
int T,n,m;
int u,v,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
ep=0;
memset (head,-1,sizeof(head));
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
while(m--)
{
scanf("%d%d%d",&u,&v,&d);
if(u == v)
continue;
out[u]++;
in[v]++;
if(!d)
{
addedge(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])
{
addedge(0,i,(out[i]-in[i])/2);
sum += (out[i]-in[i])/2;
}
else
{
addedge(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;
}
#include <stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 210
#define INFINITY 1000000000
struct edge
{
int cap;
int flow;
int ver;
edge *next;
edge *rev;
};
edge edges[2500];
edge *link[MAX+1];
int dist[MAX +1];
int h[MAX + 1];
int in[MAX+1];
int out[MAX+1];
int num;
int total_flow;
int min(int a, int b)
{
return a < b ? a : b;
};
void addedge(int start, int end, int c)
{
num++;
edges[num].ver = end;
edges[num].cap = c;
edges[num].next = link[start];
link[start] = edges + num;
num++;
edges[num].ver = start;
edges[num].cap = 0;
edges[num].next = link[end];
link[end] = edges + num;
link[start]->rev = link[end];
link[end]->rev = link[start];
}
void rev_bfs(int n, int src, int des)
{
int q[MAX + 1];
int head = 0;
int tail = 0;
for(int i = 1; i <= n; i++)
{
dist[i] = MAX;
h[i] = 0;
}
q[tail++] = des;
dist[des] = 0;
h[0] = 1;
int p;
while(tail != head)
{
p = q[head++];
for(edge *e = link[p]; e; e = e->next)
{
if(dist[e->ver] != MAX || e->rev->cap == 0)
continue;
dist[e->ver] = dist[p] + 1;
h[dist[e->ver]]++;
q[tail++] = e->ver;
}
}
}
int sap(int n, int src, int des)
{
rev_bfs(n, src, des);
edge *cur_edges[MAX+1];
edge *rev_path[MAX+1];
total_flow = 0;
int i;
for(i = 1; i <= n ; i++)
cur_edges[i] = link[i];
int argu_flow = INFINITY;
int u = src;
while(dist[src] < n)
{
if(u == des)
{
for(i = src; i != des; i = cur_edges[i]->ver)
argu_flow = min(argu_flow, cur_edges[i]->cap);
for(i = src; i != des ; i = cur_edges[i]->ver)
{
cur_edges[i]->cap -= argu_flow;
cur_edges[i]->rev->cap += argu_flow;
cur_edges[i]->flow += argu_flow;
cur_edges[i]->rev->flow -= argu_flow;
}
total_flow += argu_flow;
u = src;
}
edge *e;
for(e = cur_edges[u]; e; e = e->next)
if(e->cap > 0 && dist[u] == dist[e->ver] + 1)
break;
if(e)
{
cur_edges[u] = e;
rev_path[e->ver] = e->rev;
u = e->ver;
}
else
{
if(--h[dist[u]] == 0)
break;
cur_edges[u] = link[u];
int mini_dist = n;
for(edge *e = link[u]; e; e = e->next)
if(e->cap > 0)
mini_dist = min(mini_dist, dist[e->ver]);
dist[u] = mini_dist + 1;
h[dist[u]]++;
if(u != src)
u = rev_path[u]->ver;
}
}
return total_flow;
}
int main()
{
int T,m,n,src,des;
int u,v,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
num=0;
memset(link, 0, sizeof(link));
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
src=n+1;
des=n+2;
while(m--)
{
scanf("%d%d%d",&u,&v,&d);
if(u == v)
continue;
out[u]++;
in[v]++;
if(!d)
{
addedge(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])
{
addedge(src,i,(out[i]-in[i])/2);
sum += (out[i]-in[i])/2;
}
else
{
addedge(i,des,(in[i]-out[i])/2);
}
}
if(flag)
{
printf("impossible\n");
continue;
}
n=n+2;
int ans=sap(n,src,des);//n是點的個數(n+2個) 點下標從1開始到 n+2(des)
if(sum == ans)
printf("possible\n");
else
printf("impossible\n");
}
return 0;
}
