首页 > 代码库 > [HDOJ5943]Kingdom of Obsession（最大匹配，思路）

[HDOJ5943]Kingdom of Obsession（最大匹配，思路）

2024-08-19 03:23:23   218人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5943

题意：n个人编号为[s+1,s+n]，有n个座位编号为[1,n]，编号为i的人只能坐到编号为它的约数的座位，问每个人是否都有位置坐。

首先，可以肯定的是素数编号的人只能做到自己的编号上或者是1上，那么假如[s+1,s+n]区间内出现了两个以上的素数，那么整个情况是无解的。

其次，假如s<n的话，可以把[s+1,s+n]直接放到[s+1,s+n]上，剩下的将会是s个人和s个座位，人的编号是[n+1,n+s]，座位的编号是[s+1,s+n]，所以直接给s和n交换一下就行。

我断定1000个数之间一定会出现至少两个素数，因此当n>1000的时候就是无解了。

接下来就是O(n^2)，按照能否整除建图了，跑出最大匹配，看看跟n是不是相等就行了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1010;
 5 int nu, nv;
 6 int G[maxn][maxn];
 7 int linker[maxn];
 8 bool vis[maxn];
 9 int s, n;
10 
11 bool dfs(int u) {
12     for(int v = 1; v <= nv; v++) {
13         if(G[u][v] && !vis[v]) {
14             vis[v] = 1;
15             if(linker[v] == -1 || dfs(linker[v])) {
16                 linker[v] = u;
17                 return 1;
18             }
19         }
20     }
21     return 0;
22 }
23 
24 int hungary() {
25     int ret = 0;
26     memset(linker, -1, sizeof(linker));
27     for(int u = 1; u <= nu; u++) {
28         memset(vis, 0, sizeof(vis));
29         if(dfs(u)) ret++;
30     }
31     return ret;
32 }
33 
34 int main() {
35     // freopen("in", "r", stdin);
36     int T, _ = 1;
37     scanf("%d", &T);
38     while(T--) {
39         scanf("%d %d", &s, &n);
40         memset(G, 0, sizeof(G));
41         printf("Case #%d: ", _++);
42         if(s < n) swap(s, n);
43         if(n > 1000) {
44             puts("No");
45             continue;
46         }
47         nu = 2 * n, nv = n;
48         for(int i = 1; i <= n; i++) {
49             for(int j = 1; j <= n; j++) {
50                 if((s + i) % j == 0) G[i+n][j] = 1;
51             }
52         }
53         if(hungary() == n) puts("Yes");
54         else puts("No");
55     }
56     return 0;
57 }

 

[HDOJ5943]Kingdom of Obsession（最大匹配，思路）


联系
我们