CF1842D Tenzing and His Animal Friends 题解

· · 题解

很好的一道图论建模题。

看到 m 个约束很容易想到对约束的两个对象建边，然后构造一个无向带权图 G 出来。下面规定 d_{i,j} 为 G 中 i 到 j 的最短路长度。

如果 G 中 1 和 n 之间不连通，那么丁真可以玩无限久：只用让丁真和 1 所在的连通块中的所有动物一起玩，就可以玩无限久。否则 n 的限制条件最终一定会影响到 1，导致丁真不能玩无限久。

现在考虑有解时怎么构造解。两种想法，一种是一开始能玩的全部一起玩（即第一次游戏最大化 01 集合中 1 的个数），然后每次会删掉几个不满足条件的，最后一直删到不能再删；还有一种是开始游戏前只有 1 还有 d_{1,i}=0 的 i，开始游戏后每次可以添加几个动物玩，直到最后不能再添加。这里着重介绍一下第二种解法。

一开始集合里只有 1 一个动物。接下来对于任意两只相互有约束的动物，为最大限度利用时间，先加入的那只可以把它们两只动物之间约束的时间自己全部消耗完。具体地，假设两只动物分别在时刻 t_1 和 t_2 加入集合，它们之间的时间限制为 w，有 |t_1-t_2|\le w。显然这是一个典型的差分约束算法；只需要按照 d_{1,i}(2\le i<n) 从小到大排序，依次将每一只动物放进集合（如果 d_{1,i}=d_{1,j} 相同那么将 i 和 j 同时放入集合）；对于相邻的两次游戏，令第二次游戏新加入的动物与 1 之间的最短路为 x，上一次游戏加入的动物与 1 之间的最短路为 y，那么第一次游戏持续时间应该为 y-x。一直放到必须把 n 加进去时结束游戏。可以证明游戏轮数最多为 n-1，玩的最多时间为 d_{1,n}，符合题意。

实现过程可以使用优先队列维护。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
main(){
  ios::sync_with_stdio(false);
  int n,m,c=0; cin>>n>>m;
  vector<vector<int> > d(n,vector<int>(n,2e18));
  vector<bool> b(n);
  for(int i=0;i<n;i++)d[i][i]=0; // 初始化
  for(int i=0;i<m;i++){
    int u,v,w; cin>>u>>v>>w;
    d[u-1][v-1]=d[v-1][u-1]=w;
  } // 建边
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      for(int k=0;k<n;k++)
        if(i!=j&&i!=k&&j!=k)
          d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
  // Floyd 算法预处理最短路
  if(d[0][n-1]==2e18)cout<<"inf\n"; // 可以玩无限久
  else{
    vector<pair<vector<bool>,int> > r;
    priority_queue<pii,vector<pii>,greater<pii> > q;
    for(int i=0;i<n;i++)
      if(d[0][i])q.emplace(d[0][i],i);
      else b[i]=true;
    while(!q.empty()&&!b[n-1]){
      int u=q.top().second; q.pop();
      if(b[u])continue;
      r.emplace_back(b,d[0][u]-c),c=d[0][u];
      for(int i=1;i<n;i++)
        if(d[0][i]==d[0][u])b[i]=true; // 打标记
    } // 每次取出剩下的中与 1 最短路最小的几个数
    cout<<d[0][n-1]<<' '<<r.size()<<endl;
    for(auto [x,y]:r){
      for(bool i:x)cout<<i;
      cout<<' '<<y<<endl;
    }
  }
  return 0;
}