首页 > ACM题库 > HDU-杭电 > HDU 4034-Graph-图-[解题报告]HOJ
2015
04-15

HDU 4034-Graph-图-[解题报告]HOJ

Graph

问题描述 :

Everyone knows how to calculate the shortest path in a directed graph. In fact, the opposite problem is also easy. Given the length of shortest path between each pair of vertexes, can you find the original graph?

输入:

The first line is the test case number T (T ≤ 100).
First line of each case is an integer N (1 ≤ N ≤ 100), the number of vertexes.
Following N lines each contains N integers. All these integers are less than 1000000.
The jth integer of ith line is the shortest path from vertex i to j.
The ith element of ith line is always 0. Other elements are all positive.

输出:

The first line is the test case number T (T ≤ 100).
First line of each case is an integer N (1 ≤ N ≤ 100), the number of vertexes.
Following N lines each contains N integers. All these integers are less than 1000000.
The jth integer of ith line is the shortest path from vertex i to j.
The ith element of ith line is always 0. Other elements are all positive.

样例输入:

3
3
0 1 1
1 0 1
1 1 0
3
0 1 3 
4 0 2
7 3 0
3
0 1 4
1 0 2
4 2 0

样例输出:

Case 1: 6
Case 2: 4
Case 3: impossible

题意:给你图中任意两点间的最短路距离,求原图中边数最少是多少?

这题应该不难想,显然如果可以由其他边迭代到这个点的话就不用连边,只要统计一下要删去的边数,而且很明确的一点是这里迭代只需要1个点去迭代,因为任意两点间都是最短,那么必然存在1个点迭代使得这两点最短,假设求i->j的最短路 ,可以迭代i->k->h->g->j,肯定在中间k,h,j有一个点使得i-j最短,假设这个点是h那么必然i->h=i->k->h;h->j=h->g->j;因为都是最短路;说了这么多是为什么?因为我要将以前求flody的最外层放里面去。。。希望你能够理解为什么能这么做。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
4613099 2011-09-16 19:38:13 Accepted 4034 140MS 308K 943 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int gp[105][105],n;
int work()
{
	int flag=1,count=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(i==j)continue;
			for(int k=1;k<=n;k++)
			{
				if(i==k||j==k)continue;
				if(gp[i][j]>gp[i][k]+gp[k][j]&&gp[i][k]&&gp[k][j])
				{
					flag=0;
					return -1;
				}
				else
					if(gp[i][j]==gp[i][k]+gp[k][j]&&gp[i][k]&&gp[k][j])
					{
						count++;
						break;
					}
			}
		}
			return count;
}
int main()
{
	int T,t,num;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
		num=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				scanf("%d",&gp[i][j]);
				if(gp[i][j]!=0)num++;
			}
			printf("Case %d: ",t);
			int tem=work();
			if(tem==-1)
				printf("impossible\n");
			else
				printf("%d\n",num-tem);
	}
	return 0;
}

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

参考:http://blog.csdn.net/xymscau/article/details/6783187


,
  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。