科技公司 网站设计经典案例,wordpress带会员主题,wordpress 导航 防刷新,58网络推广Description Input Output Sample Input 5 1 1 2 2 1Sample Output 1 2 4 0 3HINT 30%的数据中N≤50#xff1b;60%的数据中N≤500#xff1b;100%的数据中N≤10000。 Source 这题是二分图应该不难看出来。 对于原序列中的一个点#xff0c;对应两个可匹配的点。 关键是怎么…Description Input Output Sample Input 5 1 1 2 2 1 Sample Output 1 2 4 0 3 HINT 30%的数据中N≤5060%的数据中N≤500100%的数据中N≤10000。 Source 这题是二分图应该不难看出来。 对于原序列中的一个点对应两个可匹配的点。 关键是怎么保证字典序最小 如果是暴力删边匈牙利的话是$O(n^3)$的。 这里有两种解决方法 1.强制让$x$号点连向字典序小的点对失配的点重新匹配 2.将所有边按照字典序排序优先选择最小的。 同时在匈牙利的时候从最大的往最小的枚举 这实际上利用了匈牙利“抢” 的思想。 如之前的已经匹配过那么字典序小的会抢字典序大的匹配。同时又因为每次选的是字典序最小的。因此答案可以保证是最优的。 #includecstdio
#includevector
#includealgorithm
#includecstring
const int INF 1e9 10, MAXN 1e5 10;
using namespace std;
inline int read() {char c getchar(); int x 0, f 1;while(c 0 || c 9) {if(c -) f -1; c getchar();}while(c 0 c 9) x x * 10 c - 0, c getchar();return x * f;
}
int N;
int a[MAXN];
int match[MAXN], vis[MAXN], cur;
vectorint v[MAXN];
void AddEdge(int x, int y) {v[x].push_back(y); v[y].push_back(x);
}
bool Argue(int x) {for(int i 0; i v[x].size(); i) {int to v[x][i];if(vis[to] cur) continue;vis[to] cur; if(match[to] -1 || Argue(match[to])) {match[to] x;return true;}}return false;
}
void Hug() {int ans 0;for(int i N - 1; i 0; i--) {cur;if(!Argue(i)) {printf(No Answer); exit(0);}} for(int i 0; i N; i) match[match[i N]] i;for(int i 0; i N; i) printf(%d , match[i]);
}
main() {
#ifdef WIN32freopen(a.in, r, stdin);freopen(a.out, w, stdout);
#endifmemset(match, -1, sizeof(match));N read();for(int i 0; i N; i) {int x read();AddEdge(i, (i x) % N N);AddEdge(i, (i - x N) % N N);}for(int i 0; i N 1; i) sort(v[i].begin(), v[i].end());Hug();
}
