HDU 4034 Graph：反向floyd

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

题意：

　　有一个有向图，n个节点。给出两两节点之间的最短路长度，问你原图至少有多少条边。

　　如果无解，输出"impossible"。

题解：

　　因为在floyd中：

　　　　if(dis[i][k] + dis[k][j] < dis[i][j])

　　　　　　dis[i][j] = dis[i][k] + dis[k][j];

　　所以对于原图再跑一遍floyd。

　　如果出现dis[i][k] + dis[k][j] < dis[i][j]的情况，则给出的邻接矩阵不是最短路，无解。

　　对于三个点i,j,k，如果有dis[i][j] == dis[i][k] + dis[k][j]，则(i,j)这条边一定可以舍去。

　　因为如果其他的最短路径要用到(i,j)边的话，用(i,k)+(k,j)边替换也是可以的。

　　所以在floyd中顺便统计下就可以了。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 105

 using namespace std;

 int n,t,cas;

 int dis[MAX_N][MAX_N];

 bool vis[MAX_N][MAX_N];

 void read()

 {

     cin>>n;

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=n;j++)

         {

             cin>>dis[i][j];

         }

     }

 }

 int floyd()

 {

     memset(vis,false,sizeof(vis));

     int cnt=n*(n-);

     for(int k=;k<=n;k++)

     {

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 if(i!=j && j!=k && i!=k)

                 {

                     if(dis[i][k]+dis[k][j]<dis[i][j]) return -;

                     if(dis[i][k]+dis[k][j]==dis[i][j] && !vis[i][j])

                     {

                         vis[i][j]=true;

                         cnt--;

                     }

                 }

             }

         }

     }

     return cnt;

 }

 void work()

 {

     int ans=floyd();

     cout<<"Case "<<cas<<": ";

     if(ans==-) cout<<"impossible"<<endl;

     else cout<<ans<<endl;

 }

 int main()

 {

     cin>>t;

     for(cas=;cas<=t;cas++)

     {

         read();

         work();

     }

 }

巴特西

HDU 4034 Graph：反向floyd

最新文章

热门文章