首页 > 其他分享 >CF1149D Abandoning Roads 题解

CF1149D Abandoning Roads 题解

时间:2024-04-06 18:57:31浏览次数:25  
标签:连通 emplace vis int 题解 leq Roads CF1149D id

Description

一张 \(n\) 个点 \(m\) 条边的无向图,只有 \(a,b\) 两种边权(\(a<b\)),对于每个 \(i\),求图中所有的最小生成树中,从 \(1\) 到 \(i\) 距离的最小值。

\(2\leq n\leq 70,n-1\leq m\leq 200,1\leq a<b\leq 10^7\)。

Solution

先考虑一个最小生成树是什么样的形态,显然保留边权为 \(a\) 的边后形成的连通块和原图保留 \(a\) 边的连通块完全相同,并且树中连接连通块之间的边都是 \(b\) 边。

所以树上两点的简单路径一定是先走 \(a\) 再走 \(b\) 再走 \(a\),以此类推,并且如果出了一个连通块就不会再回来,容易发现在原图中如果存在一条这样的 \(1\) 到 \(i\) 的路径,那么在新树中一定也存在。

这样就可以 dp 了,设 \(f_{s,i}\) 表示已经出了 \(s\) 这个集合的所有连通块,并且当前在 \(j\) 的最短路。跑 dijkstra 即可。

时间复杂度:\(O(2^nn)\)。

考虑优化。

注意到对于一个大小不超过 \(3\) 的连通块,如果出了它再走回来一定没有直接走连通块内的边优,所以这些连通块不用记到状态里,则状态数总共就只有 \(2^{\frac{n}{4}}\) 个了。

时间复杂度:\(O(2^{\frac{n}{4}}n)\)。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 75, kMaxS = (1 << 18);

int n, m, a, b, cnt, tot;
int g[kMaxN][kMaxN], id[kMaxN], f[kMaxN][kMaxS];
bool vis[kMaxN];
std::vector<int> vec;

void dfs(int u) {
  vec.emplace_back(u), vis[u] = 1;
  for (int i = 1; i <= n; ++i)
    if (g[u][i] == a && !vis[i])
      dfs(i);
}

void dijkstra() {
  static bool vis[kMaxN][kMaxS] = {0};
  memset(f, 0x3f, sizeof(f));
  std::priority_queue<std::tuple<int, int, int>> q;
  f[1][0] = 0, q.emplace(0, 1, 0);
  for (; !q.empty();) {
    auto [d, i, s] = q.top(); q.pop();
    if (vis[i][s]) continue;
    vis[i][s] = 1;
    for (int j = 1; j <= n; ++j) {
      if (!g[i][j]) continue;
      int t = s;
      if (id[j] < cnt) {
        if (s >> id[j] & 1) continue;
        if (id[j] == id[i]) {
          if (g[i][j] == a && f[j][t] > f[i][s] + g[i][j]) {
            f[j][t] = f[i][s] + g[i][j], q.emplace(-f[j][t], j, t);
          }
        } else {
          if (id[i] < cnt) t |= (1 << id[i]);
          if (f[j][t] > f[i][s] + g[i][j]) {
            f[j][t] = f[i][s] + g[i][j], q.emplace(-f[j][t], j, t);
          }
        }
      } else {
        if (id[j] == id[i]) {
          if (g[i][j] == a && f[j][t] > f[i][s] + g[i][j]) {
            f[j][t] = f[i][s] + g[i][j], q.emplace(-f[j][t], j, t);
          }
        } else {
          if (id[i] < cnt) t |= (1 << id[i]);
          if (f[j][t] > f[i][s] + g[i][j]) {
            f[j][t] = f[i][s] + g[i][j], q.emplace(-f[j][t], j, t);
          }
        }
      }
    }
  }
}

void dickdreamer() {
  std::cin >> n >> m >> a >> b;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    g[u][v] = g[v][u] = w;
  }
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) continue;
    dfs(i);
    if (vec.size() >= 4) {
      for (auto x : vec) id[x] = tot;
      ++cnt, ++tot;
    }
    vec.clear();
  }
  std::fill_n(vis + 1, n, 0);
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) continue;
    dfs(i);
    if (vec.size() <= 3) {
      for (auto x : vec) id[x] = tot;
      ++tot;
    }
    vec.clear();
  }
  dijkstra();
  for (int i = 1; i <= n; ++i)
    std::cout << *std::min_element(f[i], f[i] + (1 << cnt)) << ' ';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:连通,emplace,vis,int,题解,leq,Roads,CF1149D,id
