本文轉(zhuǎn)載至哲學(xué)與程序博客：http://zhexue.sinaapp.com/?p=105
題目來源：ZOJ1992
對(duì)于一個(gè)混合圖，即有有向邊又有無向邊的圖，判斷是否存在一條歐拉回路。
解法（轉(zhuǎn)）：混合圖歐拉回路用的是網(wǎng)絡(luò)流。把該圖的無向邊隨便定向，計(jì)算每個(gè)點(diǎn)的入度和出度。如果有某個(gè)點(diǎn)出入度之差為奇數(shù)，那么肯定不存在歐拉回路。因?yàn)闅W拉回路要求每點(diǎn)入度 = 出度，也就是總度數(shù)為偶數(shù)，存在奇數(shù)度點(diǎn)必不能有歐拉回路?，F(xiàn)在每個(gè)點(diǎn)入度和出度之差均為偶數(shù)。將這個(gè)偶數(shù)除以2，得x。即是說，對(duì)于每一個(gè)點(diǎn)，只要將x條邊反向（入>出就是變?nèi)?，?gt;入就是變出），就能保證出 = 入。如果每個(gè)點(diǎn)都是出 = 入，那么很明顯，該圖就存在歐拉回路?，F(xiàn)在的問題就變成了：該改變哪些邊，可以讓每個(gè)點(diǎn)出 = 入？構(gòu)造網(wǎng)絡(luò)流模型。有向邊不能改變方向，直接刪掉。開始已定向的無向邊，定的是什么向，就把網(wǎng)絡(luò)構(gòu)建成什么樣，邊長容量上限1。另新建s和t。對(duì)于入 > 出的點(diǎn)u，連接邊(u, t)、容量為x，對(duì)于出 > 入的點(diǎn)v，連接邊(s, v)，容量為x（注意對(duì)不同的點(diǎn)x不同。當(dāng)初由于不小心，在這里錯(cuò)了好幾次）。之后，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。查看流值分配，將所有流量非 0（上限是1，流值不是0就是1）的邊反向，就能得到每點(diǎn)入度 = 出度的歐拉圖。由于是滿流，所以每個(gè)入 > 出的點(diǎn)，都有x條邊進(jìn)來，將這些進(jìn)來的邊反向，OK，入 = 出了。對(duì)于出 > 入的點(diǎn)亦然。那么，沒和s、t連接的點(diǎn)怎么辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那么這個(gè)既沒和s也沒和t連接的點(diǎn)，自然早在開始就已經(jīng)滿足入 = 出了。那么在網(wǎng)絡(luò)流過程中，這些點(diǎn)屬于“中間點(diǎn)”。我們知道中間點(diǎn)流量不允許有累積的，這樣，進(jìn)去多少就出來多少，反向之后，自然仍保持平衡。所以，就這樣，混合圖歐拉回路問題，解了。
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 205
#define MAXN N
#define inf 100000000
int map[N][N];
int flow[N][N];
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
else if (!pre[i]&&(j=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
for (i=0;i<n;i++)
if(mat[source][i] > flow[source][i])
return 0;
return 1;
}
int main()
{
int T, degin[N],degout[N], n, m, x, y, z;
int flag;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(degin,0,sizeof(degin));
memset(degout,0,sizeof(degout));
memset(map,0,sizeof(map));
for(int i = 0; i < m; i++){
scanf("%d%d%d",&x,&y,&z);
degout[x]++;
degin[y]++;
if(!z)map[x][y]++;
}
flag = 0;
for(int i = 1; i <= n && !flag; i++){
if((degin[i]+degout[i])%2)flag=1;
if(degin[i] > degout[i])
map[i][n+1] = (degin[i]-degout[i])/2;
else
map[0][i] = (degout[i]-degin[i])/2;
}
if(flag)
printf("impossible\n");
else{
if(max_flow(n+2,map,0,n+1,flow))
printf("possible\n");
else
printf("impossible\n");
}
}
return 0;
}