当前位置: 首页 > news >正文

题解:AT_agc038_f [AGC038F] Two Permutations

题目:

置换环是显然的,一个环有旋一下和不旋两种状态。

\((P_i=i,Q_i=i,P_i=Q_i)\) 无非这三个限制。

  1. \((0,0,0)\):旋一个以上就有贡献。
  2. \((0,0,1)\):旋一个才有贡献。
  3. \((0,1,0)\):旋 P 才有贡献。
  4. \((1,0,0)\):旋 Q 才有贡献。
  5. \((1,1,1)\):没贡献。
  6. \((0,1,1)\):不合法。
  7. \((1,0,1)\):不合法。
  8. \((1,1,0)\):不合法。

最小割!直接出来了!
设 S、T 点后肯定要再把每个置换环当点塞进去,思考一个点 \(i\) 怎么连边:
下面称 \(p_i\)\(P_i\) 在的置换环,\(q_i\)\(Q_i\) 在的置换环。
假定连 \(S\) 为旋,连 \(T\) 为没旋。
第一种:wc。

trick:假定 \(p_i\)\(S\) 为旋,\(q_i\)\(T\) 为旋。

第一种:\(S→q_i→p_i→T\) 无法贡献,连 \(q_i→p_i\) 边权为 \(1\)
第二种:\(S→q_i→p_i→T,S→p_i→q_i→T\) 无法贡献,连 \(q_i→p_i,p_i→q_i\) 边权为 \(1\)
第三种:\(S→q_i→…\) 无法贡献,连 \(S→q_i\) 边权为 \(1\)
第四种:\(p_i→T→…\) 无法贡献,连 \(p_i→T\) 边权为 \(1\)
第五种:直接 ans--

初始令 \(ans=n\),减去第五种情况直接跑就行。

#include<bits/stdc++.h>
using namespace std;const int QAQ=2e6+9,inf=1e9;int dis[QAQ],kai[QAQ],lim;
int n,p[QAQ],q[QAQ],cnt=1,head[QAQ],nex[QAQ*5],to[QAQ*5],w[QAQ],ans;
void lian2(int u,int v,int wa)
{to[++cnt]=v;nex[cnt]=head[u];w[cnt]=wa;head[u]=cnt;
}
void lian(int u,int v,int w)
{lian2(u,v,w);lian2(v,u,0);
}
int s,t;
queue<int> dui;
int bfs()
{for(int i=1;i<=lim;i++) dis[i]=inf;dis[s]=0;kai[s]=head[s];while(!dui.empty()) dui.pop();dui.push(s);while(!dui.empty()){int x=dui.front();dui.pop();for(int i=head[x];i;i=nex[i]){int v=to[i];if(w[i]>0&&dis[v]==inf){kai[v]=head[v];dis[v]=dis[x]+1;dui.push(v);}}}if(dis[t]!=inf) return 1;return 0;
}
int dfs(int x,int xian)
{if(x==t) return xian;int ans=0;for(int i=kai[x];i&&xian>0;i=nex[i]){kai[x]=i;int v=to[i];if(dis[v]==dis[x]+1&&w[i]>0){int k=dfs(v,min(xian,w[i]));w[i]-=k,w[i^1]+=k;ans+=k,xian-=k;if(k==0) dis[v]=inf;}}return ans;
}
int cnt1,cnt2;
struct xxx
{int f[QAQ];int find(int x) {return x==f[x]?f[x]:f[x]=find(f[x]);}void hebing(int x,int y){x=find(x),y=find(y);if(x==y) return ;f[x]=y;}void cs(){for(int i=0;i<n;i++) f[i]=i;}} ta,tb;
int duia[QAQ],duib[QAQ];
signed main()
{cin>>n;ta.cs(),tb.cs();for(int i=0;i<n;i++) cin>>p[i],ta.hebing(i,p[i]);for(int i=0;i<n;i++) cin>>q[i],tb.hebing(i,q[i]);for(int i=0;i<n;i++){if(i==ta.find(i)) duia[i]=++cnt1;if(i==tb.find(i)) duib[i]=++cnt2;}for(int i=0;i<n;i++) duia[i]=duia[ta.find(i)],duib[i]=duib[tb.find(i)];lim=cnt1+cnt2;for(int i=0;i<n;i++) duib[i]+=cnt1;s=lim+1,t=lim+2;lim+=2;for(int i=1;i<=cnt1;i++) lian(s,i,0),lian(i,t,0);for(int i=1;i<=cnt2;i++) lian(s,cnt1+i,0),lian(cnt1+i,t,0);ans=n;for(int i=0;i<n;i++){if(p[i]!=i&&q[i]!=i&&p[i]!=q[i]) lian(duib[i],duia[i],1);else if(p[i]!=i&&q[i]!=i&&p[i]==q[i]) lian(duia[i],duib[i],1),lian(duib[i],duia[i],1);else if(p[i]==i&&q[i]!=i&&p[i]!=q[i]) lian(duib[i],t,1);else if(p[i]!=i&&q[i]==i&&p[i]!=q[i]) lian(s,duia[i],1);else if(p[i]==i&&q[i]==i&&p[i]==q[i]) ans--;}while(bfs()) ans-=dfs(s,inf);cout<<ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=23752

相关文章:

  • 10.3 考试总结
  • CSP-S 复赛指南(2025年版)
  • AI元人文系列文章:AI元人文的未来——软硬件协同
  • 10.3考试反思
  • 10.2 考试总结
  • 20251003国庆模拟3
  • 20251002国庆模拟2
  • ハレハレヤ
  • 4-创建索引和约束 - 实践
  • 2025十一集训——Day2做题
  • 核聚变:Commonwealth Fusion Systems
  • 占个位置~
  • AI元人文系列文章:价值决策芯片——为机器安上一颗“透明的心”
  • 30天JavaScript挑战 - 从零基础到精通的完整学习指南
  • 题解:AT_agc057_c [AGC057C] Increment or Xor
  • 占个位置
  • 使用 Copilot AI + Blazor 编一个五子棋游戏
  • 关于VMware虚拟机如何下载-2025.10.3
  • 国庆集训做题10.1 - 10.3
  • 玳瑁的嵌入式日记---0928(ARM--UART) - 指南
  • 解决Visual Studio中无法使用scanf和C++万能头的问题
  • 英文笔记
  • 解码红黑树
  • 10/3
  • Advanced Computer Graphics
  • Netflix确保数亿用户观影体验的“事件”管理是如何构建与实践的?
  • 为什么词嵌入可以和位置编码相加
  • 【比赛记录】2025CSP-S模拟赛57
  • 实用指南:软件设计师——04 操作系统
  • 20251001国庆模拟