DDOSvoid's Blog

校内赛 2021-2-15 Problem G

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

给定一个二维平面 $nm$ 和 $k$ 个矩形，每个矩形都有一个代价

要求选择代价最小的若干个矩形使得 $(1,1)$ 和 $(n,m)$ 不连通，注意矩形之间可能相交或者重叠

$n,m,k\le 2000$

Solution

我们以左和下边界为起点，右和上边界为终点，对于每个矩形都建一个点

如果两个矩形相邻或相交，则这两个点相连

那么我们求最短路即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 2010
#define ll long long 
#define INF 1000000000000000000ll
using namespace std;

int n, m, k;

int xl[maxn], xr[maxn], yl[maxn], yr[maxn], w[maxn]; 

ll g[maxn][maxn];

inline bool check(int l1, int r1, int l2, int r2) {
    if (l1 > l2) swap(l1, l2), swap(r1, r2); 
    if (r1 + 1 < l2) return 0;
    return 1;
}

ll dis[maxn]; bool vis[maxn]; 
void dijkstra() {
    fill(dis, dis + k + 2, INF); dis[0] = 0; dis[k + 2] = INF;
    fill(vis, vis + k + 2, 0); 
    for (int i = 0; i <= k + 1; ++i) {
        int p = k + 2; 
        for (int j = 0; j <= k + 1; ++j)
            if (!vis[j] && dis[j] < dis[p]) p = j;
        if (p == k + 2) break; vis[p] = 1; 
        for (int j = 0; j <= k + 1; ++j) dis[j] = min(dis[j], dis[p] + g[p][j]); 
    }
} 

void work() {
    cin >> n >> m >> k; 
    for (int i = 0; i <= k + 1; ++i)
        for (int j = 0; j <= k + 1; ++j) g[i][j] = i == j ? 0 : INF;
    for (int i = 1; i <= k; ++i) {
        cin >> xl[i] >> xr[i] >> yl[i] >> yr[i] >> w[i]; 
        if (xr[i] == n || yl[i] == 1) g[0][i] = w[i];
        if (xl[i] == 1 || yr[i] == m) g[i][k + 1] = 0;
        for (int j = 1; j < i; ++j)
            if (check(xl[i], xr[i], xl[j], xr[j]) && check(yl[i], yr[i], yl[j], yr[j]))
                g[i][j] = w[j], g[j][i] = w[i];
    } dijkstra(); if (dis[k + 1] == INF) dis[k + 1] = -1;
    cout << dis[k + 1] << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}