BZOJ 1562 浅谈匈牙利算法性质挖掘以【变换序列】即最小字典序构
世界真的很大 匈牙利算法并不是一个有许多性质可以挖掘或者拓展的算法 但是对于其思路还是必须要熟悉才行。 邻接表的具体构建方式已经忘得差不多了,只是背的到 算是都复习了一遍 认真想起来其实也不是很难 看题先: description:input:output :要求选一种满足题意的“置换”,使得字典序最小 能不能使每一个点都有一个去处,翻译一下就是: 思路能一下想到的有两个 二呢,考虑到,求出最大匹配之后,match数组保存的匹配边已经是一种方案了,只不过可能不是最小而已,有没有什么办法暗箱操作一下匈牙利算法的过程,使得求出的正好是最小字典序呢? 怎么想都是第二种看起来实现难度低一点 复习一下匈牙利算法的实现流程:传送门 考虑邻接表,有着“后加的边先跑”的原则。所以我们只需要在加边的时候,先加大的,再加小的,就行了 满足这两个约束条件后,跑出来的匹配是不是字典序最小的匹配呢? 若问为何? 完整代码: #include<stdio.h>
struct edge
{
int v,last;
}ed[4000010];
int n,ans=0,tot=0,num=0;
int head[200010],book[200010],match[200010];
void add(int u,int v)
{
num++;
ed[num].v=v;
ed[num].last=head[u];
head[u]=num;
}
int dfs(int u)
{
for(int i=head[u];i;i=ed[i].last)
{
int v=ed[i].v;
if(book[v]!=tot)
{
book[v]=tot;
if(!match[v] || dfs(match[v]))
{
match[u]=v,match[v]=u;
return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int d;
scanf("%d",&d);
int a=(i+d)%n+n,b=(i-d+n)%n+n;
if(a>b) add(i,a),add(i,b);
else add(i,b),a);
}
for(int i=n-1;i>=0;i--)
{
tot++;
if(!match[i]) ans+=dfs(i);
}
if(ans<n) printf("No Answer");
else
{
for(int i=0;i<n;i++)
{
printf("%d",match[i]-n);
if(i!=n-1) printf(" ");
}
}
return 0;
}
/*
Whoso pulleth out this sword from this stone and anvil is duly born King of all England
*/
嗯,就是这样 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |