题解：P6270 [湖北省队互测 2014] 十万人的地铁

· · 题解

感谢巨佬 george0929 的题解使得我明白这道题的思路。

同样是省选模拟赛的 T2，毋庸置疑地被创飞了。

Question 1

第一问，答案是什么。

猜测发现，如果我们的一些人在一个连通块中，他们之间可以随意 交换武汉通，因此我们只需要将连通块里面 s,t 按照从小到大排序，那么这个连通块对于答案的贡献就是 \sum |s_i-t_i|。

至于如何交换，如果任意随机交换，容易造成绕路行为，所以我们的关键是找到一个不绕路的构造方法。

Question 2

考虑数学归纳法。

首先对于只有一个人 s\rightarrow t，我们只能沿着路径走过去，无法交换，结论成立。

如果有多个人，我们取出 s 最大的人 x 和 t 最大的人 y。

若 x=y，则我们沿着 s\rightarrow t 走过去即可。

接下来我们考虑通过某些方法，既交换 x,y 两人的武汉通，同时使得其中一个人到达终点（另一个人可以递归处理）

Case 1 t_x\le s_y

我们容易发现 t_x\le t_y,s_x\ge s_y。

所以我们得到 t_x\le s_y\le s_x。

构造 x:s_x\rightarrow s_y。

然后交换武汉通，y 后面不会遇到其他人了，所以执行 y:s_y\rightarrow t_y。

然后我们将人 x 的 s_x 设置为 s_y，并将人 y 删除。

Case 2 t_x>s_y

与前面的正好相反，根据前面的东西同理可得。

我们首先将 t_y 设置为 t_x，删除人 x 并进行递归。

递归完成后，我们的人 y 到达了 t_x。

此时执行 x:s_x\rightarrow t_x，容易发现路上不会遇到任何人。

二人在 t_x 相遇并交换武汉通。

此时执行 y:t_x\rightarrow t_y，所有人到达终点，结束求解。

:::info[code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{int op,x,y;};
vector <node> vc;
#define N 100010
int now[N],s[N],t[N],res;
set <pair<int,int>> S,T;
void solve(){
    while (S.size()){
        int x=(S.begin()->second),y=(T.begin()->second);
        S.erase(S.begin()); T.erase(T.begin());
        if (x==y){
            vc.push_back({0,x,t[x]});
            res+=abs(s[x]-t[x]);
            continue;
        }
        res+=abs(s[x]-t[y]);
        S.erase({-s[y],y});
        T.erase({-t[x],x});
        if (t[x]<=s[y]){
            vc.push_back({0,x,s[y]});
            vc.push_back({1,x,y});
            vc.push_back({0,y,t[y]});
            s[x]=s[y];
            S.insert({-s[x],x});
            T.insert({-t[x],x});
            solve();
        }
        else{
            int tx=t[x],ty=t[y];
            t[y]=t[x];
            S.insert({-s[y],y});
            T.insert({-t[y],y});
            solve();
            vc.push_back({0,x,tx});
            vc.push_back({1,x,y});
            vc.push_back({0,y,ty});
        }
    }
}
signed main(){
    int tt; cin>>tt;
    while (tt--){
        int n,m; cin>>n>>m; res=0;
        for (int i=1; i<=n; i++) cin>>s[i]>>t[i],now[i]=s[i];
        S.clear(); T.clear(); vc.clear();
        for (int i=1; i<=n; i++){
            S.insert({-s[i],i});
            T.insert({-t[i],i});
        }  
        solve();
        vector <node> ans;
        for (auto x:vc){
            if (x.op==1) ans.push_back(x);
            else{
                if (now[x.x]==x.y) continue;
                now[x.x]=x.y; ans.push_back(x);
            }
        }
        cout<<res<<" "<<ans.size()<<"\n";
        for (auto x:ans) cout<<x.op<<" "<<x.x<<" "<<x.y<<"\n";
    }
}

:::