HDU 4034 图论 Floyd-白红宇

HDU 4034 图论 Floyd

阅读量：2440 次

发布时间：2019-05-10

本文共 2658 字，大约阅读时间需要 8 分钟。

/*******************************************************************************   前几天真TMD NC死了。。。一次Floyd就完事，每次观察dp[i, k] + dp[k, j]和dp[i, j]的值，若dp[i, k] + dp[k, j] < dp[i, j]，显然无解，因为尼玛的都不是最短路的图。。。如果dp[i, k] + dp[k, j] == dp[i, j]，那就把i-->j这条边给删了，因为可以通过k为中间点走，所以多余了～*******************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;typedef __int64 LL; //VCtypedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef vector
                                 
                                   VI;typedef vector
                                  
                                    VC;typedef vector
                                   
                                     VF;typedef vector
                                    
                                      VS;template 
                                     
                                      T sqa(const T & x){ return x * x;}template 
                                      
                                       T gcd(T a, T b){ if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;};const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 104;int test, n, dp[MAXN][MAXN];bool hs[MAXN][MAXN];bool floyd(){ for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { if (i == k) { continue ; } for (int j = 0; j < n; ++j) { if (k == j || i == j) { continue ; } if (dp[i][k] + dp[k][j] < dp[i][j]) { return false; } if (dp[i][k] + dp[k][j] == dp[i][j]) { hs[i][j] = false; } } } } return true;}void ace(){ int cas = 1; int res = 0; for (cin >> test; test--; ++cas) { cin >> n; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> dp[i][j]; if (i == j) { dp[i][j] = 0; } } } CLR(hs, true); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (0 == dp[i][j]) { hs[i][j] = false; } } } cout << "Case " << cas << ": "; if (!floyd()) { cout << "impossible" << endl; continue ; } res = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { res += hs[i][j]; } } cout << res << endl; } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif ace(); return 0;}/*******************************************************************************Test Data...330 1 11 0 11 1 030 1 3 4 0 27 3 030 1 41 0 24 2 0*******************************************************************************/