hdu 4034 Graph(深化最短路floyd)

 

 

Graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 2188 Accepted Submission(s): 1101

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.

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
題目大意：給出一個地圖，已知每兩個點之間的最短路徑，求原圖最少有多少條邊。 特別注意： 1、這個圖是有向圖。 2、可以找到原圖就是輸出最少有多少條邊，否則輸出-1。 3、用floyd找到最短路以及進行更新。 4、先得到邊，再通過floyd去掉一些邊，舉個例子說：1->2的最短路為5，2->3的最短路為3,1->3的最短路為12，很明顯1->2->3的<1->3的路徑，所以1->3這條邊可以去掉。 5、注意輸出有個Case，避免wa。
詳見代碼。

#include 
#include 
#include 
#include 

using namespace std;

int Map[110][110],n;

int Search()
{
    int flag=1;
    int ans=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 (Map[i][j]>Map[i][k]+Map[k][j]&&Map[i][k]&&Map[k][j])
                {
                    flag=0;
                    return -1;
                }
                else
                {
                    if (Map[i][j]==Map[i][k]+Map[k][j]&&Map[i][k]&&Map[k][j])
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
    }
    return ans;
}

int main()
{
    int T;
    int nn;
    int Case=1;
    scanf(%d,&T);
    while (T--)
    {
        nn=0;
        scanf(%d,&n);
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++)
            {
                scanf(%d,&Map[i][j]);
                if (Map[i][j]!=0)
                    nn++;
            }
        }
        printf (Case %d: ,Case++);
        int cmp=Search();
        if (cmp==-1)
            printf (impossible
);
        else
            printf (%d
,nn-cmp);
    }
    return 0;
}