1562. [NOI2009]变换序列【二分图】

Description

1562. [NOI2009]变换序列【二分图】

Input

1562. [NOI2009]变换序列【二分图】

Output

1562. [NOI2009]变换序列【二分图】

Sample Input

5
1 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的数据中N≤50;
60%的数据中N≤500;
100%的数据中N≤10000。

匈牙利裸题
因为要注意字典序
所以加边还有find的时候要注意一下先后顺序

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N (10000+100)
using namespace std;
struct node
{
int to,next;
} edge[N*];
int n,x,from[N],to[N],head[N],num_edge,used[N],now,a[]; void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} bool check(int x,int y,int ans)
{
if (y< || y>=n) return false;
if (min(abs(x-y),n-abs(x-y))==ans) return true;
return false;
} bool find(int x)
{
for (int i=head[x];i!=;i=edge[i].next)
if (used[edge[i].to]!=now)
{
used[edge[i].to]=now;
if (!to[edge[i].to] || find(to[edge[i].to]))
{
to[edge[i].to]=x;
from[x]=edge[i].to;
return true;
}
}
return false;
} int main()
{
memset(used,0x7f,sizeof(used));
scanf("%d",&n);
for (int i=;i<=n-;++i)
{
scanf("%d",&x);
a[]=i+x,a[]=i-x,a[]=i+(n-x),a[]=i-(n-x);
sort(a+,a++);
if (check(i,a[],x))
add(i,a[]);
if (check(i,a[],x))
add(i,a[]);
if (check(i,a[],x))
add(i,a[]);
if (check(i,a[],x))
add(i,a[]); } int ans=;
for (int i=n-;i>=;--i)
{
now=i;
if (find(i)) ans++;
else break;
}
if (ans!=n)
printf("No Answer");
else
{
for (int i=;i<=n-;++i)
printf("%d ",from[i]);
printf("%d",from[n-]);
}
}
上一篇:EUI Scroller实现图片轮播 组件 ItemScroller


下一篇:原生Javascript实现图片轮播效果