BZOJ 1562 [NOI2009] 变换序列

野性酷女 2021-12-17 07:17 206阅读 0赞

[\[NOI2009\] 变换序列][NOI2009_]

\[题解\]

就是有一个序列，每个位置可以填两个数，不可重复，问最小字典序。

显然，可以建一个二分图，判合法就是找完美匹配。

那怎么弄最小字典序呢？有好多种解法，我这里给出了两种。

解法一:

先求出它的一个完美匹配，把每个点扫一遍，如果它连的点是它能连的最小的了，就不管他，否则强制将当前节点与其能连的最小点对应，这时从这个点找增广路，如果有，就算修正成功，否则修正失败。

这个方法的好处是通用，时间复杂度O(n\*n)

解法二：

从最后一个点开始求增广路，求增广路时优先考虑序号较小点。

证明：[daolao博客][daolao]。

代码：

这里给出解法二的代码。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cmath>
    #include<queue>
    #define SIZE 100005
    #define rint register int
    using namespace std;
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
        return x*f;
    }
    inline void write(int x)
    {
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
        return ;
    }
    
    int n,match[SIZE],ans[SIZE],cnt;
    int d[SIZE],vis[SIZE],f[3][SIZE];
    
    int dfs(int x)
    {
        for(rint i=1;i<=2;++i)
        {
            int y=f[i][x];if(vis[y]) continue;
            vis[y]=1;
            if(match[y]==-1 || dfs(match[y]))
            {
                match[y]=x;ans[x]=y;
                return 1;
            }
        }
        return 0;
    }
    
    inline void clear()
    {
        memset(match,-1,sizeof(match));
        memset(ans,0,sizeof(ans));
    }
    
    int main()
    {
        n=read();clear();
        for(rint i=0;i<n;++i) d[i]=read();
        for(rint i=0;i<n;++i)
        {
            int a=(i-d[i]+n)%n,b=(i+d[i])%n;
            if(a>b) swap(a,b);
            f[1][i]=a,f[2][i]=b;
        }
        for(rint i=n-1;i>=0;--i)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ++cnt;
        }
        if(cnt<n) return puts("No Answer"),0;
        for(rint i=0;i<n;++i)
        {
            write(ans[i]);
            if(i!=n) cout<<" ";
        } 
        return 0;
    }

转载于:https://www.cnblogs.com/mxrmxr/p/10350636.html

[NOI2009_]: https://www.lydsy.com/JudgeOnline/problem.php?id=1562
[daolao]: https://www.byvoid.com/zhs/blog/noi-2009-transform
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211217/4658d413432643fea515249f3529f5f1.png