题解：P10683 [COTS 2024] 划分 Particija

· · 题解

第一次写这么长的题解。

首先我们考虑 k=0 时如何计算答案。

转化一下限制条件，也就是说对于任意一个 i，a_i 和 b_i 必须有恰好一个被选择。于是我们选择图论建模。左部点为 i，右部点为 i+n，连边方式是 a_i 与 b_i+n 连边。

然后限制就被转化成了每条边恰好一个端点被选择，要求选择最少的点。

又因为这是一个二分图，当你选择某个连通块的左部点时，你就必须把整个连通块的左部点选上，和二分图染色一个意思，这点可以手动模拟一下。

于是 k=0 时最后的答案就是所有连通块左部点和右部点数量较小值之和。

然后考虑修改一个数，相当于可以把一条 (a_i,b_i+n) 修改为 (a_i,x+n) 或者 (x,b_i+n)，其中 x 为 1 到 n 中的任意点。

现在有一个十分有意思的性质，对于任意四个数 a,b,c,d，都有 \min(a,b)+\min(c,d) \le \min(a+c,b+d)。

证明是显然的，因为前式相当于 \min(a+c,a+d,b+c,b+d)。

也就是说只有当我们合并两个连通块时，答案才可能变得更大。只有当我们将一个连通块分割成两个时，答案才可能变得更小。

那么就可以做 k=1 了。考虑将修改转化为一次删除和一次加入，如果我们删除的这条边没有将一个连通块分成两个，那么答案一定不会变得更小。因为下一步操作加边只可能合并让答案变大。也就是说我们修改的边只有可能是割边。

而且我们还要考虑加边对答案的影响，但我们发现其实可以做到没有影响。如果你修改的边的端点 x,y 有至少一个在删除这条边后不为孤点，那么你可以把这条边塞到那个连通块里面去。否则只要 n 不为 1，你必然能找到一个连通块的左部点数量不超过右部点，塞进去即可。

对这个值的计算，我们可以预处理出一条边是否是割边以及每个连通块的大小。

然后枚举每个点，如果一个点没去过就以它为根搜一遍 dfs 生成树，同时统计子树内的左部点数量和右部点数量。

如果一条边是割边，它必然会在往下搜的时候被找到，这个时候下面传上来的数量就是割开这条割边之后一个连通块的左右部点大小，另一个用总数减去即可。最后求个最小值就做完了

现在我们再来考虑 k=2 的情况。那么只有合并会有正收益。我们贪心的想，如果你现在有一个连通块左部点超过右部点，是不是你肯定会连接上一个右部点超过左部点的连通块，让这两个连通块被浪费的左部点和右部点相互匹配。

因为你还需要删除一条边，所以你需要分成割边和非割边考虑。

处理出左部点与右部点差值最大和最小的连通块差值（注意这里的差值不取绝对值）。定义一个连通块对应的连通块指：如果左部点大于右部点就取差值最小的，否则就是最大的。

对于一个连通块的割边，将其连接的两个连通块分别连接其对应的连通块计算。如果某个连通块里有非割边，就直接连接这个连通块和对应的连通块。然后取最大值计算即可。

