3.(若存在2个deg[i]为奇数的结点,则在两点连一条流量为1的边,方向任意)设立源点s和汇点t(自己另外定两个点),若某点i入度<出度,连边(s,i,-deg[i]/2),若入度>出度,连边(i,t,deg[i]/2);对于任意定向的无向边(i,j,1)。
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>using namespace std;typedef long long ll;const int INF = 1<<30;const int N = 2010;int _,cas=1, n, fa[30], pre[30], deg[30], s, t, d[30];int cur[30];bool vis[30];struct edge{ int u, v, cap, next; edge() {} edge(int u, int v, int w, int next):u(u),v(v),cap(w),next(next) {}}e[N<<1];int ecnt;void addedge(int u, int v, int w){ e[ecnt] = edge(u, v, w, pre[u]); pre[u] = ecnt++; e[ecnt] = edge(v, u, 0, pre[v]); pre[v] = ecnt++;}int find(int x){ return x==fa[x]?x:(fa[x]=find(fa[x]));}void Union(int u, int v){ u = find(u), v= find(v); if(u==v) return ; fa[u] = v;}bool is_ok(){ for(int i=0; i<26; i++) if(vis[i] && find(i)!=find(s)) return false; int res = 0; for(int i=0; i<26; i++) if(deg[i]%2){ res++; if(res==1) s = i; else t = i; } return res==0 || res==2;}bool BFS(){ memset(vis, 0, sizeof(vis)); queue<int >q; q.push(s); d[s] = 0, vis[s]=1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i=pre[u]; ~i; i=e[i].next) { int v = e[i].v; if(!vis[v] && e[i].cap>0) { vis[v] = 1; d[v] = d[u] +1; q.push(v); } } } return vis[t];}int DFS(int u, int c){ if(u==t || c==0) return c; int flow=0, f; for(int &i=pre[u]; ~i; i=e[i].next) { int v = e[i].v; if(d[v]==d[u]+1 && (f=DFS(v, min(c, e[i].cap)))>0) { e[i].cap -= f; e[i^1].cap += f; flow += f; c -= f; if(c==0) break; } } return flow;}int Maxflow(){ int flow = 0; while(BFS()) { memcpy(cur, pre, sizeof(pre)); flow += DFS(s, INF); } return flow;}void solve(){ scanf("%d", &n); memset(pre, -1, sizeof(pre)); memset(deg, 0, sizeof(deg)); memset(vis, 0, sizeof(vis)); for(int i=0; i<27; i++) fa[i] = i; ecnt = 0; int rev; char str[27]; for(int i=0; i<n; i++) { scanf("%s%d", str, &rev); int u = str[0]-‘a‘, v = str[strlen(str)-1]-‘a‘; deg[u]--; deg[v]++; vis[u] = vis[v] = true; s = u; if(rev) addedge(u, v, 1); Union(u,v); } t = -1; printf("Case %d: ", cas++); if(!is_ok()) { puts("Poor boy!"); return ; } if(t!=-1) addedge(t, s, 1); s = 26, t = 27; int fulflow = 0, flow; for(int i=0; i<26; i++) { if(deg[i]==0) continue; if(deg[i]<0) addedge(s, i, -deg[i]/2); else addedge(i, t, deg[i]/2), fulflow+=deg[i]/2; } flow = Maxflow(); puts(flow==fulflow?"Well done!":"Poor boy!");}int main(){// freopen("in.txt", "r", stdin); cin>>_; while(_--) solve(); return 0;}