From: https://www.cnblogs.com/Scarab/p/18117733

相关文章

  • P10245 Swimming Pool题解
    P10245SwimmingPool题意给你四条边\(abcd\),求这四条边是否可以组成梯形。思路这显然是一道简单的普通数学题。判断是否能构成梯形只需看四条边是否能满足,上底减下底的绝对值小于两腰之和且大于两腰之差。证明过程如图,\(AB=a\),\(BC=b\),\(CD=c\),\(AD=d\)。过点\(D\)......
  • P10244 String Minimization 题解
    P10244StringMinimization题意给你四个长度为\(n\)的字符串,分别是\(abcd\)。你可以选择一个\(i\)然后交换\(a[i]\)和\(c[i]\),并交换\(b[i]\)和\(d[i]\)。求在\(a\)的字典序尽量小的前提下,\(b\)字典序最小是什么。思路本题并不难。只需要在\(a[i]>c[i]\)......
  • CF1929B Sasha and the Drawing 题解
    CF1929B题意给定一个\(n\timesn\)的正方形,已知正方形最多有\(4\timesn-2\)条对角线,要求要有至少\(k\)条对角线经过至少一块黑色方格,求至少要将几条对角线涂成黑色。分析分类讨论:当\(k<=4\timesn-4\)时,就只需要在上下两侧图就行,所以答案是\([\frac{k}{2}]\)。当......
  • CF301B Yaroslav and Time 题解
    CF301B这不最短路的板子题吗?思路用\(ak\)代表走到第\(k\)点时的可恢复单位时间的值。\(i\)到\(j\)的距离是\(\left(\left|xi-xj\right|+\left|yi-yj\right|\right)\timesd-ak\)。再打一下最短路代码,建议Floyd,因为短。ACCode#include<bits/stdc......
  • CF30D King's Problem? 题解
    CF30D题意有\(n+1\)个点,其中的\(n\)个点在数轴上。求以点\(k\)为起点走过所有点的最短距离,允许重复。思路有两种情况:\(k\)在数轴上(如图1)。\(k\)在第\(n+1\)个点上(如图2)。图1:图2:像第一种情况:一定存在数轴上某点\(k\),使得人先走遍\(1\simk\),回来,再走遍......
  • CF1915B Not Quite Latin Square 题解
    CF1915B题意给出一个\(3\)行\(3\)列的字符矩形,其中每行都有字符ABC各一个组成,现有一个字符未知,求出未知字符。思路就是说每个字符都应该出现\(3\)次,所以我们只要找到出现两次的字符即可。ACCode#include<bits/stdc++.h>usingnamespacestd;intt;chara[10][10......
  • CF916C 题解
    CF916C题解思路思考发现,如果我们让很多边的边权变得非常大,而故意留下\(1\)到\(n\)的某一条路径,使整条路径之和甚至还没有剩下一条边的权值大,这条路径显然就是最短路了。更重要的是,这样构造的结果,这条路径同时还是整张图的最小生成树。这样我们只需要找一个\(100000\)......
  • P6680 [CCO2019] Marshmallow Molecules 题解
    P6680题意一个\(n\)点\(m\)边的图,图无重边,无自环。满足这样一条性质:如果三边互不相等,则三边可以构成三角形。思路思路简单,用集合的思想来做。引用一下K0stlin大佬的性质:题目中的操作等价于将一个点大于某个儿子的儿子们赋给这个儿子(这里的儿子表示这个点有出边连向的......
  • CF1883B Chemistry 题解
    原题传送门思路:如"aba","abba"这样的回文字符串,每个字符的出现次数有以下两种情况:1:全部是偶数(abba)2:只有一个为奇数(aba)于是只要字符出现个数为奇数的个数小于等于k+1即可否则无解ACcode:#include<bits/stdc++.h>usingnamespacestd;intt,n,k,number[50];strings;......
  • CF895C Square Subsets 题解
    看到\(a_i\le70\)后,发现\(n\)啥用没有,因为只需要枚举\(1-70\)选几个即可。看到求完全平方数后,想到分解质因数,由于\(a_i\le70\),所以只有\(19\)个质数,可以进行状压dp。设\(dp_{i,j}\)表示枚举到\(i\),状态为\(j\)的方案数,便有:\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j\o......