题解 P5925 【[POI2007]天然气管道Gaz】

2020-01-19 14:17:20


广告


抢了一个首 A

首先可以发现,每个天然气井选哪个中转站对答案没有影响,也就是说只要随便搞一组合法方案,算出来的花费就是答案。

假设第 $i$ 个天然气井选的是第 $p_i$ 个中转站,那么答案为

$$\sum_{i=1}^nx_{p_i}\!'-x_i+y_i-y_{p_i}\!'$$

这个东西显然等于

$$\sum_{i=1}^nx_i\!'-x_i+y_i-y_i\!'$$

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int main() {
    int n=read(); ll ans=0;
    for (re int i=1;i<=n;++i) ans-=read(),ans+=read();
    for (re int i=1;i<=n;++i) ans+=read(),ans-=read();
    printf("%lld\n",ans);
    return 0;
}