Codeforce 295B Greg and Graph(Floyd的深入理解)

题目链接：http://codeforces.com/problemset/problem/295/B

题目大意：
给出n个点的完全有权有向图，每次删去一个点，求删掉该点之前整张图各个点的最短路之和（包括i->j和j->i）。
解题思路：
这里利用了floyd的性质，下面看一下floyd的写法：
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
每次利用点k进行松弛，可以理解为将k点加入图中，所以我们可以倒着加点，如下所示：
for (k=n;k>=1;k--)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j] = min(a[i][j], a[i][p[k]]+a[p[k]][j]);
每次松弛完顺便记录结果即可。

代码：

 #include<bits/stdc++.h>

 #define lc(a) (a<<1)

 #define rc(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define clr(arr,val) memset(arr,val,sizeof(arr))

 #define _for(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=1e3+;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 int p[N];

 LL mp[N][N];

 LL ans[N];

 bool del[N];

 int main(){

     FAST_IO;

     int n;

     cin>>n;

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

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

             cin>>mp[i][j];

         }

     }

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

         del[i]=true;

         cin>>p[i];

     }

     //利用floyd松弛的特性，每次松弛相当于加点，所以直接倒着加点，同时记录结果

     for(int k=n;k>=;k--){

         int t=p[k];

         del[t]=false;

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

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

                 mp[i][j]=min(mp[i][j],mp[i][t]+mp[t][j]);

             }

         }

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

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

                 if(!del[i]&&!del[j]){

                     ans[k]+=mp[i][j];

                 }

             }

         }

     }

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

         cout<<ans[i]<<endl;

     }

     return ;

 }

巴特西

Codeforce 295B Greg and Graph(Floyd的深入理解)

最新文章

热门文章