HS BDC

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2014-2-3 15:00:40
  4 File Name     :E:\2014ACM\专题学习\图论\欧拉路\混合图\HDU3472.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 
 21 const int MAXN = 30;
 22 //最大流部分
 23 const int MAXM = 10000;
 24 const int INF = 0x3f3f3f3f;
 25 struct Edge
 26 {
 27     int to,next,cap,flow;
 28 }edge[MAXM];
 29 int tol;
 30 int head[MAXN];
 31 int gap[MAXN], dep[MAXN], pre[MAXN], cur[MAXN];
 32 void init()
 33 {
 34     tol = 0;
 35     memset(head,-1,sizeof(head));
 36 }
 37 void addedge(int u,int v,int w,int rw = 0)
 38 {
 39     edge[tol].to = v;
 40     edge[tol].cap = w;
 41     edge[tol].next = head[u];
 42     edge[tol].flow = 0;
 43     head[u] = tol++;
 44     edge[tol].to = u;
 45     edge[tol].cap = rw;
 46     edge[tol].next = head[v];
 47     edge[tol].flow = 0;
 48     head[v] = tol++;
 49 }
 50 int sap(int start,int end,int N)
 51 {
 52     memset(gap,0,sizeof(gap));
 53     memset(dep,0,sizeof(dep));
 54     memcpy(cur,head,sizeof(head));
 55     int u = start;
 56     pre[u] = -1;
 57     gap[0] = N;
 58     int ans = 0;
 59     while(dep[start] < N)
 60     {
 61         if(u == end)
 62         {
 63             int Min = INF;
 64             for(int i = pre[u];i != -1;i = pre[edge[i^1].to])
 65                 if(Min > edge[i].cap - edge[i].flow)
 66                     Min = edge[i].cap - edge[i].flow;
 67             for(int i = pre[u]; i != -1;i = pre[edge[i^1].to])
 68             {
 69                 edge[i].flow += Min;
 70                 edge[i^1].flow -= Min;
 71             }
 72             u = start;
 73             ans += Min;
 74             continue;
 75         }
 76         bool flag = false;
 77         int v;
 78         for(int i = cur[u]; i != -1;i = edge[i].next)
 79         {
 80             v = edge[i].to;
 81             if(edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u])
 82             {
 83                 flag = true;
 84                 cur[u] = pre[v] = i;
 85                 break;
 86             }
 87         }
 88         if(flag)
 89         {
 90             u = v;
 91             continue;
 92         }
 93         
 94         int Min = N;
 95         for(int i = head[u];  i != -1;i = edge[i].next)
 96             if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
 97             {
 98                 Min = dep[edge[i].to];
 99                 cur[u] = i;
100             }
101         gap[dep[u]] --;
102         if(!gap[dep[u]])return ans;
103         dep[u] = Min+1;
104         gap[dep[u]]++;
105         if(u != start) u = edge[pre[u]^1].to;
106     }
107     return ans;
108 }
109 
110 int in[30],out[30];
111 int F[30];
112 int find(int x)
113 {
114     if(F[x] == -1)return x;
115     else return F[x] = find(F[x]);
116 }
117 void bing(int u,int v)
118 {
119     int t1 = find(u), t2 = find(v);
120     if(t1 != t2)F[t1] = t2;
121 }
122 char str[100];
123 int main()
124 {
125     //freopen("in.txt","r",stdin);
126     //freopen("out.txt","w",stdout);
127     int T,n;
128     scanf("%d",&T);
129     int iCase = 0;
130     while(T--)
131     {
132         iCase++;
133         scanf("%d",&n);
134         memset(F,-1,sizeof(F));
135         memset(in,0,sizeof(in));
136         memset(out,0,sizeof(out));
137         init();
138         int k;
139         int s = -1;
140         while(n--)
141         {
142             scanf("%s%d",str,&k);
143             int len = strlen(str);
144             int u = str[0] - 'a';
145             int v = str[len-1] - 'a';
146             out[u]++;
147             in[v]++;
148             s = u;
149             if(k == 1)
150                 addedge(u,v,1);
151             bing(u,v);
152         }
153         bool flag = true;
154         int cnt = 0;
155         int s1 = -1, s2 = -1;
156         for(int i = 0;i < 26;i++)
157             if(in[i] || out[i])
158             {
159                 if(find(i) != find(s))
160                 {
161                     flag = false;
162                     break;
163                 }
164                 if((in[i] + out[i])&1)
165                 {
166                     cnt++;
167                     if(s1 == -1)s1 = i;
168                     else s2 = i;
169                 }
170             }
171         if(cnt != 0 && cnt != 2)flag = false;
172         if(!flag)
173         {
174             printf("Case %d: Poor boy!\n",iCase);
175             continue;
176         }
177         if(cnt == 2)
178         {
179             out[s1]++;
180             in[s2]++;
181             addedge(s1,s2,1);
182         }
183         for(int i = 0;i < 26;i++)
184         {
185             if(out[i] - in[i] > 0)
186                 addedge(26,i,(out[i] - in[i])/2);
187             else if(in[i] - out[i] > 0)
188                 addedge(i,27,(in[i] - out[i])/2);
189         }
190         sap(26,27,28);
191         for(int i = head[26];i != -1;i = edge[i].next)
192             if(edge[i].cap > 0 && edge[i].cap > edge[i].flow)
193             {
194                 flag = false;
195                 break;
196             }
197         if(flag)printf("Case %d: Well done!\n",iCase);
198         else printf("Case %d: Poor boy!\n",iCase);
199     }
200     return 0;
201 }