首页 > ACM题库 > HDU-杭电 > HDU 1625 Numbering Paths-最短路径-[解题报告] C++
2013
12-16

HDU 1625 Numbering Paths-最短路径-[解题报告] C++

Numbering Paths

问题描述 :

Problems that process input and generate a simple “yes” or “no” answer are called decision problems. One class of decision problems, the NP-complete problems, are not amenable to general efficient solutions. Other problems may be simple as decision problems, but enumerating all possible “yes” answers may be very difficult (or at least time-consuming).

This problem involves determining the number of routes available to an emergency vehicle operating in a city of one-way streets.

Given the intersections connected by one-way streets in a city, you are to write a program that determines the number of different routes between each intersection. A route is a sequence of one-way streets connecting two intersections.

Intersections are identified by non-negative integers. A one-way street is specified by a pair of intersections. For example, j k indicates that there is a one-way street from intersection j to intersection k. Note that two-way streets can be modeled by specifying two one-way streets: j k and k j .

Consider a city of four intersections connected by the following one-way streets:

0 1
0 2
1 2
2 3

There is one route from intersection 0 to 1, two routes from 0 to 2 (the routes are 0-1-2 and 0-2 ), two routes from 0 to 3, one route from 1 to 2, one route from 1 to 3, one route from 2 to 3, and no other routes.
It is possible for an infinite number of different routes to exist. For example if the intersections above are augmented by the street , there is still only one route from 0 to 1, but there are infinitely many different routes from 0 to 2. This is because the street from 2 to 3 and back to 2 can be repeated yielding a different sequence of streets and hence a different route. Thus the route 0-2-3-2-3-2 is a different route than 0-2-3-2 .

输入:

The input is a sequence of city specifications. Each specification begins with the number of one-way streets in the city followed by that many one-way streets given as pairs of intersections. Each pair j k represents a one-way street from intersection j to intersection k. In all cities, intersections are numbered sequentially from 0 to the “largest” intersection. All integers in the input are separated by whitespace. The input is terminated by end-of-file.

There will never be a one-way street from an intersection to itself. No city will have more than 30 intersections.

输出:

For each city specification, a square matrix of the number of different routes from intersection j to intersection k is printed. If the matrix is denoted M, then M[j][k] is the number of different routes from intersection j to intersection k. The matrix M should be printed in row-major order, one row per line. Each matrix should be preceded by the string “matrix for city k” (with k appropriately instantiated, beginning with 0).

If there are an infinite number of different paths between two intersections a -1 should be printed. DO NOT worry about justifying and aligning the output of each matrix. All entries in a row should be separated by whitespace.

样例输入:

7 0 1 0 2 0 4 2 4 2 3 3 1 4 3
5 
0 2 
0 1 1 5 2 5 2 1
9
0 1 0 2 0 3
0 4 1 4 2 1
2 0
3 0
3 1

样例输出:

matrix for city 0
 0 4 1 3 2
 0 0 0 0 0
 0 2 0 2 1
 0 1 0 0 0
 0 1 0 1 0
matrix for city 1
 0 2 1 0 0 3
 0 0 0 0 0 1
 0 1 0 0 0 2
 0 0 0 0 0 0
 0 0 0 0 0 0
 0 0 0 0 0 0
matrix for city 2
 -1 -1 -1 -1 -1
 0 0 0 0 1
 -1 -1 -1 -1 -1
 -1 -1 -1 -1 -1
 0 0 0 0 0

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

思路:大牛说是floyd判环,一想确实如此,我还一直在想如果用记忆化的怎么处理环呢…orz….

首先通过Floyd预处理,把所有的路径数求出来,即d[i][j] += d[i][k] * d[k][j]。然后确定有无环,如果存在环的话,即d[k][k] != 0(存在环),那么所有的点i,j,只要经过了k(i->k->j),那么它的路径数是不能确定的,反之,确定。

#include<iostream>
 #include<cstdio>
 #include<cstring>
 using namespace std;
 #define MAXN 55
 int path[MAXN][MAXN];
 int m,n;
 
 void floyd(){
     for(int k=0;k<=n;k++){
         for(int i=0;i<=n;i++){
             for(int j=0;j<=n;j++){
                 path[i][j]+=path[i][k]*path[k][j];
             }
         }
     }
     for(int i=0;i<=n;i++)if(path[i][i]){
         path[i][i]=-1;
         for(int j=0;j<=n;j++){
             for(int k=0;k<=n;k++){
                 if(path[j][i]&&path[i][k]){
                     path[j][k]=-1;
                 }
             }
         }
     }
 }
 
 int main(){
     int u,v,t=0;
     while(~scanf("%d",&m)){
         memset(path,0,sizeof(path));
         n=0;
         for(int i=1;i<=m;i++){
             scanf("%d%d",&u,&v);
             path[u][v]=1;
             n=max(n,max(u,v));
         }
         printf("matrix for city %d\n",t++);
         floyd();
         for(int i=0;i<=n;i++){
             for(int j=0;j<n;j++){
                 printf(" %d",path[i][j]);
             }
             printf(" %d\n",path[i][n]);
         }
     }
     return 0;
 }

 

解题报告转自:http://www.cnblogs.com/wally/archive/2013/05/11/3072575.html


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