[POI2005]DWU-Double-row

有2n个士兵站成两排,他们需要被重新排列,以保证每一排里没有同样高的士兵——这样我们就说,士兵们被合理地安排了位置。 每次操作可以交换两个在同一位置(但不在同一排)的士兵。你的任务是用最少的操作来确保士兵们被合理地安排了位置。 例如: 有18个士兵站成两排,箭头标明了重新安排士兵位置的正确方式(图飞了?)。 写一个这样的程序: 读入n与士兵的身高,以及他们最初所站的位置,确保以最小的交换(站在同一位置的不同排的士兵)的次数来合理地安排士兵的位置,输出操作数。

Solution

我最菜了。

听一些dalao说要染色,于是我就有了一些NAIVE的想法,把每一列的两个点之间连一条边,既然每个点的度数最多为2,那么它最后一定是一堆环,我们要么全部正着走,要么都反着走,所以我们对每个联通块都做一遍就可以了。

Code

#include<iostream>
#include<cstdio>
#define N 100002
using namespace std;
int head[N],tot,a[N],b[N],ans,pos[],n,ma;
bool vis[N];
struct edge{
int n,to,tag;
}e[N<<];
inline void add(int u,int v,int tag){
e[++tot].n=head[u];
e[tot].to=v;
e[tot].tag=tag;
head[u]=tot;
}
void dfs(int u,int fa){
vis[u]=;
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
int v=e[i].to;
pos[e[i].tag]++;
if(!vis[v])dfs(v,u);
break;
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i]),ma=max(ma,a[i]);
for(int i=;i<=n;++i)scanf("%d",&b[i]),add(a[i],b[i],),add(b[i],a[i],),ma=max(ma,b[i]);
for(int i=;i<=ma;++i)if(!vis[i]){
pos[]=pos[]=;
dfs(i,);
ans+=min(pos[],pos[]); ;
}
cout<<ans;
return ;
}

获得了40pts

emmm

有一个问题就是说有些数会出现一次,因为每个点度数最多为2,不可能是基环树,只能是一条链,那么GG了。

我们把每列看成一个点,如果两列必须一样连0边,否则连1边,染色即可。

真·Code

#include<iostream>
#include<cstdio>
#define N 100002
using namespace std;
int head[N],tot,x,ans,pos[],n,pre[N],co[N];
bool vis[N];
struct edge{
int n,to,tag;
}e[N<<];
inline void add(int u,int v,int tag){
e[++tot].n=head[u];
e[tot].to=v;
e[tot].tag=tag;
head[u]=tot;
}
void dfs(int u,int c){
vis[u]=;pos[c]++;
for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
int v=e[i].to;
dfs(v,c^e[i].tag);
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
scanf("%d",&x);
if(pre[x]){
add(i,pre[x],);
add(pre[x],i,);
}
else pre[x]=i;
}
for(int i=;i<=n;++i){
scanf("%d",&x);
if(pre[x]){
add(i,pre[x],co[x]);
add(pre[x],i,co[x]);
}
else pre[x]=i,co[x]=;
}
for(int i=;i<=n;++i)if(!vis[i]){
pos[]=pos[]=;
dfs(i,);
ans+=min(pos[],pos[]);
}
cout<<ans;
return ;
}
上一篇:ligerui_实际项目_003:form中添加数据,表格(grid)里面显示,最后将表格(grid)里的数据提交到servlet


下一篇:OC基础回想(十二)协议