UVA 1151 Buy or Build ( 枚舉 + 最小生成樹 )

UVa Online Judge
先計算完全沒有用子網路集的生成樹，留下可能用到的 n - 1 條邊，再二進位枚舉子網路的可能子集。這麼做可以大大減少考慮不可能用到的邊。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;
const int MAXM = MAXN * MAXN / 2;
const int MAXQ = 8 + 2;

struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}
    bool operator < (const Edge &oth) const{
        return w < oth.w;
    }
} es[MAXM];

struct UnionFind{
    int fa[MAXN];
    void init(int n){
        for(int i = 0; i <= n; ++i)
            fa[ i ] = i;
    }
    int find(int x){ return x == fa[ x ] ? x : fa[x] = find( fa[x] ); }
    bool unite(int a, int b){
        int x = find( a ), y = find( b );
        if( x == y ) return false;
        fa[ x ] = y; return true;
    }
} uf;

int n, m, q;
int subnet_size[MAXQ], subnet_cost[MAXQ], subnet[MAXQ][MAXN];
int x[MAXN], y[MAXN];

struct Kruskal{
    vector<Edge> chose_edge;
    int solveWithoutSubnet(){
        chose_edge.clear();
        uf.init( n );
        sort( es, es + m );
        int cost = 0;
        for(int i = 0; i < m; ++i){
            int u = es[i].u, v = es[i].v, w = es[i].w;
            if( uf.unite( u, v ) ){
                cost += w;
                chose_edge.push_back( es[ i ] );
                if( chose_edge.size() == n - 1 ) break;
            }
        }
        assert( chose_edge.size() == n - 1 );
        return cost;
    }
    int solveWithSubnets(int S){
        uf.init( n );
        int cost = 0, picked = 0;
        for(int i = 0; i < q; ++i)
            if( S & ( 1 << i ) ){
                cost += subnet_cost[ i ];
                for(int j = 0; j < subnet_size[ i ]; ++j)
                    for(int k = j + 1; k < subnet_size[ i ]; ++k)
                        if( uf.unite( subnet[ i ][ j ], subnet[ i ][ k ] ) )
                            ++picked;
            }
        if( picked == n - 1 ) return cost;
        for(Edge &e: chose_edge){
            int u = e.u, v = e.v, w = e.w;
            if( uf.unite( u, v ) ){
                cost += w;
                if( ++picked == n - 1 ) break;
            }
        }
        assert( picked == n - 1 );
        return cost;
    }
} mst;

int euDis2(int a, int b){
    int dx2 = ( x[ a ] - x[ b ] ) * ( x[ a ] - x[ b ] );
    int dy2 = ( y[ a ] - y[ b ] ) * ( y[ a ] - y[ b ] );
    return dx2 + dy2;
}

void getEdgeCost(){
    m = 0;
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
            es[ m++ ] = Edge( i, j, euDis2( i, j ) );
}

void solve(){
    getEdgeCost();
    int ans = mst.solveWithoutSubnet();
    for(int i = 1; i < ( 1 << q ); ++i)
        ans = min( ans, mst.solveWithSubnets( i ) );
    printf("%d\n", ans);
}

int main(){
    int T; scanf("%d" ,&T);
    while( T-- ){
        scanf("%d%d",&n, &q);
        for(int i = 0; i < q; ++i){
            scanf("%d%d", &subnet_size[i], &subnet_cost[i]);
            for(int j = 0; j < subnet_size[i]; ++j)
                scanf("%d", &subnet[i][j]);
        }
        for(int i = 1; i <= n; ++i) // citits are 1 idx
            scanf("%d%d", &x[i], &y[i]);
        solve();
        if( T ) puts("");
    }
    return 0;
}