1 定義
歐拉通路 (Euler tour)——通過圖中每條邊一次且僅一次，並且過每一頂點的通路。
歐拉回路 (Euler circuit)——通過圖中每條邊一次且僅一次，並且過每一頂點的回路。
歐拉圖——存在歐拉回路的圖。
2 無向圖是否具有歐拉通路或回路的判定
G有歐拉通路的充分必要條件為：G 連通，G中只有兩個奇度頂點(它們分別是歐拉通路的兩個端點)。
G有歐拉回路(G為歐拉圖)：G連通，G中均為偶度頂點。
3 有向圖是否具有歐拉通路或回路的判定
D有歐拉通路：D連通，除兩個頂點外，其余頂點的入度均等於出度，這兩個特殊的頂點中，一個頂點的入度比出度大1，另一個頂點的入度比出度小1。
D有歐拉回路(D為歐拉圖)：D連通，D中所有頂點的入度等於出度。
4 混合圖。混合圖也就是無向圖與有向圖的混合，即圖中的邊既有有向邊也有無向邊。
5 混合圖歐拉回路
混合圖歐拉回路用的是網絡流。
把該圖的無向邊隨便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數，那麼肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度，也就是總度數為偶數，存在奇數度點必不能有歐拉回路。
現在每個點入度和出度之差均為偶數。將這個偶數除以2，得x。即是說，對於每一個點，只要將x條邊反向（入>出就是變入，出>入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那麼很明顯，該圖就存在歐拉回路。
現在的問題就變成了：該改變哪些邊，可以讓每個點出 = 入？構造網絡流模型。有向邊不能改變方向，直接刪掉。開始已定向的無向邊，定的是什麼向，就把網絡構建成什麼樣，邊長容量上限1。另新建s和t。對於入 > 出的點u，連接邊(u, t)、容量為x，對於出 > 入的點v，連接邊(s, v)，容量為x（注意對不同的點x不同。當初由於不小心，在這裡錯了好幾次）。之後，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。查看流值分配，將所有流量非 0（上限是1，流值不是0就是1）的邊反向，就能得到每點入度 = 出度的歐拉圖。
由於是滿流，所以每個入 > 出的點，都有x條邊進來，將這些進來的邊反向，OK，入 = 出了。對於出 > 入的點亦然。那麼，沒和s、t連接的點怎麼辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那麼這個既沒和s也沒和t連接的點，自然早在開始就已經滿足入 = 出了。那麼在網絡流過程中，這些點屬於“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之後，自然仍保持平衡。
所以，就這樣，混合圖歐拉回路問題，解了。
-----------------------------------------------------------------------------------
注意最大流應該等於的是 所有的出度大於入度的點上的x之和
[cpp]
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define MAXN 2222
#define MAXM 222222
#define INF 1000000000
using namespace std;
struct node
{
int ver; // vertex
int cap; // capacity
int flow; // current flow in this arc
int next, rev;
}edge[MAXM];
int dist[MAXN], numbs[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, int c)
{ //e記錄邊的總數
edge[e].ver = y;
edge[e].cap = c;
edge[e].flow = 0;
edge[e].rev = e + 1; //反向邊在edge中的下標位置
edge[e].next = head[x]; //記錄以x為起點的上一條邊在edge中的下標位置
head[x] = e++; //以x為起點的邊的位置
//反向邊
edge[e].ver = x;
edge[e].cap = 0; //反向邊的初始網絡流為0
edge[e].flow = 0;
edge[e].rev = e - 1;
edge[e].next = head[y];
head[y] = e++;
}
void rev_BFS()
{
int Q[MAXN], qhead = 0, qtail = 0;
for(int i = 1; i <= n; ++i)
{
dist[i] = MAXN;
numbs[i] = 0;
}
Q[qtail++] = des;
dist[des] = 0;
numbs[0] = 1;
while(qhead != qtail)
{
int v = Q[qhead++];
for(int i = head[v]; i != -1; i = edge[i].next)
{
if(edge[edge[i].rev].cap == 0 || dist[edge[i].ver] < MAXN)continue;
dist[edge[i].ver] = dist[v] + 1;
++numbs[dist[edge[i].ver]];
Q[qtail++] = edge[i].ver;
}
}
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
}
int maxflow()
{
int u, totalflow = 0;
int Curhead[MAXN], revpath[MAXN];
for(int i = 1; i <= n; ++i)Curhead[i] = head[i];
u = src;
while(dist[src] < n)
{
if(u == des) // find an augmenting path
{
int augflow = INF;
for(int i = src; i != des; i = edge[Curhead[i]].ver)
augflow = min(augflow, edge[Curhead[i]].cap);
for(int i = src; i != des; i = edge[Curhead[i]].ver)
{
edge[Curhead[i]].cap -= augflow;
edge[edge[Curhead[i]].rev].cap += augflow;
edge[Curhead[i]].flow += augflow;
edge[edge[Curhead[i]].rev].flow -= augflow;
}
totalflow += augflow;
u = src;
}
int i;
for(i = Curhead[u]; i != -1; i = edge[i].next)
if(edge[i].cap > 0 && dist[u] == dist[edge[i].ver] + 1)break;
if(i != -1) // find an admissible arc, then Advance
{
Curhead[u] = i;
revpath[edge[i].ver] = edge[i].rev;
u = edge[i].ver;
}
else // no admissible arc, then relabel this vertex
{
if(0 == (--numbs[dist[u]]))break; // GAP cut, Important!
Curhead[u] = head[u];
int mindist = n;
for(int j = head[u]; j != -1; j = edge[j].next)
if(edge[j].cap > 0)mindist = min(mindist, dist[edge[j].ver]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != src)
u = edge[revpath[u]].ver; // Backtrack
}
}
return totalflow;
}
int ind[MAXN], outd[MAXN];
int xx[MAXM], yy[MAXM], cc[MAXM];
int main()
{
int T, m;
scanf("%d", &T);
while(T--)
{
init();
memset(ind, 0, sizeof(ind));
memset(outd, 0, sizeof(outd));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &xx[i], &yy[i], &cc[i]);
ind[yy[i]]++;
outd[xx[i]]++;
}
bool flag = true;
for(int i = 1; i <= n; i++)
if((outd[i] - ind[i]) % 2 != 0)
{
flag = false;
break;
}
if(!flag) {printf("impossible\n"); continue;}
int flow = 0;
for(int i = 1; i <= m; i++)
{
if(xx[i] == yy[i] || cc[i]) continue;
add(xx[i] + 1, yy[i] + 1, 1);
}
src = 1, des = n + 2;
for(int i = 1; i <= n; i++)
{ www.2cto.com
int x = abs(outd[i] - ind[i]) / 2;
if(outd[i] > ind[i]) add(src, i + 1, x), flow += x;
else if(ind[i] > outd[i]) add(i + 1, des, x);
}
n = n + 2;
rev_BFS();
if(maxflow() == flow) printf("possible\n");
else printf("impossible\n");
}
return 0;
}
作者：sdj222555
