【强连通+背包】CF1763E

偏执的太偏执、 2024-02-21 12:02 39阅读 0赞

[Problem - E - Codeforces][]

题意

![11300a890b0c4b5ca947b1baacee89de.png][]

思路

首先，先考虑第一个条件，要保证是p个节点互相到达且节点数最少，一定是个强连通，**图的形态一定就是和强连通相关的。**

然后，因为在这个前提上，要让单向节点数尽可能多，那就考虑将这些强连通分量用有向边连接

那么用哪些多大的强连通连接在一起就用背包处理一下就好了，因为要让节点数尽可能少，代价就是节点数，价值就是每个团的点对数，即x \* (x - 1) / 2

然后背包完之后考虑第二问，求单向点数

把背包的方案求出来之后直接计算贡献即可，具体看代码

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 2e5 + 10;
    constexpr int mod = 998244353;
    constexpr int Inf = 0x3f3f3f3f;
    
    int n;
    int f[N];
    int dp[N];
    
    int calc(int x) {
    	return x * (x - 1) / 2;
    }
    void solve() {
    	std::cin >> n;
    	memset(dp, 0x3f, sizeof(dp));
    	dp[0] = 0;
    	for (int i = 2; i <= 633; i ++) {
    		int w = calc(i);
    		for (int j = w; j <= n; j ++) {
    			if (dp[j] > dp[j - w] + i) {
    				dp[j] = dp[j - w] + i;
    				f[j] = i;
    			}
    		}
    	}
    	std::vector<int> b;
    	for (int i = n; i; i -= calc(f[i])) b.push_back(f[i]);
    	int sum = 0, ans = 0;
    	for (auto x : b) {
    		ans += sum * x;
    		sum += x;
    	}
    	std::cout << dp[n] << " " << ans << "\n";
    }
    signed main() {
    	std::ios::sync_with_stdio(false);
    	std::cin.tie(nullptr);
    
    	int t = 1;
    	while (t--) {
    		solve();
    	}
    	return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1763/problem/E
[11300a890b0c4b5ca947b1baacee89de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/359f7292846f4edb93f9bcad1c8d1895.png