2015
04-13

# Sea Sky

Sea and Sky are the most favorite things of iSea, even when he was a small child.
Suzi once wrote: white dew fly over the river, water and light draw near to the sky. What a wonderful scene it would be, connecting the two charming scenery. But iSea cannot ask help from God, or some other deities in China. The only mean he can use is imagination.

For example, from sea, he can associate with love, from love, he can see sky in (strange logic, aha? leave him alone, we don’t really care how he imagine since he is so weird). In this way, he connects "Sea" and "Sky" in mind, fulfills his goal.
However, he can only solve the puzzle with small number of words, when the connection increases, his brain will come to be a total mess. Now, can you smart guys help him?

Now iSea gives you some word pairs he can associate, from any one of them to another. He wishes use the maximum word to make an association list, from “sea” to “sky”, of course, no word should appear in the list twice because it would lead to an infinite loop. Your task is to find a list, which contains the maximum word and every neighbor word can be connected in mind. If several solutions exist, find the lexicographically minimum one.
Lexicographical sequence is the order in one dictionary. For example, “cat” is less than “do”, and “do” is less than “dog”.

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with an integer N, then N lines follow, each line contains two words can be connected in mind.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 100
3. The number of different words and the length of words is no more than sixteen.

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with an integer N, then N lines follow, each line contains two words can be connected in mind.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 100
3. The number of different words and the length of words is no more than sixteen.

3
2
sea love
sky love
7
sea pure
pure air
air white
sky white
pure holy
holy white
sky holy
3
sea blue
sky white
blue green

Case 1: sea love sky
Case 2: sea pure air white holy sky
Case 3: what a pity

开始的时候把这些字符串用map转化为节点并建图，建好图写了个十分暴力的深搜，试探性地交了下果然Tle。然后开始想如何剪枝，很常规的有两个：1、如果sea和sky不出现在输入中，那他们怎么连接都连接不到对方，人鬼殊途啊。2、如果sea和sky不在一个连通分支，那他们怎么连接都连接不到对方，不是同一个世界的人啊。这两个显然不能有效地增加效率，加上去再交还是Tle。然后开始找性质，其实剪枝就是要求我们找出题目中的性质，然后把不需要搜索的地方排除掉。本题要求的序列中字符串不能出现两次，那我们从sea节点开始遍历，如果某个节点不经过sky就能遍历，那说明在最后的深搜中可以到达，如果某些节点必须要通过sky节点，那说明这个节点必然没办法到达（可以到达的话sky节点就要经过两次），这些符合条件的节点组成几何Set1？同理，可以从end也找一次也能找到一个集合Set2。这样就得到了两个集合Set1和Set2，他们的交集就是可能出现在最后的序列中的节点。记录这个集合大小result，表示所有序列的最大长度，如果第一次碰到序列长度等于result，他就是最后的解（前提是字典序最小，这个在建图前对每个字符串排个序就可以保证）。

举个例子: a <–>sea    b<—> sea  sky<–> b  sky<–>d  那Set1集合为sea a b sky,Set2集合为sky b d sea，他们的交集是sea sky b，只有这三个字符串可能出现在最后的序列中。

10

sea a
sea b
sea c
c d
a sky
sky c
sky b
d sky

7
sea pure
pure air
air white
sky white
pure holy
holy white
sky holy

2
sea love
sky love

3
sea blue
blue green
fuckfuck white

#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define MIN 30
#define MAX 300
#define max(a,b) (a)>(b)?(a):(b)

struct node {

char s1[MAX],s2[MAX];
}ver[MAX];

vector<int> maze[MIN];
map<string,int> mmap;

int n,result,flag,maybe[MIN][4];
int beg,end,maxx,tot,fa[MIN],vis[MIN];
char str[MAX][MIN],ans[MAX][MIN];

