HS BDC
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 964 Accepted Submission(s): 390
Problem Description
IELTS is around the corner! love8909 has registered for the exam, but he still hasn’t got prepared. Now he decides to take actions. But when he takes out the New Oriental IELTS Vocabulary, he finds there are so many words. But love8909 doesn’t get scared, because he has got a special skill. If he can make a list with some meaningful words, he will quickly remember these words and will not forget them. If the last letter of some word Wa is the same as the first letter of some word Wb, then you can connect these two words and make a list of two words. If you can connect a word to a list, you will make a longer list.
While love8909 is making the list, he finds that some words are still meaningful words if you reverse them. For example, if you reverse the word “pat”, you will get another meaningful word “tap”.
After scanning the vocabulary, love8909 has found there are N words, some of them are meaningful if reversed, while others are not. Now he wonders whether he can remember all these words using his special skill.
The N-word list must contain every word once and only once.
While love8909 is making the list, he finds that some words are still meaningful words if you reverse them. For example, if you reverse the word “pat”, you will get another meaningful word “tap”.
After scanning the vocabulary, love8909 has found there are N words, some of them are meaningful if reversed, while others are not. Now he wonders whether he can remember all these words using his special skill.
The N-word list must contain every word once and only once.
Input
An integer T (T <= 50) comes on the first line, indicating the number of test cases.
On the first line of each test cases is an integer N (N <= 1000), telling you that there are N words that love8909 wants to remember. Then comes N lines. Each of the following N lines has this format: word type. Word will be a string with only ‘a’~’z’, and type will be 0(not meaningful when reversed) or 1(meaningful when reversed). The length of each word is guaranteed to be less than 20.
On the first line of each test cases is an integer N (N <= 1000), telling you that there are N words that love8909 wants to remember. Then comes N lines. Each of the following N lines has this format: word type. Word will be a string with only ‘a’~’z’, and type will be 0(not meaningful when reversed) or 1(meaningful when reversed). The length of each word is guaranteed to be less than 20.
Output
The format of the output is like “Case t: s”, t is the number of the test cases, starting from 1, and s is a string.
For each test case, if love8909 can remember all the words, s will be “Well done!”, otherwise it’s “Poor boy!”
For each test case, if love8909 can remember all the words, s will be “Well done!”, otherwise it’s “Poor boy!”
Sample Input
3
6
aloha 0
arachnid 0
dog 0
gopher 0
tar 1
tiger 0
3
thee 1
earn 0
nothing 0
2
pat 1
acm 0
Sample Output
Case 1: Well done! Case 2: Well done! Case 3: Poor boy!
一道水题，只需注意先判断图的连通性即可，然后就是直接套模板就可以ac
谁要是有闲工夫可以研究一下这两个测试数据
1：
4
a 0
b 0
bc 0
ac 1
2:
4
a 0
b 0
bc 0
ca 1
#include<iostream> #include<queue> #include<cstring> #include<cstdio> #include<climits> #define MAXE 1800 #define MAXP 30 #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b using namespace std; struct Edge { int s,t,f,next; } edge[MAXE]; int head[MAXP]; int cur[MAXP]; int pre[MAXP]; int stack[MAXE]; int used[MAXP]; int fa[MAXP]; int degree[MAXP]; int ent; int sum; int n,m,s,t,supers,supert; int num; int find(int x) { while(fa[x]!=x) x=fa[x]; return x; } void add(int start,int last,int f) { edge[ent].s=start; edge[ent].t=last; edge[ent].f=f; edge[ent].next=head[start]; head[start]=ent++; edge[ent].s=last; edge[ent].t=start; edge[ent].f=0; edge[ent].next=head[last]; head[last]=ent++; } bool bfs(int S,int T) { memset(pre,-1,sizeof(pre)); pre[S]=0; queue<int>q; q.push(S); while(!q.empty()) { int temp=q.front(); q.pop(); for(int i=head[temp]; i!=-1; i=edge[i].next) { int temp2=edge[i].t; if(pre[temp2]==-1&&edge[i].f) { pre[temp2]=pre[temp]+1; q.push(temp2); } } } return pre[T]!=-1; } int dinic(int start,int last) { int flow=0,now; while(bfs(start,last)) { int top=0; memcpy(cur,head,sizeof(head)); int u=start; while(1) { if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流 { int minn=INT_MAX; for(int i=0; i<top; i++) { if(minn>edge[stack[i]].f) { minn=edge[stack[i]].f; now=i; } } flow+=minn; for(int i=0; i<top; i++) { edge[stack[i]].f-=minn; edge[stack[i]^1].f+=minn; } top=now; u=edge[stack[top]].s; } for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边 if(edge[i].f&&pre[edge[i].t]==pre[u]+1) break; if(cur[u]==-1)//如果从该点未找到可行边，将该点标记并回溯 { if(top==0)break; pre[u]=-1; u=edge[stack[--top]].s; } else//如果找到了继续运行 { stack[top++]=cur[u]; u=edge[cur[u]].t; } } } return flow; } int main() { int cas; scanf("%d",&cas); for(int times=1;times<=cas;times++) { memset(head,-1,sizeof(head)); memset(used,0,sizeof(used)); memset(degree,0,sizeof(degree));//初始化的过程 ent=0; s=0,t=27; scanf("%d",&n); char str[25]; int mark; for(int i=1;i<=26;i++) fa[i]=i; for(int i=1;i<=n;i++) { scanf("%s%d",str,&mark); int len=strlen(str); int u=str[0]-'a'+1; int v=str[len-1]-'a'+1; used[u]=1; used[v]=1; if(find(u)!=find(v)) { fa[find(v)]=find(u);//检查图的联通性的过程 } degree[u]--; degree[v]++; if(mark) add(u,v,1); } int ok=1; int temp=0; for(int i=1;i<=26;i++) { if(used[i]&&fa[i]==i) { temp++; } } if(temp!=1)ok=0;//判断图是否联通 temp=0; int v1=-1,v2=-1; for(int i=1;i<=26;i++) { if(degree[i]%2) { temp++; if(v1==-1)v1=i; else v2=i; } } if(temp==0||temp==2) { if(temp==2) { add(v1,v2,1);//这块不用纠结那两个度数是奇数的点到底是不是一个入度大于出度一个出度大于入度，因为也许两个点的度数会同号完全就是由于我们给双向边随机取向的时候错误的取向导致的，所以我们不能直接否决掉而是要让他继续运行下去，如果是由于我们给双向边随机取向导致的错误，那后来就可以纠正过来。反之，如果不是这个原因造成的，那我们让他继续运行下去，最终他得出的答案也肯定是否定的。总之，在这儿只要这两个点的度数同为奇数我们就应该让他继续运行下去，至于你百度到的别的dinic代码，基本上都是这儿错了，你们尝试运行我提供的数据，他们都得挂。 degree[v1]--; degree[v2]++; } } else ok=0; printf("Case %d: ",times); temp=0; if(!ok)printf("Poor boy! "); else { for(int i=1;i<=26;i++) { if(degree[i]>0) add(i,t,degree[i]/2); else if(degree[i]<0) { add(s,i,-degree[i]/2); temp+=-degree[i]/2; } } if(dinic(s,t)==temp)printf("Well done! ");//如果跑出来的最大流正好能使得与s点相连的边都满流，则表示符合要求 else printf("Poor boy! "); } } return 0; }