匈牙利算法 - Luogu 1963 变换序列

P1963 变换序列

题目描述

---

考试时乱水了20分，还不如暴力

之后我一看

发现每一个i最多有2个能与之匹配的T[i]

明显的不带权二分图匹配

可以用匈牙利算法

但是

在匈牙利算法匹配当中，如何才能保证字典序最小呢？

其实就是从后往前寻找匹配，且优先匹配小的T（即连边时小的在前）。

然后就可以兴奋的水过这一题了

其实我考试时把正解写挂了

代码蒯上

#include<iostream>

#include<iomanip>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

inline int gotcha()

{

    register char c = getchar();register long long x = 0, z = 1;

    for(;c>'9'||c<'0';c=getchar())z=c=='-'?-1:1;

    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';

    return x*z;

}

const int _ = 10002;

int n,d[_],to[_]={0},ans[_],e[_][3]={0};

bool ed[_]={0};

int dis(int x,int y){return min(abs(x-y),n-abs(x-y));}

bool finder(int now)

{

    for(int i=1;i<=2;i++)

    {

        if(ed[e[now][i]])continue;

        ed[e[now][i]]=1;

        if(to[e[now][i]]==-1 || finder(to[e[now][i]]))

        {to[e[now][i]]=now;return 1;}

    }

    return 0;

}

int main()

{

    register int i,j,k;

    n=gotcha();

    for(i=0;i<n;i++)d[i]=gotcha();

    for(i=0;i<n;i++)

    {

        j=(i+d[i])%n,k=(i-d[i]+n)%n;

        if(j>k)swap(j,k);

        e[i][1]=j;e[i][2]=k;

        to[i]=-1;

    }

    for(i=n-1;i>=0;i--)

    {

        memset(ed,0,sizeof(ed));

        if(!finder(i))

        {

            printf("%s","No Answer");

            return 0;

        }

    }

    for(i=0;i<n;i++)ans[to[i]]=i;

    for(i=0;i<n;i++)printf("%d ",ans[i]);

    return 0;

}

---

%%%Rank1 XZZ!