首页 > 代码库 > hdu 4034 Graph
hdu 4034 Graph
转载请注明出处:http://blog.csdn.net/u012860063
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4034
Graph
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)Total Submission(s): 1650 Accepted Submission(s): 826
Problem Description
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?
Input
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.
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.
Output
For each case, you should output “Case k: ” first, where k indicates the case number and counts from one. Then one integer, the minimum possible edge number in original graph. Output “impossible” if such graph doesn‘t exist.
Sample Input
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
Sample Output
Case 1: 6 Case 2: 4 Case 3: impossible
Source
The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest
Recommend
lcy | We have carefully selected several similar problems for you: 4039 4038 4036 4033 4037
题意:就是找出边数最小的原始图,输出边数即可!
思路:就是遍历原有的边数,判断有那些边是可以去掉的,用Floyd就好!
代码如下:
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <climits> #include <ctype.h> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <iostream> #include <algorithm> using namespace std; #define PI acos(-1.0) #define INF 0xffffff int n,coun,i,j,k; int map[147][147]; void init() { memset(map,0,sizeof(map)); } int Floyd() { for(i = 1 ; i <= n ; i++) { for(j = 1 ; j <= n ; j++) { if(map[i][j] == 0) continue; for(k = 1 ; k <= n ;k++) { if( map[i][k] != 0 && map[k][j] != 0) { if(map[i][j] > map[i][k] + map[k][j]) //不可能存在折线的路径比直线的路径短,如果出现则可判断这样的图表不存在 return 0; else if(map[i][j] == map[i][k] + map[k][j]) { coun--; break; } } } } } return coun; } int main() { int T,cas; while(~scanf("%d",&T)) { cas = 0; while(T--) { coun = 0; init(); scanf("%d",&n); for(i = 1; i <= n ; i++) { for(j = 1 ; j <= n ; j++) { scanf("%d",&map[i][j]); if(map[i][j] != 0) coun++; } } int ans = Floyd(); if(ans != 0) printf("Case %d: %d\n",++cas,ans); else printf("Case %d: impossible\n",++cas); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。