索鸟网

  1. 首页
  2. BZOJ 1562 浅谈匈牙利算法性质挖掘以【变换序列】即最小字典序构成

BZOJ 1562 浅谈匈牙利算法性质挖掘以【变换序列】即最小字典序构成


这里写图片描述
世界真的很大
匈牙利算法并不是一个有许多性质可以挖掘或者拓展的算法
但是对于其思路还是必须要熟悉才行。
邻接表的具体构建方式已经忘得差不多了,只是背的到
算是都复习了一遍
认真想起来其实也不是很难

看题先:

description:

这里写图片描述

input:

这里写图片描述

output :

这里写图片描述

要求选一种满足题意的“置换”,使得字典序最小
不懂置换是什么的话就看这里:传送门
所谓满足条件,就是说原先序列的一个点最多有两个可以去的地方
合理安排每个点去哪个点,看能不能使得所有点都有一个去处
如果方案有多种的话,就输出字典序最小的那一种

能不能使每一个点都有一个去处,翻译一下就是:
求一种方案使尽量多的点有去处且不重叠,然后看点数到不到n
二分图最大匹配,看匹配数有没有n。
到此,判断有没有一种合法方案就结束了,问题在于输出字典序最小的方案。

思路能一下想到的有两个
一是再找找一种方法去求这种最小的字典序的方案
感觉~~有点难

二呢,考虑到,求出最大匹配之后,match数组保存的匹配边已经是一种方案了,只不过可能不是最小而已,有没有什么办法暗箱操作一下匈牙利算法的过程,使得求出的正好是最小字典序呢?

怎么想都是第二种看起来实现难度低一点

复习一下匈牙利算法的实现流程:传送门
即,在每一次新点匹配的时候,如果能匹配,那自然是直接匹配,反之就会去看前面的点能不能让出这一个空位
即是说,以后匹配的点为优先。
那我们越想让哪个点取得最小值,越应该让其匹配顺序靠后,因为这样他收到其他店的干扰就越小。
由于是字典序最小,我们肯定是让编号小的取到较靠前的位置。
为了防止这些位置被其他点所占据,我们肯定是让编号小的点后匹配
那么对于一个点,我们肯定优先想让其匹配较靠前的点,这个怎么处理?
自然是在加边的时候判一下就好

考虑邻接表,有着“后加的边先跑”的原则。所以我们只需要在加边的时候,先加大的,再加小的,就行了

满足这两个约束条件后,跑出来的匹配是不是字典序最小的匹配呢?
答案是肯定的

若问为何?
他A了不是吗233

完整代码:

#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),add(i,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
*/

嗯,就是这样

来源地址:http://blog.csdn.net/berrykanry/article/details/78229828 版权归作者所有!

相关教程

  • BZOJ 4443 浅谈二分+二分图即四分图性质利用

    世界真的很大 作为二分图的一道经典题在做了这么多二分图之后还没有做过实在是太可惜了 今天讲课提到了这道题知道怎么做但是没写过总觉得心慌 然后1A,哼哼 看题先: description: 小凸和小方是好朋友,小方给小凸一个N*M(N<=M)的矩阵A,要求小秃从其中选出N个数,其中任意两个数字不能在同一行或同一列,现小凸想知道选出来的N个数中第K大的数字的最小值是多少
  • python编程题-拼接最小字典序

    对于一个给定的字符串数组,请找到一种拼接顺序,使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。给定一个字符串数组strs,同时给定它的大小,请返回拼接成的串。测试样例:["abc","de"],2"abcde"python代码# -*- coding:utf-8 -*- class Prior:   &n
  • 浅谈算法和数据结构: 二 基本排序算法

    本篇开始学习排序算法。排序与我们日常生活中息息相关,比如,我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间或者时长排序、买东西会按照销量或者好评度排序、查找文件会按照修改时间排序等等。在计算机程序设计中,排序和查找也是最基本的算法,很多其他的算法都是以排序算法为基础,在一般的数据处理或分析中,通常第一步就是进行排序,比如说二分查找,首先要对数据进
  • (POJ 3687)Labeling Balls [逆top序列] 求按照某种排列方式的字典序最小的top序列

    Labeling Balls Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14922 Accepted: 4372 Description Windy has N balls of distinct weights from 1 unit to N units. Now he tries to
  • 匈牙利算法模板

    #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 100; int n1, n2, m; bool vis[maxn]; int match[maxn]; vector&
  • CCF CSP 2016年12月第4题 压缩编码(区间DP)

    问题描述 试题编号: 201612-4 试题名称: 压缩编码 时间限制: 3.0s 内存限制: 256.0MB 问题描述: 问题描述   给定一段文字,已知单词a1, a2, …, an出现的频率分别t1, t
  • 洛谷 P1118 [USACO06FEB]数字三角形Backward Digit Su…

    题目描述 FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list
  • 51Nod - 1675 序列变换 mobius反演

    题意: lyk有两序列a和b。 lyk想知道存在多少对x,y,满足以下两个条件。 1:gcd(x,y)=1。 2: abx=bay a_{b_x} = b_{a_y} 。 例如若a={1,1,1},b={1,1,1}。那么存在7对,因为除了x=2,y=2或x=3,y=3外都满足条件。 Input 第一行一个数n(1<=n<=100