P2916 [USACO08NOV] 安慰奶牛 Cheering up the Cow#
题目描述#
約翰は N 個の牧場を持っており、それぞれ 1 から N までの番号が付けられています。各牧場には 1 頭の牛が住んでいます。これらの牧場を結ぶ P 本の道路があり、それぞれの道路は双方向です。j 番目の道路は牧場 Sj と Ej を結び、通行には Lj の時間がかかります。2 つの牧場の間には最大で 1 本の道路しかありません。約翰は、各牧場が連結された状態でできるだけ多くの道路を取り除くことを計画しています。
約翰は、道路が取り壊されると牛たちはとても悲しむことを知っているため、彼は取り壊し後すぐに彼らをなだめる計画を立てています。約翰は、出発する牧場を任意に選び、彼のなだめる作業を開始することができます。彼がすべての牛を訪れた後、出発地に戻る必要があります。彼が牧場 i を通過するたびに、彼は Ci の時間をかけて牛と話さなければなりません。以前に作業を行った場合でも、再び話をする必要があります。約翰は出発時と帰りに、出発地の牛とも話さなければなりません。約翰が道路をどれだけ取り壊す必要があるか、そして牛たちをなだめるためにかかる最小の時間を計算してください。
入出力形式#
入力形式：
* 1 行目：2 つの整数 N と P がスペースで区切られています。
* 2 行目から N+1 行目：各行には 1 つの整数 Ci が含まれています。
* N+2 行目から N+P+1 行目：各行には 3 つの整数 Sj、Ej、および Lj がスペースで区切られています。
出力形式：
* 1 行目：1 つの整数、すべての牛を訪れるのにかかる合計時間（寝ている牧場の牛を 2 回訪れることを含む）
入出力例#
入力例 #1：
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12
出力例 #1：
176
考え方#
私は、道路の重みを歩く時間に 2 倍し、両端の時間に 1 倍加えたものに設定すると、最小生成木の選択結果（例）と例の答えが同じであることに気づきました。
したがって、どのエッジを選択するかを求めた後、dfs を使用して合計時間を計算することを考えました。
hqxさんに伝えると、彼は厳密な推論を経て、エッジの重みを 2 倍の道路時間に 1 倍の両端時間を加えたものに設定するだけで、最小生成木の合計に最も少ない話す時間を加えると、最短の合計時間になることがわかりました。
理由は、往復で各エッジが 2 回通過する（例を見たり、データを作成したりしてください）、それぞれのエッジが 2 つの端点の時間を消費することです。出発点は 1 回多く計算されます。
HQX さん、TQL！
CODE#
#include<cstdio>
#include<iostream>
#include<algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int MAXN=1000000+5,INF=0x3f3f3f3f;
int n,p;
int c[10005];
struct tu
{
struct edge
{
int p1,p2,w,a;
friend bool operator <(edge x,edge y)
{
return x.a<y.a;
}
} b[MAXN];
int newpe;
int head[MAXN];
int fa[MAXN];
bool v[MAXN];
void insert(int p1,int p2,int w)
{
b[++newpe].p1=p1;
b[newpe].p2=p2;
b[newpe].w=w;
b[newpe].a=2*b[newpe].w+c[p1]+c[p2];
}
int zxscs(void)//最小生成树（原谅我不会打克鲁斯卡尔）
{
sort(b+1,b+1+newpe);
for(int i=1;i<=n;++i)
{
fa[i]=i;
}
int cnt=0;
int tot=0;
for(int i=1;i<=newpe;++i)
{
if(doFind(b[i].p1)!=doFind(b[i].p2))
{
++cnt;
tot+=b[i].a;
doUnion(b[i].p1,b[i].p2);
}
if(cnt==n-1)
{
return tot;
}
}
return 0;
}
void doUnion(int x,int y)
{
x=doFind(x);
y=doFind(y);
fa[x]=y;
}
int doFind(int x)
{
if(fa[x]==x)return x;
else return fa[x]=doFind(fa[x]);
}
} mp;
int main(void)
{
scanf("%d%d",&n,&p);
int minc=INF;
for(int i=1;i<=n;++i)
{
scanf("%d",c+i);
minc=min(c[i],minc);
}
for(int i=1;i<=p;++i)
{
int p1,p2,w;
scanf("%d%d%d",&p1,&p2,&w);
mp.insert(p1,p2,w);
}
int ans;
ans=mp.zxscs();
ans+=minc;
printf("%d\n",ans);
return 0;
}