任意门：http://www.lydsy.com/JudgeOnline/problem.php?id=1562
题目：
对于0,1,…,N-1的N个整数，给定一个距离序列D0,D1,…,DN-1，定义一个变换序列T0,T1,…,TN-1使得每个i,Ti的环上距离等于Di。一个合法的变换序列应是0,1,…,N-1的一个排列，任务是要求出字典序最小的那个变换序列。
题解:
二分建图是显而易见的，可是怎么处理字典序最小？
大神博客：https://www.byvoid.com/blog/noi-2009-transform/
实际倒着做一遍就可以了，正确性显然（只不过我不是这样写的）；
先做最大匹配，然后看所匹配的是否为最小标号，不是则强行改值，然后再做最大匹配看是否有完备匹配，无则将值改回。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 bool vis[30000]; 6 int f[80000],pre[80000],v[80000],now[80000]; 7 int a[20010],b[20010]; 8 int n,ans,tot,cc; 9 void insert(int a, int b) 10 { 11 tot++; pre[tot]=now[a]; now[a]=tot; v[tot]=b; 12 } 13 bool dfs(int x) 14 { 15 if (x<cc) return false; 16 for (int i=now[x]; i; i=pre[i]) 17 { 18 if (!vis[v[i]]) 19 { 20 vis[v[i]]=true; 21 if (f[v[i]]==-1 || dfs(f[v[i]])) 22 { 23 f[v[i]]=x; 24 f[x]=v[i]; 25 return true; 26 } 27 } 28 } 29 return false; 30 } 31 int main() 32 { 33 int d; 34 scanf("%d",&n); 35 tot=0; 36 for (int i=1; i<=n; i++) 37 { 38 scanf("%d",&d); 39 a[i]=(i+d) % n; 40 if (a[i]==0) a[i]=n; 41 b[i]=(i-d); 42 if (b[i]<1) 43 b[i]+=n; 44 if (a[i]>b[i]) 45 { 46 int c; 47 c=a[i]; a[i]=b[i]; b[i]=c; 48 } 49 a[i]+=n; b[i]+=n; 50 insert(i,a[i]); 51 insert(i,b[i]); 52 } 53 memset(f,-1,sizeof(f)); 54 ans=0; 55 for (int i=1; i<=n; i++) 56 { 57 memset(vis,false,sizeof(vis)); 58 if (dfs(i)) ans++; 59 } 60 if (ans<n) { printf("No Answer "); return 0 ;} 61 for (int i=1; i<=n; i++) 62 { 63 if (f[i]!=a[i]) 64 { 65 cc=i; 66 memset(vis,false,sizeof(vis)); 67 int t=f[a[i]]; 68 f[a[i]]=i; 69 f[b[i]]=-1; 70 vis[a[i]]=true; 71 if (dfs(t)) 72 { 73 f[i]=a[i]; 74 } 75 else 76 { 77 f[b[i]]=i; 78 f[a[i]]=t; 79 80 } 81 } 82 } 83 for (int i=1; i<n; i++) 84 { 85 printf("%d ",f[i]-n-1); 86 } 87 printf("%d ",f[n]-n-1); 88 return 0; 89 } 90 91