题目描述

你在玩电子游戏的时候遇到了麻烦。。。。。。 你玩的游戏是在一个虚拟的城市里进行，这个城市里有n个点，都从0~n-1编了号，每两个点之间有且仅有一条路径。现在，你的敌人到这个城市来踩点了!!!为了阻止他们更好的踩点， 你决定切断他们所有踩点人员的联系，使他们孤军作战，然后在各个击破。但是这就要切断某些街道，而你每切断一条路，市民就会产生相对的不满值，不满值越大，城市的和谐度就越小。所以你现在需要知道为了使踩点人员所在的点两两之间不联通所切断的边产生的最小不满值是多少？

---

思路

将损失的价值从大到小排序，每次加入一条边，然后暴力判断是不是冲突。用并查集判断两个点是否属于同一集合，属于的话直接取这条边，就不用判断了

---

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxn 10001
#define fill(x, y) memset(x, y, sizeof(x))
struct arr
{
    int x, y, w;
}a[maxn];
struct edge
{
    int to, next;
}e[maxn];
int l = 0;
int b[maxn], f[maxn], ls[maxn];
bool v[maxn];
int cmp(arr a, arr b)
{
    return a.w > b.w;
}
int find(int x)
{
    if (f[x] == x) return x;
    f[x] = find(f[x]);
    return f[x];
}
int insert(int x, int y)
{
    if (find(x) != find(y))
    {
        f[find(x)] = find(y);
        return 0;
    }
    return 0;
}
int check()
{
    bool fl[51];
    fill(fl, false);
    queue t;
    for (int i = 1; i <= l; i++)
    {
        if (fl[b[i]] == 0) 
        {
            fl[b[i]] = 1;
            t.push(b[i]);
            while (!t.empty())
            {
                int now = t.front();
                t.pop();
                for (int j = ls[now]; j; j = e[j].next)
                {
                    if (v[e[j].to] == 1 && fl[e[j].to] == 0) return 0;
                    if (fl[e[j].to] == 0)
                    {
                        fl[e[j].to] = 1;
                        t.push(e[j].to);
                        if (v[e[j].to] == 1) return 0;
                    }
                }
            }
        }
    }
    return 1;
}
int main()
{
    int n, tot = 0;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].w);
        a[i].x++; a[i].y++;
        tot += a[i].w;
    }
    int x;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    while (~scanf("%d", &x))
    {
        x++;
        v[x] = 1;
        b[++l] = x;
    }
    sort(a + 1, a + n, cmp);
    int  ans = 0, p = 0;
    for (int i = 1; i < n; i++)
    {
        if (find(a[i].x) != find(a[i].y))
        {
            e[++p] = (edge) {a[i].y, ls[a[i].x]};
            int xx = ls[a[i].x];
            ls[a[i].x] = p;
            e[++p] = (edge) {a[i].x, ls[a[i].y]};
            int yy = ls[a[i].y];
            ls[a[i].y] = p;
            if (check())
            {
                ans += a[i].w;
                insert(a[i].x, a[i].y);
            }
            else
            { 
                p -= 2;
                ls[a[i].x] = xx;
                ls[a[i].y] = yy;
            }
        }
        else ans += a[i].w;
    }
    printf("%d\n", tot - ans);
}