自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:15:26，当前版本为作者最后更新于2024-11-07 15:30:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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;
}