#include <bits/stdc++.h> using namespace std; #define ll long long #define out cin.tie(0)->sync_with_stdio(false) const int md = 1e9+7; int n, a[514], b[514], p[514]; bool vis[514]; int g[514][514]; //匈牙利算法,求最大匹配数 a -> b bool match(int x) { for (int i = 0; i < n; i++) { if (!vis[i] && g[x][i]) { vis[i] = true; if (p[i] == 0 || match(p[i])) { p[i] = x; return true; } } } return false; } int Hungarian() { int cnt = 0; for (int i = 0; i < n; i++) { memset(vis,0,sizeof(vis)); if (match(i)) cnt++; } return cnt; } int main(int argc, char const *argv[]) { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> b[i]; for (int j = 0; j < n; j++) { if (gcd(a[j],b[i]) == 1) g[j][i] = 1; //改成 g[i][j] = 1; 即可全部通过 } } int cnt = Hungarian(); if (cnt == n) { cout << "Bob" << endl; } else { cout << "Alice" << endl; } //system("pause"); return 0; }
为什么只是图的结点只是换个方向就错了,只能通过95%左右。
全部评论
(2) 回帖