题解 P3430 【[POI2005]DWU-Double-row】

【POI补全计划#14 POI2005 DWU】 先说题意 有两行人，每行n个，每人有身高，每次操作可以交换同一列的两人，使得最终两行人的身高分别互不相同，保证有解 问最少交换几次 补样例解释图片  以下是题解 --------------------------------题解分割线------------------------------------- 也算是思维难度比较简单的一题了 考虑要使得每行身高互不相同要满足什么条件 1.若相同的两个数字在同一行，第i列和第j列，则第i列和第j列中一定恰有一列需要交换，于是在点i和点j间连一条权值为1的边 2.若相同的两个数字不在同一行，在第i列和第j列，则第i列和第j列中一定要么都需要交换要么都不需要交换，于是在点i和点j间连一条权值为0的边 只需要在新图上进行二染色，使得权值为1的边两侧染色不同，权值为0的边两侧染色相同，取每个连通块中同色的较少部分加入答案 这种东西随便dfs一下就出来了 贴代码 ```cpp #include<iostream> #include<cstdio> using namespace std; int pos[100010][2]; int n,tmp0; struct edge { int v,w; edge *next; }*h[50010],pool[100010]; int top; inline void addedge(int u,int v,int w) { edge *tmp=&pool[top++];tmp->v=v;tmp->w=w;tmp->next=h[u];h[u]=tmp; edge *pmt=&pool[top++];pmt->v=u;pmt->w=w;pmt->next=h[v];h[v]=pmt; } int vis[50010],col[50010],cntc[2],cnt,ans; void dfs(int u) { vis[u]=1; cntc[col[u]]++; for(edge *tmp=h[u];tmp;tmp=tmp->next) { if(!vis[tmp->v]) { col[tmp->v]=col[u]^tmp->w; dfs(tmp->v); } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&tmp0); if(pos[tmp0][0])pos[tmp0][1]=i; else pos[tmp0][0]=i; } for(int i=1;i<=n;i++) { scanf("%d",&tmp0); if(pos[tmp0][0])pos[tmp0][1]=-i; else pos[tmp0][0]=-i; } for(int i=1;i<=100000;i++) { if(pos[i][0]&&pos[i][1]) { addedge(abs(pos[i][0]),abs(pos[i][1]),!((pos[i][0]>0)^(pos[i][1]>0))); } } for(int i=1;i<=n;i++) { if(!vis[i]) { cntc[0]=cntc[1]=0; dfs(i); ans+=min(cntc[0],cntc[1]); } } printf("%d\n",ans); return 0; } ```