P3141 [USACO16FEB] Fenced In P题解
题目
如果此题数据要小一点，那么我们可以用克鲁斯卡尔算法通过，但是这个数据太大了，空间会爆炸，时间也会爆炸。
我们发现，如果用 MST 做，那么很多边的边权都一样，我们可以整行整列地删除。
我们造一个样例解析一下：
+-+--+---+
| | | |
+-+--+---+
| | | |
| | | |
+-+--+---+
首先，我们删除第一列的栅栏：
+-+--+---+
| | | |
+ +--+---+
| | | |
| | | |
+-+--+---+
此时答案是 1 1 1。
再删除第一排的栅栏:
+-+--+---+
| |
+ +--+---+
| | | |
| | | |
+-+--+---+
此时答案是 3 3 3。
我们继续删除第二列的栅栏：
+-+--+---+
| |
+ + +---+
| | | |
| | | |
+-+--+---+
此时答案是 5 5 5。
我们继续删除第二行的栅栏：
+-+--+---+
| |
+ + +---+
| |
| |
+-+--+---+
此时答案是 9 9 9。
我们把第三列的栅栏删除，由于之前删除的两行栅栏导致第三列栅栏少删除一个，不用删除。
你可以继续造更大的数据发现规律：
我们先把每一列，每一行的栅栏长度算出来，从小到达排序，然后用双指针算法，两个指针 i i i 和 j j j，第一个记录统计到哪一行，第二个记录统计到哪一列，这两个变量的初始值应该为 2 2 2，然后把第一列，第一行栅栏删除。讨论时，如果我们当前讨论的行比列要短，就删除 m − j + 1 m-j+1 m−j+1 个栅栏，因为之前删除的栅栏导致我们现在不用删除一些栅栏。反之，同理，就是 n − i + 1 n-i+1 n−i+1 个栅栏。如果一个指针走完了，那么所有的都是联通的，就不用再循环了。时间复杂度 O ( n ) O(n) O(n)，通过。
AC Code：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int h, w, n, m;
int a[300000], b[300000];
long long a1[300000], b1[300000];
long long ans;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> h >> w >> n >> m;for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i <= m; i ++) cin >> b[i];sort(a + 1, a + n + 1);sort(b + 1, b + m + 1);n++;a[n] = h;m++;b[m] = w;for (int i = 1; i <= n; i ++) {a1[i] = a[i] - a[i - 1];}for (int i = 1; i <= m; i ++) {b1[i] = b[i] - b[i - 1];}sort(a1 + 1, a1 + n + 1);sort(b1 + 1, b1 + m + 1);
// for (int i = 1; i <= n; i ++) {
// cout << a1[i] << ' ';
// }
// cout << '\n';
// for (int j = 1; j <= m; j ++) {
// cout << b1[j] << ' ';
// }
// cout << '\n';int i = 2, j = 2;ans = a1[1] * (m - 1);ans += b1[1] * (n - 1);while (i <= n && j <= m) {if (a1[i] < b1[j]) {ans += a1[i] * (m - j + 1);i++;}else {ans += b1[j] * (n - i + 1);j++;}}cout << ans;return 0;
}