USACO08NOV为母牛欢呼CheeringuptheCows

洛谷2916 BZOJ2911

  • 题意
    约翰有$N$个牧场,编号依次为$1$到$N$。每个牧场里住着一头奶牛。连接这些牧场的有$P$条道路,每条道路都是双向的。第$j$条道路连接的是牧场$S_j$和$E_j$,通行需要$L_j$的时间。两牧场之间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。约翰知道,在道路被强拆后,奶牛会非常伤心,所以他计划拆除道路之后就去忽悠她们。约翰可以选择从任意一个牧场出发开始他维稳工作。当他走访完所有的奶牛之后,还要回到他的出发地。每次路过牧场$i$的时候,他必须花$C_i$的时间和奶牛交谈,即使之前已经做过工作了,也要留下来再谈一次。注意约翰在出发和回去的时候,都要和出发地的奶牛谈一次话。请你计算一下,约翰要拆除哪些道路,才能让忽悠奶牛的时间变得最少?
  • Solution
    • 比较显然的一点是,剩下来的东西肯定一棵树。FJ就在树上走来走去。
    • 对于树上的每条边,FJ绝对要走两次,因为他还要回去。
    • 每个点走多少次搞不清,但是当FJ走完$u -> v$时,绝对会和$v$谈一次话。
    • 所以对于边E<u,v>,当u->v时和$v$谈一次,当v->u时和$u$谈一次,所以每条边的花费是w<u,v>+value[u]+value[v]
    • 更改边权后MST即可。
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
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1e4+5, maxm = 1e5+5, zhf = 0x3f3f3f3f ;
int n, m, fa[maxn] ;
struct node {
int u, v, w ;
friend bool operator < ( node a, node b ) {
return a.w < b.w ;
}
} e[maxm] ;
int find ( int x ) { return fa[x] = x==fa[x]? x:find(fa[x]) ; }
int main() {
int i, j, k, x, y, fx, fy ;
int rec = zhf, cnt = 0 ;
Read(n) ; Read(m) ;
for ( i = 1 ; i <= n ; i ++ ) Read(fa[i]), rec = min(rec, fa[i]) ;
for ( i = 1 ; i <= m ; i ++ ) {
Read(e[i].u) ; Read(e[i].v) ; Read(e[i].w) ;
e[i].w <<= 1 ;
e[i].w += fa[e[i].u] + fa[e[i].v] ;
}
sort ( e+1, e+m+1 ) ;
for ( i = 1 ; i <= n ; i ++ ) fa[i] = i ;
for ( i = 1 ; i <= m ; i ++ ) {
x = e[i].u, y = e[i].v ;
fx = find(x) ; fy = find(y) ;
if ( fx == fy ) continue ;
fa[fx] = fy ;
rec += e[i].w ;
if ( ++cnt == n - 1 ) break ;
}
printf ( "%d\n", rec ) ;
return 0 ;
}