2014
03-31

# HS BDC

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.

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.

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.

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

Case 1: Well done!
Case 2: Well done!
Case 3: Poor boy!

HintIn the first case, the word “tar” is still meaningful when reversed, and love8909 can make a list as “aloha-arachnid-dog-gopher-rat-tiger”.
In the second case, the word “thee” is still meaningful when reversed, and love8909 can make a list as “thee-earn-nothing”. In the third case,
no lists can be created. 

T个测试数据

n串字符 能否倒过来用(1表示能倒着用)

欧拉回路是图G中的一个回路，经过每条边有且仅一次，称该回路为欧拉回路。具有欧拉回路的图称为欧拉图，简称E图。

http://yzmduncan.iteye.com/blog/1149049

.

ch[i]表示字母i+‘a’ 的入度-出度的值

ch[i]>0 与汇点建边，权值为 ch[i]

#include <stdio.h>
#include <string.h>
#include <queue>
#define inf 10000
#define ll short
#define end End

using namespace std;

struct Edge{
short from, to, cap, nex;
}edge[1007];
void addedge(short u, short v, short cap){
Edge E ={u, v, cap, head[u]};
edge[edgenum] = E;
edge[edgenum] = E_;
}

short sign[28];
bool BFS(short from, short to){
memset(sign, -1, sizeof(sign));
sign[from] = 0;

queue<short>q;
q.push(from);
while( !q.empty() ){
int u = q.front(); q.pop();
for(short i = head[u]; i!=-1; i = edge[i].nex)
{
short v = edge[i].to;
if(sign[v]==-1 && edge[i].cap)
{
sign[v] = sign[u] + 1, q.push(v);
if(sign[to] != -1)return true;
}
}
}
return false;
}
short Stack[4], top, cur[4];
short dinic(short from, short to){
short ans = 0;
while( BFS(from, to) )
{
short u = from;		top = 0;
while(1)
{
if(u == to)
{
short flow = inf, loc;//loc 表示 Stack 中 cap 最小的边
for(short i = 0; i < top; i++)
if(flow > edge[ Stack[i] ].cap)
{
flow = edge[Stack[i]].cap;
loc = i;
}

for(short i = 0; i < top; i++)
{
edge[ Stack[i] ].cap -= flow;
edge[Stack[i]^1].cap += flow;
}
ans += flow;
top = loc;
u = edge[Stack[top]].from;
}
for(short i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标
if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
if(cur[u] != -1)
{
Stack[top++] = cur[u];
u = edge[ cur[u] ].to;
}
else
{
if( top == 0 )break;
sign[u] = -1;
u = edge[ Stack[--top] ].from;
}
}
}
return ans;
}
ll n;
char ss[22];
short ch[27], f[27];
bool use[27];
short start, end;

short find(short x){return x==f[x]?x:(f[x]=find(f[x]));}
void Union(short x, short y){
short fx = find(x), fy = find(y);
short temp = fx; if(fx>fy){fx=fy;fy=temp;}
f[fx] = fy;
}
int main(){
short T, i, j, Cas = 1; scanf("%d",&T);
while(T--)
{
memset(ch, 0, sizeof(ch));
memset(use,0, sizeof(use));
for(i=0;i<27;i++)f[i] = i;

scanf("%d",&n);
for(i = 0; i < n; i++)
{
scanf("%s %d",ss,&j);
int a = ss[0]-'a', b = ss[strlen(ss)-1] - 'a';
ch[a]++, ch[b]--;
use[a] = use[b] = true;
Union(a,b);

}
printf("Case %d: ",Cas++);
bool ok = true;
for(i=0;i<26;i++)
if(use[i])
{
j = i;
for(i++;i<26;i++)
if(use[i] && find(j)!=find(i))ok = false;
break;
}
short num = 0;
for(i=0;i<26;i++)if(use[i] &&  ch[i]%2)
{
num++;
if(ch[i]<0)start = i;
else end = i;
}
if(num == 1 || num>2)ok = false;
if(!ok){ printf("Poor boy!\n"); continue;}
start = 26, end = 27;
short sum = 0;
for(i=0;i<26;i++)if(ch[i] && use[i] && i!=end && i!=start)
{
if(ch[i]<0)
else
}
if(sum != dinic(start, end))
printf("Poor boy!\n");
else
printf("Well done!\n");

}
}

1. #include <cstdio>

int main() {