HDU3472 – HS BDC（混合图的欧拉回路）

题目链接：HDU3472

【题意】给出n个单词，求出首尾能否连接成一个串，有些单子可以翻转，每个单词必须且只能用一次；问能否连成一个大串。

【分析】通过这题学习了混合图的欧拉回路；把每个单词的首尾字母看成点，每个单词看成边，当能翻转时是无向图，否则是有向图；其实混合图的欧拉路径就是通过网络流给每个无向边定向。

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：若要求输出路径，将网络中有(无)流量的边反向，加上原图的有向边，用套圈算法即可。

【AC CODE】0ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 30, MAXM = 1000+60+10;
int nxt[MAXM],from[MAXM],to[MAXM],cap[MAXM],tol,head[MAXN];

void add_edge(int u, int v, int c)
{
	nxt[tol] = head[u],from[tol] = u,to[tol] = v,cap[tol] = c;
	head[u] = tol++;
	nxt[tol] = head[v],from[tol] = v,to[tol] = u,cap[tol] = c;
	head[v] = tol++;
}
int d[MAXN],st,ed;
bool bfs()
{
	clc(d,-1);
	queue<int> q;
	q.push(st);
	d[st] = 0;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = head[u]; ~i; i = nxt[i])
		{
			int v = to[i];
			if(-1 == d[v] && cap[i])
			{
				d[v] = d[u]+1;
				q.push(v);
				if(~d[ed]) return true;
			}
		}
	}
	return false;
}
int s[MAXN],top,cur[MAXN];
int maxflow()
{
	int ans = 0;
	while(bfs())
	{
		memcpy(cur,head,sizeof(head));
		int u = st;
		top = 0;
		while(1)
		{
			if(u == ed)
			{
				int flow = INF, loc;
				rep(i,0,top)
				{
					if(flow > cap[s[i]])
					{
						flow = cap[s[i]];
						loc = i;
					}
				}
				rep(i,0,top)
				{
					cap[s[i]] -= flow;
					cap[s[i]^1] += flow;
				}
				ans += flow;
				u = from[s[top=loc]];
			}
			for(int i = cur[u]; ~i; cur[u] = i = nxt[i])
				if(cap[i] && d[u]+1 == d[to[i]]) break;
			if(~cur[u])
			{
				s[top++] = cur[u];
				u = to[cur[u]];
			}
			else
			{
				if(!top) break;
				d[u] = -1;
				u = from[s[--top]];
			}
		}
	}
	return ans;
}
int du[MAXN],f[MAXN];
bool vis[MAXN];
int find(int x){return f[x] == x?x:f[x] = find(f[x]);}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	scanf("%d%*c", &t);
	st = 27,ed = 28;
	while(t--)
	{
		int n;
		scanf("%d%*c", &n);
		clc(head,-1);
		tol = 0;
		clc(du,0);
		clc(vis,0);
		char ch[30];
		rep(i,0,26) f[i] = i;
		int sum = 0,cnt = 1;
		rep(i,0,n)
		{
			int fz;
			scanf("%s %d", ch, &fz);
			int a = ch[0]-'a', b = ch[strlen(ch)-1]-'a';
			du[a]--, du[b]++;
			if(!vis[a]) vis[a] = true,sum++;
			if(!vis[b]) vis[b] = true,sum++;
			int x = find(a), y = find(b);
			if(x != y) f[x] = y, cnt++;
			if(fz)//所有无向图加入网络流判断方向
			{
				add_edge(a,b,1);
			}
		}
		int ji = 0;
		rep(i,0,26)
		{
			if(du[i]&1) ji++;
		}
		printf("Case %d: ",++count);
		if((ji && ji != 2) || cnt != sum)//不是0个或2个点度数是奇数，图不连通
		{
			puts("Poor boy!");
			continue;
		}
		sum = 0;
		if(ji == 2)//有两个点的度数是奇数，加一条边变成欧拉回路
		{
			int a,b;
			rep(i,0,26)
			{
				if(du[i]&1)
				{
					if(du[i] < 0) a = i;
					else if(du[i] > 0) b = i;
				}
			}
			add_edge(a,b,1);
		}
		repe(i,0,26)//把st和入度<出度的边相连，ed和入度>出度的边连，权值都是abs(du[i])/2
		{
			int c = abs(du[i])/2;
			if(du[i] < 0)
			{
				sum += c;
				add_edge(st,i,c);
			}
			else if(du[i] > 0)
			{
				add_edge(i,ed,c);
			}
		}
		int ans = maxflow();
		if(ans == sum) puts("Well done!");
		else puts("Poor boy!");
	}
	return 0;
}