1003 NOIP 模拟赛Day2 城市建设

题面不好找放一个吧。

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 <cstdio>
#include <cstring>
#include <algorithm>
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 <typename T>
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
", ans);
    return 0;
}
View Code

    

原文地址:https://www.cnblogs.com/CzxingcHen/p/9740033.html