我个人在 k=2 时的代码实现可能有点神秘，我在统计割边时是直接把割出来的连通块的对应连通块当成了整个连通块的对应连通块计算。但这样做因为你取得是最大值所以也能过，应该是对的但我不会证。卡掉了麻烦私信或直接评论一下。k=2 时的代码请谨慎食用。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
int T,k,n,a[1000005],b[1000005],siz1,siz2,id[1000005],dfn[1000005],low[1000005],cnt;
vector<pair<int,int> > v[1000005];
vector<pair<int,int> > V;
bool vis[1000005],VIS[1000005];
void pre(int cur){
    if(vis[cur]) return;
    vis[cur]=true,id[cur]=V.size(),siz1+=(cur<=n),siz2+=(cur>n);
    for(auto i:v[cur]) pre(i.F);
    return;
}
void tarjan(int cur,int id){
    dfn[cur]=low[cur]=++cnt;
    for(auto i:v[cur]){
        int nxt=i.F,w=i.S;
        if(id==w) continue;
        if(!dfn[nxt]){
            tarjan(nxt,w);
            low[cur]=min(low[cur],low[nxt]);
            if(low[nxt]>dfn[cur]) VIS[w]=true;
        }
        else low[cur]=min(low[cur],dfn[nxt]);
    }
    return;
}
int mini;
int val[1000005];
pair<int,int> dfs(int cur){
    // cout<<cur<<'\n'
    if(vis[cur]) return {0,0};
    vis[cur]=true;
    int siz1=(cur<=n),siz2=(cur>n);
    for(auto i:v[cur]){
        int nxt=i.F,w=i.S;
        if(vis[nxt]) continue;
        pair<int,int> p=dfs(nxt);
        siz1+=p.F,siz2+=p.S;
        if(VIS[w]) mini=min(mini,-min(V[id[cur]].F,V[id[cur]].S)+min(p.F,p.S)+min(V[id[cur]].F-p.F,V[id[cur]].S-p.S));
    }
    return {siz1,siz2};
}
pair<int,int> DFS(int cur,int fa){
    if(vis[cur]){mini=max(mini,min(abs(V[id[cur]].F-V[id[cur]].S),abs(val[id[cur]])));return {0,0};}
    vis[cur]=true;
    int siz1=(cur<=n),siz2=(cur>n);
    for(auto i:v[cur]){
        int nxt=i.F,w=i.S;
        if(nxt==fa) continue;
        pair<int,int> p=DFS(nxt,cur),P=V[id[cur]];
        siz1+=p.F,siz2+=p.S;
        if(VIS[w]) mini=max(mini,-min(P.F,P.S)+min(p.F,p.S)+min(P.F-p.F,P.S-p.S)+min(abs(val[id[cur]]),max(abs(p.F-p.S),abs((P.F-p.F)-(P.S-p.S)))));
    }
    return {siz1,siz2};
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T>>k;
    while(T--){
        cin>>n;
        V.clear();
        for(int i=1; i<=n; i++) v[i].clear(),v[i+n].clear(),vis[i]=vis[i+n]=false;
        for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=n; i++) cin>>b[i],v[a[i]].push_back({b[i]+n,i}),v[b[i]+n].push_back({a[i],i});
        siz1=siz2=0;
        for(int i=1; i<=n; i++) if(!vis[i]) siz1=siz2=0,pre(i),V.push_back({siz1,siz2});
        if(!k){
            int ans=0;
            for(auto p:V) ans+=min(p.F,p.S);
            cout<<ans<<'\n';
        }
        else if(k==1){
            if(n==1){cout<<"1\n";continue;}
            for(int i=1; i<=n; i++) dfn[i]=low[i]=dfn[i+n]=low[i+n]=VIS[i]=0;
            cnt=0;
            for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i,0);
            int ans=0;mini=0;
            for(auto p:V) ans+=min(p.F,p.S);
            for(int i=1; i<=n; i++) vis[i]=vis[i+n]=false;
            for(int i=1; i<=n; i++) if(!vis[i]) dfs(i);
            cout<<ans+mini<<'\n';
        }
        else{
            for(int i=1; i<=n; i++) dfn[i]=low[i]=dfn[i+n]=low[i+n]=VIS[i]=0;
            cnt=0;
            for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i,0);
            int ans=0;mini=0;
            for(auto p:V) ans+=min(p.F,p.S);
            for(int i=1; i<=n; i++) vis[i]=vis[i+n]=false;
            bool f1=false,f2=false;
            sort(a+1,a+n+1),sort(b+1,b+n+1);
            for(int i=1; i<=n; i++) if(a[i]==a[i-1]) f1=true;
            for(int i=1; i<=n; i++) if(b[i]==b[i-1]) f2=true;
            for(int i=0; i<V.size(); i++) if(V[i].F>V[i].S) val[i]=-f2;else val[i]=f1;
            int mn=0,mx=0;
            for(int i=0; i<V.size(); i++) mn=min(mn,V[i].F-V[i].S),mx=max(mx,V[i].F-V[i].S);
            for(int i=0; i<V.size(); i++) if(V[i].F-V[i].S>0) val[i]=min(val[i],mn);else val[i]=max(val[i],mx);
            for(int i=1; i<=n; i++) if(!vis[i]) DFS(i,0);
            cout<<ans+mini<<'\n';
        }
    }
    return 0;
}