[ABC270F] Transportation

题意

有 (n) 个点，有 (m) 条可以加上的边，如果两个点同时建立了一种东西，那么也算连了一条边，每条边都有个代价，每个点建一个东西也有不同的代价，问想要让图连通，最少需要多少代价。

思路

显然是最小生成树，但是由于可以见两种东西，所以比较难处理，所以可以将这个点权变成一条边，这样就好处理了，所以可以额外开两个点 (n + 1) 和 (n + 2)，可以将所有点的两种建东西的代价作为边权连向它们，但可以不建东西，所以做四次最小生成树即可。

代码

#include 
#include 

using namespace std;

const int MaxN = 2e5 + 10;

struct S {
  int u, v, w;

  bool operator> n >> m;
  for (int i = 1, u; i > u;
    a[++tot] = {i, n + 1, u};
  }
  for (int i = 1, u; i > u;
    a[++tot] = {i, n + 2, u};
  }
  for (int i = 1, u, v, w; i > u >> v >> w;
    a[++tot] = {u, v, w};
  }
  sort(a + 1, a + tot + 1);
  for (int u = 0; u > 1) & 1) != 1) || (a[i].v == n + 2 && (u & 1) != 1)) {
        continue;
      }
      if (FindFather(a[i].u) != FindFather(a[i].v)) {
        sum += a[i].w, vis[a[i].u] = vis[a[i].v] = 1;
        insert(a[i].u, a[i].v);
      }
    }
    int cnt = 0;
    for (int i = 1; i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 【Redis】NoSQL 数据库 ② ( NoSQL 数据库特点 | NoSQL 数据库适用场景 | 常见的 NoSQL 数据库 | Redis | MongoDB | 数据库排名 )

文章目录 一、NoSQL 数据库特点 二、NoSQL 数据库适用场景 三、常见的 NoSQL 数据库 ( Redis | MongoDB ) 四、数据库排名 一、NoSQL 数据库特点 NoSQL 全称 Not Only SQL , 称为 ” 非关系型数据库 …