USACO08OCT打井WateringHole

发表于
  • Description
    John决定将水引入到他的$N(1\le N\le 300)$个牧场。
    他准备通过挖若干井，并在各块田中修筑水道来连通各块田地以供水。
    在第$i$田中挖一口井需要花费 $ W_i (1\le W_i \le 10^5) $ 元。
    连接$i$号田与$j$号田需要 $ P_{ij} (1\le P_{ij} \le 10^5) $ 元。
    请求出农民John 需要为连通整个牧场的每一块田地所需要的钱数。

  • 这个题好普

  • Solution1

    • 每个点加供水系统有两种做法，连接某个已经在系统中的点，或者新建一个水井。
    • 新建一个超级源点，向所有点连边权为建水井花费的边。
    • 对于这$N+1$个点直接做MST即可。
    • 时间复杂度$O(MST)$

  • Solution2

    • 类似Prim的方法？
    • 欺负数据范围，直接枚举哪个点必须放。
    • 时间复杂度$O(N^3)$
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
#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 = 305, zhf = 1<<29 ;
int n, m, w[maxn], dis[maxn], g[maxn][maxn] ;
bool inq[maxn] ;
int calc ( int x ) {
    memset ( inq, 0, sizeof inq ) ;
    int i, j, minn, rec = 0 ;
    for ( i = 1 ; i <= n ; i ++ )
        if ( i != x ) dis[i] = min(g[x][i], w[i]) ;
        else dis[i] = w[i] ;
    //printf ( "start : %d\n", x ) ;
    inq[x] = 1 ;
    for ( i = 2 ; i <= n ; i ++ ) {
        minn = zhf ;
        for ( j = 1 ; j <= n ; j ++ )
            if ( !inq[j] && dis[j] < minn ) {
                minn = dis[j] ;
                x = j ;
            }
        inq[x] = 1 ;
        //printf ( "insert %d dis=%d\n", x, dis[x] ) ;
        rec += dis[j] ;
        for ( j = 1 ; j <= n ; j ++ )
            if ( !inq[j] ) dis[j] = min(dis[j], g[x][j]) ;
    }
    for ( i = 1 ; i <= n ; i ++ ) rec += dis[i] ;
    //for ( i = 1 ; i <= n ; i ++ ) printf ( "%d ", dis[i] ) ; printf ( "rec=%d\n", rec ) ;
    return rec ;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen ( "P1550.in", "r", stdin ) ;
    freopen ( "P1550.out", "w", stdout ) ;
#endif
    int i, j, ans = zhf ;
    Read(n) ;
    for ( i = 1 ; i <= n ; i ++ ) Read(w[i]) ;
    for ( i = 1 ; i <= n ; i ++ )
        for ( j = 1 ; j <= n ; j ++ )
            Read(g[i][j]) ;
    for ( i = 1 ; i <= n ; i ++ )
        ans = min(ans, calc(i)) ;
    printf ( "%d\n", ans ) ;
    return 0 ;
}