題意

2n 個數站成兩排（每個數在 2n個數中最多出現兩遍），一次操作可以交換任意一列中兩個數，求使每行數不重復的最少操作數。

（n<=50000）

題解

說實話，我真沒想到圖論。（我太菜了）

一開始以為是DP，寫了一遍然后被自己的數據秒卡。

其實我已經發現選擇的方案有依賴性，可是就是沒想到圖論。

假如一排中的i位置與j位置相等把i,j用權值為1的邊連起來。

假如一排中i位置的數和另一排中j位置的數相等，把i，j用權值為0的邊連起來。

然后要保證用1連起來的兩點顏色不一樣。用0連起的兩個點顏色不一樣進行黑白染色。

然后每一個聯通塊的最小數量的顏色之和就是答案。

（顏色相當于是否第i列換位置，顯然1連的兩點必須一個換一個不換，0連接的點要不全換，要不全不換）

（為什么不一樣的用1連，一樣的用0連，應為這樣好染色，看代碼）

?

1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<cstdio> 5 #include<algorithm> 6 #include<map> 7 #include<queue> 8 using namespace std; 9 const int N=50010; 10 map<int,int>ma,mb; 11 int col[N],vis[N],n,a[N],b[N],ans,head[N],cnt; 12 struct edge{ 13 int to,nxt,w; 14 }e[N*5]; 15 void add(int u,int v,int w){ 16 cnt++; 17 e[cnt].nxt=head[u]; 18 e[cnt].to=v; 19 e[cnt].w=w; 20 head[u]=cnt; 21 } 22 void bfs(int s){ 23 queue<int> q; 24 q.push(s); 25 col[s]=1; 26 vis[s]=1; 27 int tot=1; 28 int num=0; 29 while(!q.empty()){ 30 int u=q.front(); 31 q.pop(); 32 for(int i=head[u];i;i=e[i].nxt){ 33 int v=e[i].to; 34 if(vis[v])continue; 35 tot++; 36 q.push(v); 37 vis[v]=1; 38 col[v]=col[u]^e[i].w; 39 if(col[v]==0)num++; 40 } 41 } 42 ans+=min(num,tot-num); 43 } 44 int main(){ 45 scanf("%d",&n); 46 for(int i=1;i<=n;i++){ 47 scanf("%d",&a[i]); 48 if(ma[a[i]]){ 49 add(ma[a[i]],i,1); 50 add(i,ma[a[i]],1); 51 } 52 else ma[a[i]]=i; 53 } 54 for(int i=1;i<=n;i++){ 55 scanf("%d",&b[i]); 56 if(ma[b[i]]){ 57 add(ma[b[i]],i,0); 58 add(i,ma[b[i]],0); 59 } 60 else{ 61 if(mb[b[i]]){ 62 add(mb[b[i]],i,1); 63 add(i,mb[b[i]],1); 64 } 65 else mb[b[i]]=i; 66 } 67 } 68 for(int i=1;i<=n;i++){ 69 if(vis[i]==0)bfs(i); 70 } 71 printf("%d",ans); 72 return 0; 73 }

?

轉載于:https://www.cnblogs.com/Xu-daxia/p/9434387.html

總結

以上是生活随笔為你收集整理的[POI2005]DWU-Double-row（图论？）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。