首页 > ACM题库 > HDU-杭电 > HDU 3812-Sea Sky-模拟-[解题报告]HOJ
2015
04-13

HDU 3812-Sea Sky-模拟-[解题报告]HOJ

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3812

题目大意:给定n个字符对ai,bi,表示ai和bi相连,现在要求求出从“sea”连接到"sky"的一个序列,序列中的字符串出现两次,长度要求最大,并且字典序最小,如果没办达到要求,输出"what a pity“。

解题思路:这题是去年武汉邀请赛的题目,难度中上,在做模拟比赛的时候碰到了这题,当时没敢开,难题猛于虎。赛后为了防止比赛时再被虐花点时间过了这题。刚开始想的时候觉得是图论没思路,但一看到最多的字符串种类为16,有戏。就想着状态dp,状态就三万多个,怎么搞都不超时,又看了一下题目,要求输出字典序最小,顿时泄气,还是要搜索啊,那索性直接搜索再加个强力剪枝什么的过了他。

       开始的时候把这些字符串用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]);
        }
    }
}

本文ZeroClock原创,但可以转载,因为我们是兄弟。

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/woshi250hua/article/details/7614161


  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的思路是什么呢?

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。