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 <iostream>
#include <algorithm>

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 <iostream>
#include <algorithm>

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> 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;
}