[猫咪们狂欢](Problem - 7488 (hdu.edu.cn))

题目大意

有$n$只猫咪和两棵大小为$n(1\le n\le 1000)$的树。每只猫咪有一个编号$1\sim n$，每棵树的节点编号也是$1\sim n$。在$n$只猫咪中，有$k$只猫咪是狂欢猫。狂欢猫会开派对，而其他猫咪则会睡觉。

每条树的边有一个狂欢值。如果某条边连接的两个节点上都待有狂欢猫，那么这条边的狂欢值就会被计入总狂欢值。要求安排这些猫咪，使得最大化狂欢猫总狂欢值，并输出这个最大值。

解题思路

考虑对从源点向每一个狂欢猫的编号建一个边权为$0$的边，再从所有的狂欢猫编号向汇点建一个边权为$0$的边。对于第一棵树中两端点可被狂欢猫覆盖的边建一个虚拟点，从源点向这个虚拟点建一个边权为狂欢值的边，再从这个虚拟点向所需的狂欢猫的节点建一个边权为正无穷的边，表示这条边不能被割。对于第二棵树也是同样的道理，从狂欢猫的节点向虚拟点建边权正无穷的边，再从此点向汇点建边权为狂欢值的猫。

这样通过建图就将题目转换成了最小割模型，最后跑一遍最小割即可。

参考代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
#define maxn 3010
#define maxm 1010  //需比总边数大
#define int long long
using namespace std;
const double eps = 1e-8;

struct G{
    struct node{
        int v, w, id;   //id记录当前节点处于所在指向节点vector的第几位
        node(int _v, int _w, int _id) : v(_v), w(_w), id(_id) {}
    };
    vector<vector<node>> e;
    int n, S, T;
    vector<int> dep, cur;
    vector<bool> vis;

    G(int n, int S, int T) {
        init(n, S, T);
    }

    void init(int _n, int _S, int _T) {
        n = _n, S = _S, T = _T;
        e.assign(n + 1, vector<node>());
        dep.resize(n + 1);
        cur.resize(n + 1);
        vis.assign(n + 1, false);
    }


    void add(int u, int v, int w) {
        e[u].push_back((node){v, w, (int)e[v].size()});
        e[v].push_back((node){u, 0, (int)e[u].size() - 1});  //建反向边
    }

    bool bfs() {
        dep.assign(n + 1, 0);
        queue<int> q;
        q.push(S);  dep[S] = 1;
        while(q.size()) {
            int t = q.front();  q.pop();
            for (int i = 0; i < e[t].size(); ++i) {
                int tmp = e[t][i].v;
                if(dep[tmp] == 0 && e[t][i].w) {
                    dep[tmp] = dep[t] + 1;
                    q.push(tmp);
                    if(tmp == T)  return true;
                }
            }
        }
        return false;
    }

    int dfs(int u, int mf) {    //同时增广多条路
        if(u == T)  return mf;
        int sum = 0;
        for (int i = cur[u]; i < e[u].size(); ++i) {
            cur[u] = i;
            int v = e[u][i].v;
            if(dep[v] == dep[u] + 1 && e[u][i].w) {
                int f = dfs(v, min(e[u][i].w, mf));
                e[u][i].w -= f;
                e[v][e[u][i].id].w += f;
                sum += f;
                mf -= f;
                if(mf == 0)  break;
            }
        }
        if(!sum)  dep[u] = 0;
        return sum;
    }

    int dinic() {
        int flow = 0;
        while(bfs()) {
            cur.assign(n + 1, 0); //重置是为了走回退边
            flow += dfs(S, 1e18);
        }
        return flow;
    }

    void mincut(int x) {
        vis[x] = true;
        for (auto u : e[x]) {
            if(!vis[u.v] && u.w)  mincut(u.v);
        }
    }
};


void solve() {
    int n, k, sum = 0;
    set<int> s;
    cin >> n >> k;
    G g(3 * n + 1, 0, 3 * n + 1);
    for (int i = 1; i <= k; ++i) {
        int x;  cin >> x;
        g.add(g.S, x, 0);  g.add(x, g.T, 0);
        s.insert(x);
    }
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        if(!s.count(u) || !s.count(v))  continue;
        g.add(g.S, n + i, w);
        g.add(n + i, u, 1e9);  g.add(n + i, v, 1e9);
        sum += w;
    }
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        if(!s.count(u) || !s.count(v))  continue;
        g.add(2 * n + i, g.T, w);
        g.add(u, 2 * n + i, 1e9);  g.add(v, 2 * n + i, 1e9);
        sum += w;
    }
    int res = g.dinic();
    cout << sum - res << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;  cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}