[题解]
就是有一个序列，每个位置可以填两个数，不可重复，问最小字典序。
显然，可以建一个二分图，判合法就是找完美匹配。
那怎么弄最小字典序呢？有好多种解法，我这里给出了两种。
解法一:
先求出它的一个完美匹配，把每个点扫一遍，如果它连的点是它能连的最小的了，就不管他，否则强制将当前节点与其能连的最小点对应，这时从这个点找增广路，如果有，就算修正成功，否则修正失败。
这个方法的好处是通用，时间复杂度O(n*n)
解法二：
从最后一个点开始求增广路，求增广路时优先考虑序号较小点。
证明：daolao博客。
代码：
这里给出解法二的代码。
#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
