学步园

               题意:

                       给一堆单词..有的单词是可以反过来的..两个单词能连接exactly前面单词的最后一个字母等于后面一个单词的第一个字母..问能否将所有单词连成一串....

               题解:

                       同样以字母为点,单词为边..把判断哈密顿通路转化成判断欧拉通路...

                       判断混合图是否存在欧拉通路: 无向边任意定向后,看有多少个点入度多了且度为奇数..有多少个点出度多了且度为奇数..若两个数量都为0..或者都为1并且加一条有向边连接两点(入度多了的指向出度多了的)..然后就和混合图欧拉回路一样的判断了...用最大流解决..话说此类问题一定不要忘记判断连通性！！！

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<time.h>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 50
#define MAXM 500005
using namespace std; 
int father[50];
bool used[50];
int getfather(int x)
{
      if (father[x]==x) return x;
      return father[x]=getfather(father[x]);
}
struct Dinic  
{  
      struct node   
      {  
             int x,y,c,next;  
      }line[MAXM];     
      int Lnum,_next[MAXN],dis[MAXN];  
      void initial(int n)   
      {  
             for (int i=0;i<=n;i++) _next[i]=-1;
             Lnum=-1;  
      }   
      void addline(int x,int y,int c)  
      {  
             line[++Lnum].next=_next[x],_next[x]=Lnum;  
             line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c;  
             line[++Lnum].next=_next[y],_next[y]=Lnum;  
             line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0;               
      }  
      bool BFS(int s,int e)  
      {   
             queue<int> Q;  
             while (!Q.empty()) Q.pop();  
             memset(dis,0,sizeof(dis));  
             dis[s]=1;  
             Q.push(s);  
             while (!Q.empty())  
             {  
                   int h,k;  
                   h=Q.front(),Q.pop();  
                   if (h==e) return dis[e];  
                   for (k=_next[h];k!=-1;k=line[k].next)  
                      if (line[k].c && !dis[line[k].y])  
                         dis[line[k].y]=dis[h]+1,Q.push(line[k].y);                   
             }   
             return false;  
      }  
      int dfs(int x,int flow,int e)    
      {       
             if (x==e) return flow;     
             int temp,cost=0;    
             for (int k=_next[x];k!=-1;k=line[k].next)    
             if (line[k].c && dis[line[k].y]==dis[x]+1)    
             {    
                    temp=dfs(line[k].y,min(flow-cost,line[k].c),e);     
                    if (temp)    
                    {    
                           line[k].c-=temp,line[k^1].c+=temp;    
                           cost+=temp;    
                           if (flow==cost) return cost;    
                    }else dis[line[k].y]=-1;    
             }    
             return cost;    
      }    
      int MaxFlow(int s,int e)  
      {  
             int MaxFlow=0;  
             while (BFS(s,e)) MaxFlow+=dfs(s,oo,e);   
             return MaxFlow;  
      }  
}T;   
bool judge(int s,int e,int id,int *d,int n)
{
       if (n==1) return true;
       int i; 
       if (n==1) return true;
       for (i=0;i<26;i++)
         if (used[i] && getfather(i)!=id) return false;
       int sum=0,t1=-1,t2=-1;
       for (i=0;i<26;i++)
          if (d[i]<0) 
          {
                 if (d[i]%2) 
                 {
                       if (t1!=-1) return false;
                       t1=i,d[i]++;
                 }
                 d[i]/=2;
                 T.addline(s,i,-d[i]),sum-=d[i]; 
          }else
          if (d[i]>0) 
          {
                 if (d[i]%2) 
                 {
                       if (t2!=-1) return false;
                       t2=i,d[i]++;
                 }
                 d[i]/=2;
                 T.addline(i,e,d[i]),sum+=d[i];  
          }
       sum/=2;
       if (t1>=0 && t2==-1 || t1==-1 && t2>=0) return false;
       if (T.MaxFlow(s,e)==sum) return true;
                          else  return false; 
}
int main()
{         
       int s,e,C,m,cases,i,n,d[50],x,y,tp; 
       char ss[22];    
       scanf("%d",&C);
       for (cases=1;cases<=C;cases++)
       {
                scanf("%d",&n);
                s=30,e=31;
                T.initial(e);
                memset(d,0,sizeof(d));
                memset(used,false,sizeof(used));
                for (i=0;i<=40;i++) father[i]=i;
                while (n--)
                {
                       scanf("%s%d",ss,&tp);
                       x=ss[0]-'a',y=ss[strlen(ss)-1]-'a';
                       d[x]--,d[y]++;
                       father[getfather(x)]=getfather(y);
                       used[x]=used[y]=true;
                       m=getfather(x);
                       if (tp) T.addline(x,y,1);
                }
                printf("Case %d: ",cases);
                if (judge(s,e,m,d,26)) printf("Well done!\n");
                                 else  printf("Poor boy!\n"); 
       }
       return 0;
}