hdu 4034 Graph（逆向floyd） - c++编程基础

floyd的松弛部分是 g[i][j] = min(g[i][j], g[i][k] + g[k][j]);也就是说，g[i][j] <= g[i][k] + g[k][j] (存在i->j, i->k, k->j的边)。

那么这个题很明显要逆向思考floyd算法。对于新图i,j,k，如果g[i][j] > g[i][k] + g[k][j],那么肯定是不合理的。而如果g[i][j] = g[i][k] + g[k][j]，明显i->j的边可以删去。

//#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i g[i][k] + g[k][j]) return -1;  
        else if(g[i][j] == g[i][k] + g[k][j])  
        {  
            vis[i][j] = 0;  
            ret--;  
        }  
    }  
    return ret;  
}  
  
int main()  
{  
    scanf("%d", &T);  
    FF(kase, 1, T+1)  
    {  
        scanf("%d", &n);  
        REP(i, n) REP(j, n)  
        {  
            scanf("%d", &g[i][j]);  
            vis[i][j] = i == j   0 : 1;  
        }  
        printf("Case %d: ", kase);  
        int ans = reFloyd();  
        if(ans == -1) puts("impossible");  
        else printf("%d\n", ans);  
    }  
    return 0;  
}