最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天消息！AcWing. 1146 新的开始

来源：博客园


【资料图】

传送门

题目大意

\(\qquad\)给一张图，每个点有对应的点权，每条边有对应的边权。可以有如下几种选择：

\(\qquad\quad\)\(1.\)选择一个没通电的点，花费\(v_i\)。\(\qquad\quad\)\(2.\)将两个点连边（要有一点通电），边权\(p_{i,j}\)\(\qquad\)经过上述操作之后，要使全图通电

解题思路

\(\qquad\)一眼看上去有一些麻烦，原因是有点权的存在，导致了这个问题求解需要从点和边两方面去考虑，而且还有“通电”这一限制，所以就导致这题看起来很困难。

\(\qquad\)那我们就可以换一个角度思考，能否将点权转化为边权呢？联系之前求解最短路用的虚拟源点，我们可以把所有点向超级源点\(S\)连一条边，权值是它的点权\(v_i\)，这样我们选择点变成了选择边，这样我们再来看通电这一个限制如何解决。

\(\qquad\)当我们假定\(S\)源点是通电的（这样操作\(1\)才能进行），它连向的点就是新开的矿井，这样操作\(1\)相当于两个点通电->不通电的连线，边权是\(v_i\)。

\(\qquad\)由于一开始这张图上的所有点都是不通电的，所以操作\(1\)至少操作\(1\)次，在经历了\(1\)次操作\(1\)之后，这张图上要通电，就是将其它点和已经通电的点连接，当已经通电的点只有\(1\)个时，剩下的点中选出一个，要么和\(S\)连边（操作\(1\)），要么和这个通电的点连边，所以我们这个包含了\(S\)的图通电之后，必定是连通的，那最小费用就是这张图中的最小生成树，用\(Kruskal\)算法跑就行了。

关于建图

\(\qquad\)这题的建图无非两种\(\qquad\)一开始读入点权的时候顺便把点和\(S\)连边，后面读入边权正常连边就行，对于\(p_{i,j}\)，连一条\(i <- >j\)的无向边，边权为\(p_{i,j}\)。用一个变量\(ecnt\)统计边数即可（当然，也可以使用vector）

代码

普通

#include #include using namespace std;const int N = 310, M = N * (N + 1);int p[M], n, S, ecnt;struct Edge {    int u, v, w;    bool operator <(const Edge& W) const {        return w < W.w;    }} edge[M];int find(int x) {    if (x != p[x]) p[x] = find(p[x]);    return p[x];}int main() {    scanf("%d", &n);        for (int i = 1; i <= n; i ++ )     {        int x;        scanf("%d", &x);        edge[++ ecnt] = {0, i, x};    }        for (int i = 1; i <= n; i ++ )         for (int j = 1; j <= n; j ++ )         {            int x; scanf("%d", &x);            edge[++ ecnt] = {i, j, x};        }        sort(edge + 1, edge + ecnt + 1);    for (int i = 1; i <= ecnt; i ++ ) p[i] = i;        int res = 0;    for (int i = 1; i <= ecnt; i ++ )     {        int fu = find(edge[i].u), fv = find(edge[i].v);        if (fu == fv) continue ;                p[fu] = fv, res += edge[i].w;    }    printf("%d\n", res);        return 0;}

vector

#include #include using namespace std;const int N = 310, M = N * (N + 1);int p[M], n, S, ecnt;struct Edge {    int u, v, w;    bool operator <(const Edge& W) const {        return w < W.w;    }} ; vector edge;int find(int x) {    if (x != p[x]) p[x] = find(p[x]);    return p[x];}int main() {    scanf("%d", &n);        for (int i = 1; i <= n; i ++ )     {        int x;        scanf("%d", &x);        edge.push_back({S, i, x});    }        for (int i = 1; i <= n; i ++ )         for (int j = 1; j <= n; j ++ )         {            int x; scanf("%d", &x);            edge.push_back({i, j, x});        }    ecnt = edge.size();        sort(edge.begin(), edge.end());    for (int i = 0; i <= ecnt; i ++ ) p[i] = i;        int res = 0;    for (int i = 0; i < ecnt; i ++ )     {        int fu = find(edge[i].u), fv = find(edge[i].v);        if (fu == fv) continue ;                p[fu] = fv, res += edge[i].w;    }    printf("%d\n", res);        return 0;}

关键词： 换一个角度 我们再来看 这个问题