题解 P5382 [THUPC2019]改善生活

发表于 | 分类于 | 阅读次数：

题面

首先让我们证明一个结论：存在一个最优解小Z只引出了一个话题
感性理解：我多选了一个相当与把两个答案进行某种意义下的平均，不会变的更优

证明：
若$S_1$表示小Z引出话题的集合，我们只要证明向$S_1$中插入集合$S_2$不会变的更优($S1\cap S_2=\emptyset$)(新方案要么不优于只选$S_1$的方案，要么不优于只选$S_2$的方案)

设当只选$S_1$时,答案为$ans_1$,$sum(k)=a_k$,
当只选$S_2$时,答案为$ans_2$,$sum(k)=b_k$(令$ans_1\leq ans_2$)
当选$S_1\cup S_2$时,答案为$ans_3$,$sum(k)=c_k$

显然$c_1=a_1+b_1$
任意$k\in [2,n] a_k\leq a_1*ans_1$

任意$k\in [2,n] b_k\leq b_1*ans_2$

任意$k \in [2,n] c_k \leq a_k+b_k\leq a_1\times ans_1+b_1\times ans_2$

(话题可能有交集)

证毕

所以只要枚举选的点，然后算答案即可(我的代码实现求了个传递闭包)

Talk is cheap, show me the code.

码风丑，请大佬轻喷

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
#include <bits/stdc++.h>
using namespace std;
int mp[710][710], n, m, c[710], w[710];
int cnt[710], ans;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", c + i);
    for(int i = 1; i <= n; i++) scanf("%d", w + i);
    for(int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        mp[u][v] = 1;
    }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) mp[i][j] |= mp[i][k] & mp[k][j];
    //没有错，n ^ 3 就是能过700 (700 ^ 3 = 3e8)
    for(int i = 1; i <= n; i++) {
        if(c[i] == 1) {
            memset(cnt, 0, sizeof cnt);
            for(int j = 1; j <= n; j++) if(mp[i][j]) cnt[c[j]] += w[j];
            for(int j = 2; j <= n; j++) ans = max(ans, cnt[j] / w[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}