通过这道模板题学了一种新的模型, 记录一下.
稳定婚姻匹配 https://www.cnblogs.com/AndyJee/p/4986741.html
至于这道题, 显然是一个二分图博弈的模型. 考虑选择 Bob, 我们要找一组匹配使得任何情况下 Bob 都有匹配边能走. 不失一般性假设 Alice 选择了 increase, 起点选在左侧, 那么一组匹配合法当且仅当不存在匹配 \((i,j),(k,l)\) 使得 \(w_{i,j}<w_{j,k}<w_{k,l}\). 令左到右的权值为原边权, 右到左的权值为原边权的相反数, 用链接内的算法一定能找到完美匹配.
- #include<bits/stdc++.h>
- using namespace std;
- int gi() {
- int x = 0, o = 1;
- char ch = getchar();
- while((ch <'0' || ch> '9') && ch != '-') {
- ch = getchar();
- }
- if(ch == '-') {
- o = -1, ch = getchar();
- }
- while(ch>= '0' && ch <= '9') {
- x = x * 10 + ch - '0', ch = getchar();
- }
- return x * o;
- }
- int n, a[60][60], p[110], v[60], x;
- vector<int> E[60];
- bool cmp(int x, int y) {
- return v[x]> v[y];
- }
- int main() {
- int T = gi();
- while(T--) {
- n = gi();
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= n; j++) {
- a[i][j] = gi();
- }
- cout <<"B\n", cout.flush();
- if((getchar() == 'D') ^ ((x = gi())> n))
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= n; j++) {
- a[i][j] = -a[i][j];
- }
- memset(p, 0, sizeof(p));
- for(int i = 1; i <= n; i++) {
- E[i].resize(n);
- for(int j = 1; j <= n; j++) {
- v[j] = a[i][j], E[i][j - 1] = j;
- }
- sort(E[i].begin(), E[i].end(), cmp);
- }
- int m = n;
- while(m)
- for(int i = 1, j; i <= n; i++)
- if(!p[i])
- while(1) {
- j = E[i].back(), E[i].pop_back();
- if(!p[j + n]) {
- p[i] = j + n;
- p[j + n] = i;
- --m;
- break;
- } else if(a[i][j]> a[p[j + n]][j]) {
- p[p[j + n]] = 0;
- p[i] = j + n;
- p[j + n] = i;
- break;
- }
- }
- while(1) {
- cout << p[x] << '\n';
- cout.flush();
- x = gi();
- if(x < 0) {
- break;
- }
- }
- }
- return 0;
- }
- [CF1161F]Zigzag Game
来源: http://www.bubuko.com/infodetail-3049218.html