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