「BZOJ1232」 [Usaco2008Nov]安慰奶牛cheer

problem

Solution

最终的图显然是一棵树

把每条边视作两条有向边。在树的情况下，一定需要走完所有的有向边。除了出发点以外，走一条有向边(u,v)(u,v)对答案的贡献为w(u,v)+c[v]w(u,v)+c[v]，亦即每条无向边对答案的贡献为w(u,v)∗2+c[u]+c[v]w(u,v)*2+c[u]+c[v]，将其作为边权跑最小生成树。生成树的权值加上最小的点权即为答案

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define maxn 10005
#define maxm 100005
using namespace std;
typedef long long ll;
 
int n,m;
int c[maxn];
int ans;
 
struct edge
{
    int u,v,w;
}g[maxm];
 
int prt[maxn];
 
int getroot(int u)
{
    return prt[u]==u?u:prt[u]=getroot(prt[u]);
}
 
bool cmp(const edge &a,const edge &b)
{
    return a.w<b.w;
}
 
void Kruskal()
{
    for(register int i=1;i<=n;++i)
        prt[i]=i;
    sort(g+1,g+m+1,cmp);
    int cnt=0;
    for(register int i=1;i<=m;++i)
    {
        int r1=getroot(g[i].u),r2=getroot(g[i].v);
        if(r1!=r2)
        {
            prt[r1]=r2;
            ++cnt;
            ans+=g[i].w;
        }
        if(cnt==n-1)
            return;
    }
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)
        scanf("%d",&c[i]);
    for(register int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
        g[i].w=g[i].w*2+c[g[i].u]+c[g[i].v];
    }
    Kruskal();
    sort(c+1,c+n+1);
    printf("%d",ans+c[1]);
    return 0;
}