题意：
给你一些字符串，有的字符串反过来也有意义，题目问给的这n个字符串是否可以首尾相连，组成一个串。
思路：
算是混合欧拉的基础题目了，混合欧拉就是专门处理这类问题的，先说下混合欧拉的大体步骤。
（1） 判断整个图是否连通，如果不连通直接不行（方法随意，并查集搜索什么的都行）
（2） 看度数差为奇数的有多少个，只能有0个或者两个，其他的都不行。
（3） 如果度数差有奇数的有两个，那么一定一个是正的v1，一个是负的v2，add(v1 ,v2 ,1);
（4） 如果方向随意的边，那么我们随意建立一条就行add(a ,b ,1),方向固定的不用管
（5） 虚拟超级远点s，超级汇点e，然后所有度数为负数的add(s ,i ,-du[i]/2),所有为 正的add(i ,e ,du[i]/2);
（6） 最后一遍最大流，看是否满流，如果满流，那么就是有解，否则无解。
至于为什么费用留可以这样求，等比赛回来再来详细补充这个问题。
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 30
#define N_edge 10000
#define INF 100000000
using namespace std;
typedef struct
{
int to ,next ,cost;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int du[N_node] ,deep[N_node];
int mer[N_node];
void add(int a, int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
int minn(int x ,int y)
{
return x < y ? x : y;
}
int finds(int x)
{
return x == mer[x] ? x : mer[x] = finds(mer[x]);
}
bool BFS_Deep(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
queue<DEP>q;
xin.x = s ,xin.t = 0;
q.push(xin);
deep[xin.x] = xin.t;
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost) continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
listt[i] = list[i];
return deep[t] != -1;
}
int DFS_Flow(int s ,int t ,int flow)
{
if(s == t) return flow;
int nowflow = 0;
for(int k = listt[s] ;k ;k = E[k].next)
{
int to = E[k].to;
int c = E[k].cost;
listt[s] = k;
if(deep[to] != deep[s] + 1 || !c) continue;
int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
int DINIC(int s ,int t ,int n)
{
int Ans = 0;
while(BFS_Deep(s ,t ,n))
{
Ans =+ DFS_Flow(s ,t ,INF);
}
return Ans;
}
int main ()
{
int n ,i ,j ,a ,b ,c;
int mark[30];
int t ,cas = 1;
char str[30];
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
memset(list ,0 ,sizeof(list)) ,tot = 1;
memset(du ,0 ,sizeof(du));
memset(mark ,0 ,sizeof(mark));
for(i = 1 ;i <= 26 ;i ++) mer[i] = i;
for(i = 1 ;i <= n ;i ++)
{
scanf("%s %d" ,str ,&c);
a = str[0] - 'a' + 1;
b = str[strlen(str)-1] - 'a' + 1;
du[a] -- ,du[b] ++;
mark[a] = mark[b] = 1;
mer[finds(a)] = finds(b);
if(c) add(a ,b ,1);
}
int sum = 0;
for(i = 1 ;i <= 26 && sum <= 2;i ++)
if(finds(i) == i && mark[i]) sum ++;
printf("Case %d: " ,cas ++);
if(sum != 1)
{
puts("Poor boy!");
continue;
}
sum = 0;
int v1 ,v2;
for(i = 1 ;i <= 26 ;i ++)
{
if(du[i] % 2 && du[i] < 0) v1 = i ,sum ++;
if(du[i] % 2 && du[i] > 0) v2 = i ,sum ++;
}
if(sum != 0 && sum != 2)
{
puts("Poor boy!");
continue;
}
if(sum == 2)
{
add(v1 ,v2 ,1);
du[v1] -- ,du[v2] ++;
}
sum = 0;
for(i = 1 ;i <= 26 ;i ++)
{
if(!mark[i]) continue;
if(du[i] < 0) add(0 ,i ,-du[i]/2) ,sum -= du[i]/2;
else add(i ,27 ,du[i]/2);
}
DINIC(0 ,27 ,27) == sum ? puts("Well done!"):puts("Poor boy!");
}
return 0;
}