题解：P12418 【MX-X12-T1】「ALFR Round 5」地铁

封面

引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404

思路：

通过分析，可以发现：

  • 当 nn 和 mm 中有一个为 11 时，只用一条线就可以，答案为 11。
  • 当 nn 和 mm 中没有一个为 11 时，当 n<mn<m 时，最优方案是是用 nn 条线把每一行的所有车站连起来，再用一条线把一列连起来，就可以实现，答案为 n+1n+1；同理当 n<mn<m 时，答案为 m+1m+1，综上 ans=min⁡(n,m)+1ans=\min(n,m)+1。

如果还是无法理解，可以看看图片。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int T;
int main(){
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		if(n==1||m==1){
			cout<<"1\n";
		}
		else{
			cout<<min(n,m)+1<<"\n";
		}
	}
	return 0;
}