算法

(贪心,排序) $O(nlogn)$

这道题目的核心，是需要发现如下性质：

不同行、列之间是完全独立的。即不管将哪行、哪列切开，对其余的行列都是没有任何影响的。

因此可以分别考虑行和列。
对于行来说，问题变成：

• 去掉哪 $K$ 行，可以使得最后剩下的行间的边数最少。这里去掉边数最多的 $K$ 行一定是最优的。否则可以将选出的行替换成边数最多的 $K$ 行，且结果不会变差。

时间复杂度

算法瓶颈在排序上，因此时间复杂度是 $O(nlogn)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, m, L, K, D;
PII row[N], col[N];
int q[N];

int main()
{
    cin >> n >> m >> K >> L >> D;

    for (int i = 1; i <= n; i ++ ) row[i].second = i;
    for (int i = 1; i <= m; i ++ ) col[i].second = i;

    while (D -- )
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (abs(x1 - x2) == 1) row[min(x1, x2)].first ++ ;
        else col[min(y1, y2)].first ++ ;
    }

    sort(row + 1, row + n + 1);
    sort(col + 1, col + m + 1);

    int cnt = 0;
    for (int i = n; i > n - K; i -- ) q[cnt ++ ] = row[i].second;
    sort(q, q + cnt);
    for (int i = 0; i < cnt; i ++ ) printf("%d ", q[i]);
    puts("");

    cnt = 0;
    for (int i = m; i > m - L; i -- ) q[cnt ++ ] = col[i].second;
    sort(q, q + cnt);
    for (int i = 0; i < cnt; i ++ ) printf("%d ", q[i]);
    puts("");

    return 0;
}