神奇的思路题
其它博客讲的太emmm了！！
我尽量讲清QWQ
思路
我们把在同一行的两个数所在列建一条长度为1的边，不在同一列的建一条长度为0的边，然后对这张新建出来的图染色，我们要保证权值为0的两边的点颜色必然相同，为1则不同，为什么这么做？对于一条边权为1的边，它两端的元素是相同且在一行的，我们必须要交换这两列其中的一列，也就是 1 1 2 3 第一列和第二列一定有一列要交换，但是我们不能确定换完其中一列后会不会造成其他影响，但我们发现，列与列之间的边连接的是相同的元素，所以图中是一些没有交点的链覆盖了整张图，所以有影响也必定是在同一条链中，不会对其他部分造成影响，所以我们只考虑链内咋办 1 1 2 3 2 4 上面这个序列，需要在第1列和第2列中选一个交换，先看染色是啥 建图是 1 to 2 cost 1，2 to 3 cost 0，所以染色就是 0 1 1，发现要么交换第一列，要么交换二列和三列，因为两个点颜色相同，必然是不在同一行，所以交换其中任何一个，都会造成多了一组冲突，所以解决办法就是把颜色相同的全部交换一下，也就是说要么把颜色为0的列全部交换，要么交换颜色为1的，然后在两种操作里取最小的一定是最优的，不理解就画图模拟一下好了QAQ
赶jio还是木讲清楚，主要就是明确交换两列只会在一个单独的链内造成影响，然后上面操作才有意义就好了
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std
;
const int M
=100500;
int n
,cnt
[2];
int vis
[M
],jud
[M
],col
[M
];
int to
[M
],w
[M
],nxt
[M
],head
[M
],tot
;
inline void read(int &x
)
{
x
=0;char ch
=getchar();
while (!isdigit(ch
)) ch
=getchar();
while (isdigit(ch
)) x
=x
*10+ch
-'0',ch
=getchar();
return ;
}
inline void add(int x
,int y
,int z
)
{
to
[++tot
]=y
;w
[tot
]=z
;nxt
[tot
]=head
[x
];head
[x
]=tot
;
to
[++tot
]=x
;w
[tot
]=z
;nxt
[tot
]=head
[y
];head
[y
]=tot
;
return ;
}
inline void dfs(int x
,int c
)
{
col
[x
]=1;cnt
[c
]++;
for (int i
=head
[x
];i
;i
=nxt
[i
])
if (!col
[to
[i
]]) dfs(to
[i
],(c
+w
[i
])&1);
return ;
}
signed main()
{
read(n
);int x
;
for (int i
=1;i
<=n
;i
++)
{
read(x
);
if (vis
[x
]) add(vis
[x
],i
,1);
else vis
[x
]=i
,jud
[x
]=1;
}
for (int i
=1;i
<=n
;i
++)
{
read(x
);
if (jud
[x
]&&vis
[x
]) add(vis
[x
],i
,0);
else if (vis
[x
]) add(vis
[x
],i
,1);
else vis
[x
]=i
;
}
int ans
=0;
for (int i
=1;i
<=n
;i
++)
if (!col
[i
])
{
cnt
[0]=cnt
[1]=0;dfs(i
,0);
ans
+=min(cnt
[1],cnt
[0]);
}
cout
<<ans
;
return 0;
}
