2017冬季24集训模拟题-24星球的末日（Floyd）

24 星球的末日
【问题描述】
24 星球的世界末日就要到了，可是诺亚方舟还没有制造完成。为了制造诺亚
方舟这个星球上的所有国家都站在统一战线。现在一共有n个国家，一个国家到
另一个国家都有一条且仅有一条通信渠道，且这个渠道有一个距离，这样就形
成了一个有向完全图。。世界末日的预兆已经来了，世界上很多东西都在遭到不
明原因的破坏，包括这些通信渠道。现在为了联合制造出诺亚方舟，需要统计
所有国家对（a到b和b到a是不同的）之间通信最短距离之和。( ( 例如只有两个星
球，a到b与b 到a的距离都是1，则最短距离和为2。) ) 可是每隔一段时间就有一些
渠道会被破坏，现在 24 星球的首领大龙急需要你来解决这个问题。
【输入文件】
读入文件 destroy.in
对于每组数据，第一行是一个n，表示有n个国家，接下来有n行，每有n 个非
负整数。第i行第j 列的数字表示国家i i 到国家j j 的通信渠道距离（距离不大于
10000 ）。接下来是一个数字m，表示在可以预知的未来中会有m次破坏会施加到
通信渠道中，每次破坏只能破坏一条渠道，一条渠道可以被破坏多次，，但是第
一次破坏这条渠道就无法再发送信息。接下来有m行，每行两个整数a、b，表示
国家a到国家b的通信渠道遭到破坏。
【输出文件】
输出文件 destroy.out
对于每组数据，输出m m 行，第i i 行表示第i i 次破坏后对应的答案是多少。如果
存在两个国家无法相互到达，输出1 1 NF 。
【输入样例】
3
0 1 1
1 0 1
1 1 0
4 4
1 2
1 2
2 3
2 3
【输出样例】
7
7
8
1NF
【数据规模】
40% 的数据中 1<n<=50,1<m<=50;
100% 的数据中 1<n<=200,1<m<=200 。

————————————————————————————题解

删边有点麻烦，所以我们一次性读入m个询问，离线处理，把所有边删除，倒着加上一条条边，回溯状态

我们加上第m条边时，我们到达的就是m-1的状态，加上第m-1条边时，就是m-2询问的状态……加上第2条边时，就是1询问的状态

枚举i=1->n j=1->n 用一条边u，v更新g[i][j]=min(g[i][j],g[i][u]+val(u,v)+g[v][j]

同时因为边可能重复被删，用一个next数组记录这条边最早被删掉的时刻，样例中next[2]=1，如果next不为0，当前状态的边是无法复原的，所以直接由上一个时刻过继过来就可以了

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <set>

 #include <vector>

 #include <string.h>

 #include <cmath>

 #define siji(i,x,y) for(int i=(x);i<=(y);++i)

 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)

 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)

 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)

 #define inf 0x3f3f3f3f

 #define ivorysi

 #define mo 97797977

 #define hash 974711

 #define base 47

 #define MAXN 30005

 #define fi first

 #define se second

 #define pii pair<int,int>

 #define eps 1e-8

 typedef long long ll;

 using namespace std;

 int n,m;

 int f[][];

 int g[][];

 int a[],b[],ans[],next[];

 bool flag=;

 void solve() {

     scanf("%d",&n);

     siji(i,,n) {

         siji(j,,n) {

             scanf("%d",&f[i][j]);

             g[i][j]=f[i][j];

         }

     }

     scanf("%d",&m);

     siji(i,,m) {

         scanf("%d%d",&a[i],&b[i]);

         g[a[i]][b[i]]=-;

     }

     siji(k,,n) {

         siji(i,,n) {

             siji(j,,n) {

                 if(g[i][k]==- || g[k][j]==-) continue;

                 int x=g[i][k]+g[k][j];

                 if(g[i][j]==-) {

                     g[i][j]=x;

                 }

                 else {

                     g[i][j]=min(x,g[i][j]);

                 }

             }

         }

     }

     siji(i,,m) {

         siji(j,i+,m) {//这里打错了一次变量名

             if(a[i]==a[j] && b[i]==b[j]) {

                 if(next[j]==) next[j]=i;

                 else if(next[j] > i) next[j]=i;

             }

         }

     }

     siji(i,,n) {

         siji(j,,n) {

             if(g[i][j]==-) {ans[m]=-;goto s;}

             ans[m]+=g[i][j];

         }

     }

     s:

     gongzi(i,m,) {

         if(next[i]!=) {ans[i-]=ans[i];continue;}

         /*

         更新时不要直接g[a[i]][b[i]]=f[a[i]][b[i]]

         因为g[a[i]][b[i]]可能小于f[a[i]][b[i]]

         这样会得到错解

         */

         siji(j,,n) {

             siji(k,,n) {

                 if(g[j][a[i]] == - || g[b[i]][k] == -) continue;

                 int x=g[j][a[i]]+f[a[i]][b[i]]+g[b[i]][k];

                 if(g[j][k]==-) {

                     g[j][k]=x;

                 }

                 else {

                     g[j][k]=min(g[j][k],x);

                 }

             }

         }

         siji(j,,n) {

             siji(k,,n) {

                 if(g[j][k]==-) {ans[i-]=-;goto t;}

                 ans[i-]+=g[j][k];

             }

         }

         t:;

     }

     siji(i,,m) {

         if(ans[i]==-) puts("1NF");

         else {

             printf("%d\n",ans[i]);

         }

     }

 }

 int main(int argc, char const *argv[])

 {

 #ifdef ivorysi

     freopen("destroy.in","r",stdin);

     freopen("destroy.out","w",stdout);

 #else

     freopen("f1.in","r",stdin);

 #endif

     solve();

     return ;

 }

巴特西

2017冬季24集训模拟题-24星球的末日（Floyd）

最新文章

热门文章