MX-X12-T1 / ALFR R5A 地铁 题解

· · 题解

首先，可以将每个地铁线路两端一直延长直到城市道路交通网的边缘，这样不会增加线路的数量，每条地铁线路能覆盖的交叉路口数量还能变多。

这样，所有地铁线路就可以被分为两种：

  1. 横向的可以经过 m 个交叉口的地铁线路；
  2. 纵向的可以经过 n 的交叉口的地铁线路。

不考虑不能「脱网」的特殊要求，要用这两种地铁线路覆盖所有 n\times m 的交叉口，最优方案肯定是选择 n 个第一种地铁线路或者 m 个第二种地铁线路平行放置。如果 n\le m，最优方案就是选择 n 个横向的地铁线路，否则就选择 m 个纵向的地铁线路。这样，答案就是 \min(n,m)。

但是这样构造出来的地铁“线网”图并没有满足不能「脱网」的要求。因此，需要一个另一个垂直方向的地铁线路将所有平行的地铁线路串起来。所以答案是 \min(n,m)+1。

注意需要特判 \min(n,m)=1 的情况，此时只需要一条线路即可，不需要另一条地铁线路来把这单独的一条线路“串起来”。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        int x=min(n,m);
        if(x==1)cout<<1<<endl;
        else cout<<x+1<<endl;
    }
    return 0;
}