[NOI2009]变换序列（二分图匹配）

我们先不考虑字典序最小，先来求出一种可行解。

不难发现，对于每一个i值，它所对应的T值在模n意义下最多两个，于是我们可以用二分图匹配来判断。

那字典序最小呢？

回顾一下二分图匹配的算法：网络流？貌似不好做到字典序最小，所以我们来看匈牙利算法

匈牙利算法是从1~n枚举点，看是否能合法，如果它要的边没被连就连，如果被连过了就一直判断是否有办法可以让前面的匹配换一种连接方式，便是用这种连边方式。

如果实在没有办法了，就只能委屈一下自己了。

那么这样匹配能否使字典序最小呢？

显然是不行的，即使我们让第一条边找到了字典序最小的点，如果后面的点请求更换，而且正好又可以更换找到更大匹配，那么就不一定是字典序最小了（毒瘤）。

那么我们可以怎么做呢？

我们逆向思维，考虑从后往前加边，后面边先选字典序小的，如果前面的边需要就直接给了，这样就可以保证字典序最小了。

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define re register

#define debug printf("Now is Line : %d\n",__LINE__)

il int read()

{

    re int x=0,f=1; re char c=getchar();

    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return x*f;

}

#define maxn 10005

int n,m,d[maxn],aa[2][maxn],vis[maxn],cnt,ans,match[maxn],to[maxn];

bool dfs(int u)

{

    for(re int i=0;i<2;++i)

    {

        int v=aa[i][u];

        if(vis[v]) continue;

        vis[v]=1;

        if(match[v]==-1||dfs(match[v])) return match[v]=u,to[u]=v,1;

    }

    return 0;

}

int main()

{

    n=read();

    memset(match,-1,sizeof(match));

    for(re int i=0;i<n;++i) d[i]=read();

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

    {

        int a=(i-d[i]+n)%n,b=(i+d[i])%n;

        if(a>b) swap(a,b);

        aa[0][i]=a,aa[1][i]=b;

    }

    for(re int i=n-1;~i;--i)

    {

        memset(vis,0,sizeof(vis));

        if(dfs(i)) ++ans;

    }

    if(ans<n) return puts("No Answer"),0;

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

    return 0;

}

巴特西

[NOI2009]变换序列（二分图匹配）

最新文章

热门文章