基礎知識
歐拉回路是圖G中的一個回路，經過每條邊有且僅一次，稱該回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖，簡稱E圖。
無向圖中存在歐拉回路的條件：每個點的度數均為偶數。
有向圖中存在歐拉回路的條件：每個點的入度=出度。
歐拉路徑比歐拉回路要求少一點：
無向圖中存在歐拉路徑的條件：每個點的度數均為偶數或者有且僅有2個度數為奇數的點。
有向圖中存在歐拉路徑的條件：除了2個點外，其餘的點入度=出度，且在這2個點中，一個點的入度比出度大1，另一個出度比入度大1。
歐拉路徑的輸出：經典的套圈算法。
下面來重點講講混合圖的歐拉回路問題。
混合圖就是邊集中有有向邊和無向邊同時存在。這時候需要用網絡流模組化求解。
模組化：
把該圖的無向邊随便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數，那麼肯定不存在歐拉回路。 因為歐拉回路要求每點入度 = 出度，也就是總度數為偶數，存在奇數度點必不能有歐拉回路。
好了，現在每個點入度和出度之差均為偶數。那麼将這個偶數除以2，得x。也就是說，對于每一個點，隻要将x條邊改變方向（入>出就是變入，出>入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那麼很明顯，該圖就存在歐拉回路。
現在的問題就變成了：我該改變哪些邊，可以讓每個點出 = 入？構造網絡流模型。
首先，有向邊是不能改變方向的，要之無用，删。一開始不是把無向邊定向了嗎？定的是什麼向，就把網絡建構成什麼樣，邊長容量上限1。另建立s和t。對于入 > 出的點u，連接配接邊(u, t)、容量為x，對于出 > 入的點v，連接配接邊(s, v)，容量為x（注意對不同的點x不同）。
之後，察看從S發出的所有邊是否滿流。有就是能有歐拉回路，沒有就是沒有。歐拉回路是哪個？察看流值配置設定，将所有流量非 0（上限是1，流值不是0就是1）的邊反向，就能得到每點入度 = 出度的歐拉圖。
由于是滿流，是以每個入 > 出的點，都有x條邊進來，将這些進來的邊反向，OK，入 = 出了。對于出 > 入的點亦然。那麼，沒和s、t連接配接的點怎麼辦？和s連接配接的條件是出 > 入，和t連接配接的條件是入 > 出，那麼這個既沒和s也沒和t連接配接的點，自然早在開始就已經滿足入 = 出了。那麼在網絡流過程中，這些點屬于“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之後，自然仍保持平衡。
是以，就這樣，混合圖歐拉回路問題，解了。
例：HDU3472
題意：給出一些單詞，其中有些單詞反轉之後也是有意義的單詞，問是否能将所有單詞首尾相連，每個單詞用1次且僅用1次。
解：這題是混合路的歐拉路徑問題。
1.首先判斷圖的連通性，若不連通，無解。
2.然後任意定向無向邊，計算每個點i的入度和出度之差deg[i]。若deg[i]為奇數，無解。
3.設立源點s和彙點t，若某點i入度<出度，連邊(s,i,-deg[i]/2)，若入度>出度，連邊(i,t,deg[i]/2)；對于任意定向的無向邊(i,j,1)。
4.若有兩個度數為奇數的點，假設存在歐拉路徑，添加一條容量為1的邊，構成歐拉回路，不影響結果。若全為偶數，直接最大流。
5.若從S發出的邊全部滿流，證明存在歐拉回路(路徑)，否則不存在。
ps：若要求輸出路徑，将網絡中有(無)流量的邊反向，加上原圖的有向邊，用套圈算法即可。
/*
混合圖的歐拉回路
模組化：将有向邊删除，給無向邊任意定向，計算每個點的入度與出入之差，若為奇數，肯定無解；
若為偶數，若圖中存在邊(i,j)，那麼設容量為1；對于每個點i，若deg[i]<0，從s連邊道i，容量為-deg[i]/2，若>0，連邊(i,t,deg[i]/2)
求最大流，如果所有從s出發的弧都滿載，則存在歐拉回路，否則不存在。
把圖中所有有(無)流量的弧都反向，把原圖中的有向邊加上，就構成了一個歐拉回路。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int maxv = 30;
const int maxe = 5000;
int n;
struct Edge
{
int v;
int next;
int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
int deg[30];
bool used[30];
int p[30],rank[30];
void addEdge(int a,int b,int c)
{
e[edgeNum].v = b;
e[edgeNum].flow = c;
e[edgeNum].next = head[a];
head[a] = edgeNum++;
e[edgeNum].v = a;
e[edgeNum].flow = 0;
e[edgeNum].next = head[b];
head[b] = edgeNum++;
}
void Init()
{
edgeNum = 0;
memset(head,-1,sizeof(head));
memset(d,0,sizeof(d));
}
int sap(int s,int t,int n) //源點，彙點，結點總數
{
int i,x,y;
int f,ans = 0;
for(i = 0; i < n; i++)
now[i] = head[i];
vh[0] = n;
x = s;
while(d[s] < n)
{
for(i = now[x]; i != -1; i = e[i].next)
if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
break;
if(i != -1)
{
now[x] = preh[y] = i;
pre[y] = x;
if((x=y) == t)
{
for(f = INF,i=t; i != s; i = pre[i])
if(e[preh[i]].flow < f)
f = e[preh[i]].flow;
ans += f;
do
{
e[preh[x]].flow -= f;
e[preh[x]^1].flow += f;
x = pre[x];
}while(x!=s);
}
}
else
{
if(!--vh[d[x]])
break;
d[x] = n;
for(i=now[x]=head[x]; i != -1; i = e[i].next)
{
if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
{
now[x] = i;
d[x] = d[e[i].v] + 1;
}
}
++vh[d[x]];
if(x != s)
x = pre[x];
}
}
return ans;
}
void makeSet()
{
for(int i = 0; i < 26; i++)
{
p[i] = i;
rank[i] = 0;
}
}
int findSet(int x)
{
if(x != p[x])
p[x] = findSet(p[x]);
return p[x];
}
void Union(int x, int y)
{
x = findSet(x);
y = findSet(y);
if(x == y)
return;
if(rank[x] > rank[y])
p[y] = x;
else
{
p[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
}
int main()
{
int i,j,k;
int t,T;
char wd[22];
scanf("%d",&T);
for(t = 1; t <= T; t++)
{
scanf("%d",&n);
Init();
makeSet();
memset(deg,0,sizeof(deg));
memset(used,0,sizeof(used));
bool flag = true;
for(i = 1; i <= n; i++)
{
scanf("%s %d",wd,&k);
int len = strlen(wd);
int a = wd[0]-'a';
int b = wd[len-1]-'a';
used[a] = true;
used[b] = true;
deg[a]--;
deg[b]++;
if(k == 1)
addEdge(a,b,1);
Union(a,b);
}
int start = 26;
int end = 27;
for(i = 0; i < 26 && flag; i++) //連通性
{
for(j = i+1; j < 26 && flag; j++)
{
if(used[i] && used[j] && findSet(i)!=findSet(j))
flag = false;
}
}
int tmpt = 0;
int v1=-1,v2=-1;
for(i = 0; i < 26 && flag; i++) //度數為奇數的點為0個或者2個
{
if(deg[i]%2 == 1 || deg[i]%2 == -1)
{
tmpt++;
if(deg[i] < 0) //起點
v1 = i;
if(deg[i] > 0) //終點
v2 = i;
}
}
if(tmpt==0 || (tmpt==2&&v1!=-1&&v2!=-1))
{
if(tmpt == 2)
addEdge(v2,v1,1);
}
else
flag = false;
int sum = 0;
for(i = 0; i < 26 && flag; i++)
{
if(deg[i] < 0)
{
addEdge(start,i,-deg[i]/2);
sum += -deg[i]/2;
}
else
addEdge(i,end,deg[i]/2);
}
if(!flag || sum != sap(start,end,end+1))
printf("Case %d: Poor boy!\n",t);
else
printf("Case %d: Well done!\n",t);
}
return 0;
}