1、题意:题意有些难理解
2、分析:我们发现如果要求判断是否合法的话就so easy了,二分图匹配即可,但是我们发现要求输出字典序最小的,那么我们在匈牙利的时候就倒着枚举,另外邻接表中的边一定要排好序,如果用的是链表的话,就从大到小,vector就从小到大插入,然后我们就可以保证字典序最小了,想了半天网络流QAQ,看了题解。。匈牙利是啥都快忘记了。。。
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; #define M 20010 inline int read(){ char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } struct Edge{ int u, v, next; } G[M]; int head[M], tot; int tim; int pre[M], vis[M]; inline void add(int u, int v){ G[++ tot] = (Edge){u, v, head[u]}; head[u] = tot; } inline bool dfs(int u){ for(int i = head[u]; i != -1; i = G[i].next){ if(vis[G[i].v] != tim){ vis[G[i].v] = tim; if(pre[G[i].v] == -1 || dfs(pre[G[i].v])){ pre[G[i].v] = u; pre[u] = G[i].v; return 1; } } } return 0; } int main(){ memset(head, -1, sizeof(head)); memset(pre, -1, sizeof(pre)); int n = read(); for(int i = 1; i <= n; i ++){ int d = read(); int a = i - d, b = i + d; if(a <= 0) a += n; if(b > n) b -= n; a += n; b += n; if(a < b) swap(a, b); add(i, a); add(i, b); } for(int i = n; i >= 1; i --){ tim ++; if(!dfs(i)){ printf("No Answer"); return 0; } } for(int i = 1; i < n; i ++) printf("%d ", pre[i] - n - 1); printf("%d\n", pre[n] - n - 1); return 0; }