P9726 [EC Final 2022] Magic 题解

Acoipp · 2023-11-30 15:14:52 · 题解

网络流。

分析

首先题目中说明了保证所有 l_i,r_i 互不相同，我们尝试从这个角度入手。

遇到区间排序的问题很显然地任取两个区间出来分类讨论一下，设这两个区间分别为 [l_1,r_1),[l_2,r_2)，那么所有情况如下所示（令 l_1<l_2）：

• 若 r_1 < l_2，那么这两个区间无交集，先后顺序不影响。

• 若 r_1 > r_2，那么前一个区间包含后一个区间，显然把前一个区间放在操作序列前会比较优秀。

• 否则这两个区间有交且不包含，如果 [l_1,r_1) 放前面，那么 l_2 这个下标上的元素就会与它之前的不一样；否则 r_1 这个下标上的元素就会与它之前的不一样，经典二选一问题。

于是对有交且不包含的区间像上述执行操作即可，建立二分图，然后用匈牙利算法或者网络流跑最大独立集即可。

二分图最大独立集等于总点数减去最大匹配。

代码

代码使用 ISAP 实现，加上 bitset 优化空间即可通过。

#include<bits/stdc++.h>
#define ll long long
#define N 10005
using namespace std;
ll n,i,j,l[N],r[N],pos[N],dis[N],sum[N],s,t,inf,ans;
bitset<N> maps[N];
ll dfs(ll x,ll step){
    if(x==t) return step;
    ll used = 0;
    for(ll i=maps[x]._Find_first();i<=t;i=max(i+1,(ll)maps[x]._Find_next(i))){
        if(maps[x][i]==0) break;
        if(dis[i]+1==dis[x]){
            ll temp = dfs(i,min(1ll,step-used));
            used += temp;
            if(temp) maps[x][i]=0,maps[i][x]=1;
            if(used==step||dis[s]>=inf) return used;
        }
    }
    if(--sum[dis[x]]==0) dis[s] = inf;
    sum[++dis[x]]++;
    return used;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++) cin>>l[i]>>r[i],pos[r[i]]=1;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(l[i]<l[j]&&l[j]<r[i]&&r[i]<r[j]) maps[l[j]][r[i]]=1;
    s=0,t=2*n+1,inf=t-s+1,sum[0]=inf;
    for(i=1;i<=2*n;i++){
        if(!pos[i]) maps[s][i]=1;
        else maps[i][t]=1;
    }
    while(dis[s]<inf) ans+=dfs(s,1e18);
    cout<<2*n-ans<<endl;
    return 0;
}