首页 > ACM题库 > HDU-杭电 > HDU 3379-Life Connections-最短路径-[解题报告]HOJ
2014
03-16

HDU 3379-Life Connections-最短路径-[解题报告]HOJ

Life Connections

问题描述 :

On Pandora all Navi are connected by friendships. After carefully mapping friendships between different Navi, Grace wants to measure the strength of the connection between pairs of Navi. She decides the way to calculate this is to treat Navi as nodes in a graph, and friendships between Navi as edges. Then the connection strength between two Navi can be defined as the number different shortest paths each could take to visit the other. Your goal is to help her calculate these values.Given a list of connections between Navi and two Navi u and v, you must compute the number of different shortest paths between u and v. The length of the path is the number of Navi on the path. Two paths are different if they pass through at least one different Navi.

输入:

Connections between Navi are described beginning with the line “GRAPH BEGIN”. Additional lines lists individual Navi (nodes), followed (on the same line) by their friends (edges). The line “GRAPH END” ends the list of connection descriptions. The next lines describe pairs of Navi for which answers need to be calculated, each on a single line. Following these lines, a new instance of the problem can be given, starting from scratch.You may assume all Navi are connected (i.e., any Navi can reach another Navi by some path). Not all Navi will have their connections listed on a separate line: the friendships of some Navi may only be implied by the friendships given on other lines.

输出:

Connections between Navi are described beginning with the line “GRAPH BEGIN”. Additional lines lists individual Navi (nodes), followed (on the same line) by their friends (edges). The line “GRAPH END” ends the list of connection descriptions. The next lines describe pairs of Navi for which answers need to be calculated, each on a single line. Following these lines, a new instance of the problem can be given, starting from scratch.You may assume all Navi are connected (i.e., any Navi can reach another Navi by some path). Not all Navi will have their connections listed on a separate line: the friendships of some Navi may only be implied by the friendships given on other lines.

样例输入:

GRAPH BEGIN 
a b c 
b d 
c d 
d e 
GRAPH END 
a b
a c
a d
a e
b c
b e

样例输出:

a b 1
a c 1
a d 2
a e 2
b c 2
b e 1

注意:自己到自己的路径数为0,交了24次啊,还有那恶心的案例,多了一个空格
源代码:
#include<iostream>
#include<string>
using namespace std;

const int maxn=1005;
int map[maxn][maxn],n,cnt[maxn][maxn];
char name[maxn][100];

int match_name(char str[])
{
   for(int i=1;i<n;i++)
       if(strcmp(str,name[i])==0)
           return i;
    strcpy(name[n],str);
    return n++;
}

void str_convert(char str[])
{
    int i,j,first_node,k;
    bool flag=0;
    char str1[100];
    for(i=0;i<strlen(str);)
    {
        for(j=0;str[i]!=' '&&str[i]!='\0';i++,j++)
            str1[j]=str[i];
        str1[j]='\0';
        i++;
        k=match_name(str1);
        if(flag==0)
        {
            first_node=k;
            flag=1;
        }
        else if(map[first_node][k]==0)
            {
              map[first_node][k]=map[k][first_node]=1;
              cnt[first_node][k]=cnt[k][first_node]=1;
            }

    }
}

void floyd() //求两点间最短路径的路径数量
{
    int i,j,k;
    for(k=1;k<n;k++)
        for(i=1;i<n;i++)
            for(j=1;j<n;j++)
              if(map[i][k] && map[k][j])
                if(map[i][j]==0)
                {
                      map[i][j]=map[i][k]+map[k][j];
                      cnt[i][j]=cnt[i][k]*cnt[k][j];
                }
                else if(map[i][k]+map[k][j]<map[i][j])
                {
                    map[i][j]=map[i][k]+map[k][j];
                    cnt[i][j]=cnt[i][k]*cnt[k][j];
                }
                else if(map[i][k]+map[k][j]==map[i][j])
                    cnt[i][j] += cnt[i][k]*cnt[k][j];
}

int main()
{
    int i,j;
    char str[100],str1[100],str2[100];

    gets(str);
    while(gets(str))
    {
      n=1;
      memset(map,0,sizeof(map));
      memset(cnt,0,sizeof(cnt));
      str_convert(str);
      while(gets(str))
      {
        if(strcmp(str,"GRAPH END")==0) break;
        str_convert(str);
      }
      for(i=1;i<n;i++)
         map[i][i]=1;

      floyd();

       while(cin>>str1>>str2)
       {
        if(strcmp(str1,"GRAPH")==0 && strcmp(str2,"BEGIN")==0) break;
        i=match_name(str1);
        j=match_name(str2);
        cout<<str1<<" "<<str2<<" "<<cnt[i][j]<<endl;
       }
    }
    return 0;
}

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

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

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  5. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。