手机软件开发和网站开发,淘宝上做网站的信得过吗,安阳房产网,装修公司加盟平台Problem - E - Codeforces
题意 思路
首先#xff0c;先考虑第一个条件#xff0c;要保证是p个节点互相到达且节点数最少#xff0c;一定是个强连通#xff0c;图的形态一定就是和强连通相关的。
然后#xff0c;因为在这个前提上#xff0c;要让单向节点数尽可能多先考虑第一个条件要保证是p个节点互相到达且节点数最少一定是个强连通图的形态一定就是和强连通相关的。
然后因为在这个前提上要让单向节点数尽可能多那就考虑将这些强连通分量用有向边连接
那么用哪些多大的强连通连接在一起就用背包处理一下就好了因为要让节点数尽可能少代价就是节点数价值就是每个团的点对数即x * (x - 1) / 2
然后背包完之后考虑第二问求单向点数
把背包的方案求出来之后直接计算贡献即可具体看代码
#include bits/stdc.h#define int long longconstexpr 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::vectorint 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;
}
