题面不好找放一个吧。
Description
描述
在有$N$个地级市的H省，政府为了城市开发建设，决定先修路，后造房子，以吸引外来人员。一开始每个城市中有$b_i$个住户，而在两个城市$u,v$之间建路需要的代价就是$R$乘以$u,v$两个城市的住户数目之和。建路的目标是使得所有城市相互之间都可达。
建完路之后，就要造房子了，由于$H$省的房产商仅有一家，所以只能一户一户的造房子。不过政府有权利任意安排建造的顺序，在城市i建造一个房子的代价是，$h_i$乘以城市i当前住户数目同城市i周边城市(即通过道路直接相连的)的当前住户数目之和。由于现在房子炙手可热，所以每造好一户，就立刻有用户入住。政府决定最后的目标是每个城市$a_i$个住户。作为政府部门的财务主管，请你计算出最少需要花费多少钱，才可以完成上述要求。
输入格式
第一行一个整数$N$，表示有$N$个城市；
接下来一行有$N$个整数，描述$b$数组，也就是每个城市一开始的住户数；
接下来一行有$N$个整数，描述$a$数组，也就是每个城市最终的住户数；
接下来一行有$N$个整数，描述$h$数组，表示建房费用；
接下来有一个$N*N$的矩阵，第$i$行第$j$个元素表示原来$i$城市和$j$城市是否有路相连。
最后一行一个整数$R$，表示建路的费用。
输出格式
一个整数，表示最小费用。
数据范围与约定
- 对于$100\%$ 的数据，$1 \leq N \leq 50$，$ b[i] \leq a[i] \leq 100000$，$h[i], R \leq 100000$，矩阵是对称的。
Solution
首先思考一个结论，假设有城市$x, y$，对应$b_x,b_y,h_x,h_y$，需要在这两个城市各建若干个房子，那么我们一个一个城市分别完成一定比交错完成优。
证明：
假设$h_x > h_y$，那么先在$x$建应当比在$y$建优，如果每一个城市都只要建两所房子的话，列出式子：
$h_x(b_x + b_y) + h_y(b_x + b_y + 1) + h_x(b_x + b_y + 2) + h_y(b_x + b_y + 3)$
$h_x(b_x + b_y) + h_x(b_x + b_y + 1) + h_y(b_x + b_y + 2) + h_y(b_x + b_y + 3)$
后者减去前者，约掉同类项：
有 $(2h_y + h_x) - (h_y + 2h_x) = h_y - h_x < 0$成立。
需要建两个房子以上的时候可以归纳。
合在一起不好算，我们考虑拆开计算贡献，对于每一个点$x$，它对答案的贡献是$h_x(b_x + (b_x + 1) + (b_x + 2) + ... + (a_x - 1)) + h_x * (sum(y))$ $y$是$x$能直接联通的点。
前面是一个等差数列求和，后面我们枚举所有的边来计算。
按照之前得到的结论，我们对于一条存在的边$(i, j)$，如果$h_i > h_j$就先把$i$的房子建完再把$j$的房子建完，否则就先建$j$。
把已知的边算完之后还要联通可能不连通的若干个联通块，这时候就可以把连边的代价计算到边权里面去做一个最小生成树，$kruskal$轻松跑过。
时间复杂度是跑不满的$O(n^2logn)$，然而$n$的大小非常具有迷惑性。
Code
#include#include #include using namespace std;typedef long long ll;const int N = 55;const int M = 2505;int n, cnt = 0, w[N][N], ufs[N];ll a[N], b[N], c, h[N];struct Pathway { int u, v; ll val; inline Pathway(int nowU = 0, int nowV = 0, ll nowVal = 0LL) { u = nowU, v = nowV, val = nowVal; } friend bool operator < (const Pathway &x, const Pathway &y) { return x.val < y.val; } } path[M];template inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op;}inline void init() { for(int i = 1; i <= n; i++) ufs[i] = i;}int find(int x) { return x == ufs[x] ? x : ufs[x] = find(ufs[x]);}int main() { read(n); for(int i = 1; i <= n; i++) read(b[i]); for(int i = 1; i <= n; i++) read(a[i]); for(int i = 1; i <= n; i++) read(h[i]); char s[N]; for(int i = 1; i <= n; i++) { scanf("%s", s + 1); for(int j = 1; j <= n; j++) if(s[j] == 'Y') w[i][j] = 1; else w[i][j] = 0; } read(c); ll ans = 0LL; int eCnt = 0; init(); for(int i = 1; i <= n; i++) for(int j = 1; j < i; j++) { if(w[i][j]) { if(h[i] < h[j]) ans += h[j] * b[i] * (a[j] - b[j]) + h[i] * a[j] * (a[i] - b[i]); else ans += h[i] * b[j] * (a[i] - b[i]) + h[j] * a[i] * (a[j] - b[j]); int u = find(i), v = find(j); if(u == v) continue; ufs[u] = v; ++eCnt; } else { if(h[i] < h[j]) path[++cnt] = Pathway(i, j, h[j] * b[i] * (a[j] - b[j]) + h[i] * a[j] * (a[i] - b[i]) + (b[i] + b[j]) * c); else path[++cnt] = Pathway(i, j, h[i] * b[j] * (a[i] - b[i]) + h[j] * a[i] * (a[j] - b[j]) + (b[i] + b[j]) * c); } } sort(path + 1, path + 1 + cnt); for(int i = 1; i <= cnt && eCnt < n - 1; i++) { int u = find(path[i].u), v = find(path[i].v); if(u == v) continue; ans += path[i].val; ufs[u] = v; ++eCnt; } for(int i = 1; i <= n; i++) ans += h[i] * (a[i] - b[i]) * (b[i] + a[i] - 1) / 2; printf("%lld\n", ans); return 0;}