2014
03-16

# 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

#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，也要很久才能得出结果，本人亲测