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

xyx404 · 2025-05-05 18:39:21 · 题解

思路：

通过分析，可以发现：

• 当 n 和 m 中有一个为 1 时，只用一条线就可以，答案为 1。
• 当 n 和 m 中没有一个为 1 时，当 n<m 时，最优方案是是用 n 条线把每一行的所有车站连起来，再用一条线把一列连起来，就可以实现，答案为 n+1；同理当 n>m 时，答案为 m+1，综上 ans=\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;
}