抄板子就是爽
题目描述
有两个长度为n的排列A,B,你需要用最少的操作来使两个排列递增。
每次操作:
1、选一个数 $i$;
2、$\mathrm{swap}(A_i,A_j),A_j=i$;
3、$\mathrm{swap}(B_i,B_j),B_j=i$;
solution
这题没那么难
首先你得意识到这是个图论题
具体怎么意识到,emmm,看数据范围?($n \le 3000$)
哦不,你发现了一个特性:
假设我们只考虑排列A,你先尝试连边 $(A_i,i)$
诶,你会发现得到一个图,每个图都由一些环组成。
然后你又发现,我们的操作,就是把每个环都拆成点。
把一个大小为 $x$ 的环拆成 $x$ 个点,需要 $x-1$ 个操作。
也就是说,你可以对每个环选择其中一个点,然后除了这个点,操作其它的点。
题目就转化为选择尽量不操作的点。
但是,问题在于,我们有两个排列。
我们这样思考,假如一个数 $i$ 不仅在A的环里,也在B的环里。
那么选择不操作这个数,肯定是最优的。
但是,A和B的环不只一个。
因此,我们将A和B的每个环抽象成一个点,若A中的一个环与B中的某些环有交集,我们就对它们连边。
没错,这其实就是个二分图匹配的模板题!
跑遍匈牙利或者dinic即可。(但我不会网络流
最后输出答案的时候,我们对每一对匹配的环,找到其中的交集,选择不输出它即可。
匈牙利算法的复杂度是O(VE),在这里就是O(n^2)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i = a;i <= n; ++i)
#define per(i,a,n) for(int i = n; i >= a; --i)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define CMIN(_a,_b) ((_a>_b)&&(_a=_b))
#define CMAX(_a,_b) ((_a<_b)&&(_a=_b))
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod = 998244353;
int rnd(int x) {return mrand() % x;}
ll powmod(ll a,ll b){ll ret=1;a%=mod;assert(b>=0); for(;b;b>>=1){if(b&1)ret=ret*a%mod;a=a*a%mod;}return ret;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int n;
int A[3010],B[3010];
int tA[3010],tB[3010];
int fA[3010],fB[3010],totA,totB;
bool G[3010][3010];
int linker[3010];
bool used[3010];
bool DFS(int u)
{
rep(v,1,totB)
{
if(G[u][v] && !used[v])
{
used[v] = true;
if(linker[v] == -1 || DFS(linker[v]))
{
linker[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(linker,-1,sizeof(linker));
rep(i,1,totA)
{
memset(used,false,sizeof(used));
if(DFS(i))
++res;
}
return res;
}
void DFSA(int u)
{
if(fA[u])
return;
fA[u] = totA;
DFSA(tA[u]);
}
void DFSB(int u)
{
if(fB[u])
return;
fB[u] = totB;
DFSB(tB[u]);
}
bool pd[3010];
int main()
{
cin >> n;
rep(i,1,n)
{
cin >> A[i];
tA[A[i]] = i;
}
rep(i,1,n)
{
cin >> B[i];
tB[B[i]] = i;
}
rep(i,1,n)
{
if(!fA[i])
{
++totA;
DFSA(i);
}
if(!fB[i])
{
++totB;
DFSB(i);
}
}
rep(i,1,n)
{
G[fA[i]][fB[i]] = true;
}
int ans = n - hungary();
rep(i,1,totB)
{
if(linker[i] != -1)
{
rep(j,1,n)
{
if(fA[j] == linker[i] && fB[j] == i)
{
pd[j] = true;
break;
}
}
}
}
printf("%d\n",ans);
rep(i,1,n)
if(!pd[i])
printf("%d ",i);
return 0;
}