【BZOJ1562】[NOI2009] 变换序列（匈牙利算法）

点此看题面

大致题意： 给你一个长度为\(n\)的序列\(D\)，让你找到一个字典序最小的\(n\)的排列\(T\)，满足\(D_i=min(|T_i-i|,n-|T_i-i|)\)。

建图

我想建图应该是比较简单的吧。

对于给定的\(D_i\)，我们可以发现对应的\(T_i\)实际上只有两种取值：

当\(D_i=|T_i-i|\)时，\(T_i=(i+D_i-1)\%n+1\)。

当\(D_i=n-|T_i-i|\)时，\(T_i=(i-D_i+n-1)\%n+1\)。

因此，将\(i\)向这两种取值各连一条边，然后跑匈牙利算法即可。

关于字典序

等等，题目中貌似还要求字典序最小。

让我们来回顾一下匈牙利算法的核心思想：

\(Excerpt\)

匈牙利算法的核心思想就是让位。

我们再回顾一下，匈牙利算法是如何让位的：

\(Excerpt\)

它的让位，通常都是由已匹配好的点给未匹配的点让位。

好，那么我们现在要让字典序最小，肯定就是尽可能要让编号小的数在前面。

换句话说，就是尽可能让编号大的数给编号小的数让位。

综上所述，我们只要倒着做匈牙利匹配，这样求出来的结果一定是字典序最小的。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define uint unsigned int

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define abs(x) ((x)<0?-(x):(x))

#define INF 1e9

#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))

#define ten(x) (((x)<<3)+((x)<<1))

#define N 10000

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

using namespace std;

int n,ee=0,lnk[N+5];

struct edge

{

    int to,nxt;

}e[2*N+5];

class FIO

{

    private:

        #define Fsize 100000

        #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)

        #define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))

        int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];

    public:

        FIO() {FinNow=FinEnd=Fin;}

        inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}

        inline void read_char(char &x) {while(isspace(x=tc()));}

        inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}

        inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}

        inline void write_char(char x) {pc(x);}

        inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}

        inline void end() {fwrite(Fout,1,FoutSize,stdout);}

}F;

class Class_HungarianAlgorithm//匈牙利算法

{

    private:

        int s[N+5],t[N+5],vis[N+5];

    public:

        inline bool Match(int x,int Time)

        {

            for(register int i=lnk[x];i;i=e[i].nxt)

            {

                if(!(vis[e[i].to]^Time)) continue;

                vis[e[i].to]=Time;

                if(!s[e[i].to]||Match(s[e[i].to],Time)) return s[e[i].to]=x,true;

            }

            return false;

        }

        inline void PrintAns() {register int i;for(i=1;i<=n;++i) t[s[i]]=i-1;for(i=1;i<=n;++i) F.write(t[i]),F.write_char(' ');}

}HungarianAlgorithm;

int main()

{

    register int i,x,s1,s2;

    for(F.read(n),i=1;i<=n;++i) F.read(x),s1=(i+x-1)%n+1,s2=(i-x+n-1)%n+1,add(i,max(s1,s2)),add(i,min(s1,s2));//建边

    for(i=n;i;--i) if(!HungarianAlgorithm.Match(i,i)) return puts("No Answer"),0;//倒着做匈牙利算法，这样的结果一定是字典序最小的

    return HungarianAlgorithm.PrintAns(),F.end(),0;

}

巴特西

【BZOJ1562】[NOI2009] 变换序列（匈牙利算法）

建图

关于字典序

\(Excerpt\)

\(Excerpt\)

代码

最新文章

热门文章