int cmp(node a,node b) {
//排序用到的比较函数
if (strcmp(a.s1,b.s1) == 0)
return strcmp(a.s2,b.s2) < 0;
else return strcmp(a.s1,b.s1) < 0;
}
int GetFa(int x) {
//获取父亲节点
int y = fa[x];
while (y != fa[y]) y = fa[y];
return y;
}
void UnionSet(int u,int v) {
//并查集的并操作
int fau = GetFa(u);
int fav = GetFa(v);
if (fav != fau) fa[fau] =fav;
}
void Create_Graph() {
//建好一张有序的图
int i,u,v;
for (i = 1; i <= 2 * n; ++i) {

string tps1 = string(ver[i].s1);
string tps2 = string(ver[i].s2);
if (mmap.find(tps1) == mmap.end())
u = ++tot,mmap[tps1] = u;
else u = mmap[tps1];
if (mmap.find(tps2) == mmap.end())
v = ++tot,mmap[tps2] = v;
else v = mmap[tps2];
maze[u].push_back(v);

UnionSet(u,v);
strcpy(str[u],ver[i].s1);
strcpy(str[v],ver[i].s2);
if (tps1 == "sea") beg = u;
else if (tps2 == "sea") beg = v;
if (tps1 == "sky") end = u;
else if (tps2 == "sky") end = v;
}
}

void LookConn(int k,int flag,int in) {
//寻找从beg开始到不经过end到达的点或者从end开始不经过beg能到达的点
vis[k] = 1,maybe[k][in] = 1;
if (k == flag) return;
for (int i = 0; i < maze[k].size(); ++i) {

int v = maze[k][i];
if (vis[v]) continue;
LookConn(v,flag,in);
}
}
void Dfs(int k,int cnt,int *vis,int *arr) {
//普通深搜，加个剪枝而已
vis[k] = 1,arr[cnt] = k;
if (k == end) {

if (cnt > maxx) {

maxx = cnt;
for (int i = 1; i <= maxx; ++i)
strcpy(ans[i],str[arr[i]]);
}
if (maxx == result) flag = 1;//剪枝，result是能够到达的最多数量，因为有序，此解必是最优
return;
}

for (int i = 0; i < maze[k].size(); ++i) {

int v = maze[k][i];
if (vis[v] == 0 && maybe[v][2] == 1) {

vis[v] = 1;
Dfs(v,cnt+1,vis,arr);
if (flag) return;
vis[v] = 0;
}
}
}
int Solve_1A(){

int i,j,k,arr[MIN];

//寻找可能到达的点
memset(maybe,0,sizeof(maybe));
memset(vis,0,sizeof(vis));
LookConn(beg,end,0);
memset(vis,0,sizeof(vis));
LookConn(end,beg,1);
result = 0;
for (i = 1; i <= tot; ++i) {

if (maybe[i][1] && maybe[i][0])
maybe[i][2] = 1;
if (maybe[i][2]) result++;
}

//赋初值，并从beg开始深搜
memset(vis,0,sizeof(vis));
Dfs(beg,1,vis,arr);
return maxx;
}

int main()
{
int u,v,tpu,tpk;
int i,j,k,t,cas = 0;

scanf("%d",&t);
while (t--) {

scanf("%d",&n);
mmap.clear();
flag = maxx = 0;
tot = beg = end = 0;
for (i = 1; i < MIN; ++i)
maze[i].clear(),fa[i] = i;

for (i = 1; i <= n; ++i) {
//无向处理成有向
scanf("%s%s",ver[i].s1,ver[i].s2);
strcpy(ver[i+n].s1,ver[i].s2);
strcpy(ver[i+n].s2,ver[i].s1);
}

//对节点根据字典序排序，把同一个节点出来的归类
sort(ver+1,ver+1+2*n,cmp);
Create_Graph();

//输出解
printf("Case %d: ",++cas);
if (end == 0 || beg == 0
|| GetFa(beg) != GetFa(end))
printf("what a pity\n");
else {

int maxx = Solve_1A();
for (i = 1; i <= maxx; ++i)
printf(i == maxx ? "%s\n" : "%s ",ans[i]);
}
}
}

1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

2. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

3. if(j){
int ans=a ;
for(int x=j-1;x>=0;x–){
if(!a ) break;
ans=min(ans,a );
sum+=ans;
}
}
求解释，，dp的思路是什么呢？