bzoj1562 [NOI2009]变换序列

Description

Input

Output

Sample Input

Sample Output

HINT

正解：匈牙利算法。

这题给他们考试。。没人想到二分图匹配。有两人想到用网络流做可行解，给了4分部分分，其他人都是爆搜。。实在觉得这题不是很难吧。。

看完题目以后就能发现这是一道裸的二分图匹配。如果用网络流做，dinic无法保证最优解，EK会超时。那么可以考虑用匈牙利算法。只要保证遍历与一个点相连的边按照相连点从小到大的顺序就行，因为对于单一的一个点来说，如果增广了一条路径就不会再增广了。而对于全局则从最后一个点开始增广，因为后增广的路径会覆盖掉先增广的路径。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;int g[30010][5],match[30010],vis[30010],n;il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il int dfs(RG int x,RG int cnt){    for (RG int i=1;i<=2;++i){	RG int v=g[x][i]; if (vis[v]==cnt) continue; vis[v]=cnt;	if (match[v]==-1 || dfs(match[v],cnt)){	    match[v]=x,match[x]=v; return 1;	}    }    return 0;}il void work(){    n=gi(); RG int x,flag=1,cnt=0;    for (RG int i=0;i<n;++i){	x=gi(); g[i][1]=i+x; if (g[i][1]>=n) g[i][1]-=n;	g[i][2]=i-x; if (g[i][2]<0) g[i][2]+=n;	if (g[i][1]>g[i][2]) swap(g[i][1],g[i][2]);	g[i][1]+=n,g[i][2]+=n;    }    memset(match,-1,sizeof(match));    for (RG int i=n-1;i>=0;--i) if (!dfs(i,++cnt)){ flag=0; break; }    if (!flag){ PRintf("No Answer"); return; } printf("%d",match[0]-n);    for (RG int i=1;i<n;++i) printf(" %d",match[i]-n); return;}int main(){    File("transform");    work();    return 0;}