首页 > 代码库 > hdu 4034

hdu 4034

2024-07-19 13:32:47   211人阅读

比赛时才发现自己基础算法都忘得光光了，逆向floyd

i->j经过k点，只要i到j的距离大于或者等于，就把这边标记，实为去掉。。。此时整个图就减一条边

 1 #include<iostream> 2 #include<cstdio> 3 #include<limits.h> 4 #include<memory.h> 5 using namespace std; 6 #define INF INT_MAX 7 #define maxn 110 8 int n; 9 int d[maxn][maxn],m[maxn][maxn];10 int vis[maxn][maxn];11 void init()12 {13     memset(d,INF,sizeof(d));14     memset(vis,0,sizeof(vis));15 }16 void input()17 {18     for(int i = 0; i < n; i++)19         for(int j = 0;  j < n; j++)20         {21             scanf("%d",&d[i][j]);m[i][j] = d[i][j];22         }23 24 }25 int floyd()//逆向floyd26 {27     int cnt = 0;28     for(int k = 0; k < n; k++)29         for(int i = 0; i < n; i++)30             for(int j = 0; j < n; j++)31                 if(i != k && k != j && d[i][j] >= d[i][k] + d[k][j])32                 {33                     vis[i][j] = 1;34                     d[i][j] = d[i][k] + d[k][j];35                     if(d[i][j] < m[i][j])return -1;36                 }37     for(int i = 0; i < n; i++)38         for(int j = 0; j < n; j++)39             if(vis[i][j]) cnt++;40     return n * n - n - cnt;41 }42 int main()43 {44     int T;45     scanf("%d",&T);46     int cas = 1;47     while(T--)48     {49         scanf("%d",&n);50         init();51         input();52         printf("Case %d: ",cas++);53         int t = floyd();54         if(t == -1) puts("impossible");55         else cout<<t<<endl;56     }57 }

 

hdu 4034


联系
我们