题意  一个城市原来有l个村庄 e1条道路  又增加了n个村庄 e2条道路  后来后销毁了m个村庄  与m相连的道路也销毁了  求使所有未销毁村庄相互连通最小花费  不能连通输出what a pity!

还是很裸的最小生成树  把销毁掉的标记下  然后prim咯  结果是无穷大就是不能连通的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 300;
int mat[N][N], des[N], d[N], ans, n, m;

void prim()
{
    memset(d, 0x3f, sizeof(d));
    int s = 0;  while(des[s]) ++s;
    d[s] = -1;
    int cur = s, next = n;
    for(int k = 1; k < n - m; ++k)
    {
        for(int i = 0; i < n; ++i)
        {
            if(des[i] || d[i] < 0) continue;
            d[i] = min(d[i], mat[cur][i]);
            if(d[i] < d[next]) next = i;
        }
        ans += d[next], d[next] = -1, cur = next, next = n;
    }
}

int main()
{
    int cas, l, e1, e2, a, b, c;
    scanf("%d", &cas);
    while(cas--)
    {
        memset(mat, 0x3f, sizeof(mat));
        memset(des, 0, sizeof(des));
        scanf("%d %d", &l, &e1);
        for(int i = 0; i < e1; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            if(c < mat[a][b]) mat[a][b] = mat[b][a] = c;
        }

        scanf("%d %d", &n, &e2);
        for(int i = 0; i < e2; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            if(c < mat[a][b]) mat[a][b] = mat[b][a] = c;
        }

        n = n + l;
        scanf("%d", &m);
        for(int i = 0; i < m; ++i)
        {
            scanf("%d", &a);
            des[a] = 1;
        }

        ans = 0;  prim();
        if(ans < d[n]) printf("%d\n", ans);
        else printf("what a pity!\n");
    }
    return 0;
}

The plan of city rebuild

2
4 5
0 1 10
0 2 20
2 3 40
1 3 10
1 2 70
1 1
4 1 60
2
2 3
3 3
0 1 20
2 1 40
2 0 70
2 3
0 3 10
1 4 90
2 4 100
0

70
160

HDU 3080 The plan of city rebuild(除点最小生成树)

原文：http://blog.csdn.net/acvay/article/details/41183187