lg1963[NOI2009]变换序列 发表于 2018-03-30 | 分类于 算法 , 图论 , 二分图匹配 | 阅读数 次 链接:lg1963[NOI2009]变换序列 题解这题难点在于要求字典序最小的匹配 首先建图的时候要先连大的点,因为处理的时候,是倒序 匈牙利算法是当前点无法匹配的时候尝试更改之前匹配的点,所以倒着匈牙利就可以保证小的点优先匹配小的点 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e5;struct node{ int v,nxt; inline void init(int a,int b){v=a;nxt=b;}}e[N];int mark[N],n,vis[N],head[N],cnt,ans;inline int solve(int x){if(x<0)x+=n; if(x>n-1)x-=n; return x+n;}void add(int u,int x){ int v1=solve(u+x),v2=solve(u-x); if(v1<v2)swap(v1,v2); e[++cnt].init(v1,head[u]);head[u]=cnt; e[++cnt].init(v2,head[u]);head[u]=cnt;}int find(int x){ vis[x]=1; for(int i=head[x],v;i;i=e[i].nxt)if(!vis[v=e[i].v]){ vis[v]=1; if(!mark[v]||find(mark[v])){ mark[v]=x;mark[x]=v; return 1; } } return 0;}int r(){ repd(i,n-1,0)if(!mark[i]){ memset(vis,0,sizeof(vis)); ans+=find(i); } return ans==n;}int main(){ scanf("%d",&n); rep(i,0,n-1){int x;scanf("%d",&x); add(i,x);} if(r())rep(i,0,n-1)printf("%d ",mark[i]-n); else puts("No Answer"); return 0;}