自动搬运

查看原文

来自洛谷，原作者为

	hehezhou **

搬运于2025-08-24 22:10:11，当前版本为作者最后更新于2019-05-21 13:51:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先让我们证明一个结论：存在一个最优解小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;
}