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

Description

Input

Output

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的时候要注意一下先后顺序

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #define N (10000+100)
 7 using namespace std;
 8 struct node
 9 {
10     int to,next;
11 } edge[N*4];
12 int n,x,from[N],to[N],head[N],num_edge,used[N],now,a[10];
13 
14 void add(int u,int v)
15 {
16     edge[++num_edge].to=v;
17     edge[num_edge].next=head[u];
18     head[u]=num_edge;
19 }
20 
21 bool check(int x,int y,int ans)
22 {
23     if (y<0 || y>=n) return false;
24     if (min(abs(x-y),n-abs(x-y))==ans) return true;
25     return false;
26 }
27 
28 bool find(int x)
29 {
30     for (int i=head[x];i!=0;i=edge[i].next)
31         if (used[edge[i].to]!=now)
32         {
33             used[edge[i].to]=now;
34             if (!to[edge[i].to] || find(to[edge[i].to]))
35             {
36                 to[edge[i].to]=x;
37                 from[x]=edge[i].to;
38                 return true;
39             }
40         }
41     return false;
42 }
43 
44 int main()
45 {
46     memset(used,0x7f,sizeof(used));
47     scanf("%d",&n);
48     for (int i=0;i<=n-1;++i)
49     {
50         scanf("%d",&x);
51         a[1]=i+x,a[2]=i-x,a[3]=i+(n-x),a[4]=i-(n-x);
52         sort(a+1,a+4+1);
53         if (check(i,a[4],x)) 
54             add(i,a[4]);
55         if (check(i,a[3],x)) 
56             add(i,a[3]);
57         if (check(i,a[2],x)) 
58             add(i,a[2]);
59         if (check(i,a[1],x)) 
60             add(i,a[1]);
61         
62     }
63     
64     int ans=0;
65     for (int i=n-1;i>=0;--i)
66     {
67         now=i;
68         if (find(i)) ans++;
69         else break;
70     }
71     if (ans!=n)
72         printf("No Answer");
73     else
74     {
75         for (int i=0;i<=n-2;++i)
76             printf("%d ",from[i]); 
77         printf("%d",from[n-1]);
78     }    
79 }