「ALFR Round 5」地铁

Link

• 如图，首先，当 $n,m \ge 2$ 时，我们考虑每一行或每一列都只有一条地铁线，如果 $m>n$ 那就就选 $n$ 条，反之则选 $m$ 条。这样可以使地铁线覆盖范围更广，同时也能使地铁线路最少。
• 但是铁路还要满足无论从哪个地铁站出发乘坐地铁，经过若干次换乘（可以不换乘），都一定可以到达其它所有地铁站。所以必定有一条线路分别和上述的 $\min(n,m)$ 条线路至少有一个交点。所以答案为 $\min(n,m)+1$。
• 当 $n=1$ 或 $m=1$ 时，此时只需要一条长为 $n$ 或 $m$ 的铁路线来使其覆盖全部即可。
• 故答案 $y$ 为：

$$y = \begin{cases} \min(n, m) + 1, & \text{if } n \geq 2 \text{ and } m \geq 2 \\ 1, & \text{if } n = 1 \text{ or } m = 1 \end{cases} $$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,t;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		if(n==1||m==1) cout<<1<<endl;
		else cout<<min(n,m)+1<<endl;
	}
}