题解 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

\forall k\in [2,n]\ a_k\leq a_1*ans_1 \forall k\in [2,n]\ b_k\leq b_1*ans_2 \forall k\in [2,n]\ c_k\leq a_k+b_k$(话题可能有交集)$\leq a_1*ans_1+b_1*ans_2 ans_3=\frac{max_{k\in [2,n]}\{c_k\}}{c_1} \leq max_{k\in [2,n]}\{\frac{a_1*ans_1+b_1*ans_2}{a_1+b_1}\} \leq max_{k\in [2,n]}\{\frac{a_1*ans_2+b_1*ans_2}{a_1+b_1}\} =ans_2

证毕

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

Talk is cheap, show me the code.

码风丑，请大佬轻喷

#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;
}