HDU - 5943 Kingdom of Obsession（二分匹配+素数）

Kingdom of Obsession

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2799    Accepted Submission(s): 835

Problem Description

There is a kindom of obsession, so people in this kingdom do things very strictly.

They name themselves in integer, and there are n people with their id continuous (s+1,s+2,⋯,s+n) standing in a line in arbitrary order, be more obsessively, people with id x wants to stand at yth position which satisfy

xmody=0

Is there any way to satisfy everyone's requirement?

 Input

First line contains an integer T, which indicates the number of test cases.

Every test case contains one line with two integers n, s.

Limits
1≤T≤100.
1≤n≤109.
0≤s≤109.

 Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.

If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.

 Sample Input

2 5 14 4 11

 Sample Output

Case #1: No Case #2: Yes

 Source

2016年中国大学生程序设计竞赛（杭州）

显然有两个s+1到s+1+n内有两个素数肯定输出No，因为两个连续的素数的间隔非常小，直接跑二分匹配就行了

/* 题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5943
题目大意：　　
给定S，N，把S+1，S+2，...S+N这N个数填到1,2,...,N里，要求X只能填到X的因子的位置。
（即X%Y=0，那么X才能放在Y位置）    问是否能够放满。
题目思路：  【二分图匹配 匈牙利算法】 首先，如果S<N,那么S+1，S+2...N这些数直接放在S+1,S+2...N的位置上
(如果其他数x放在这些位置上面，这些数不放在对应位置，那么x一定能放在这些数放的位置，所以直接交换即可)
所以可以直接将S和N调换，缩小N。接着看N个连续的数，如果出现2个素数。那么必然无解(都只能放1)所以可以估算一下素数的最大间隔(我取504),N超过必然无解。
N小于504的情况下，直接暴力建边（能整除就连边），然后跑二分图匹配即可
摘自：http://blog.csdn.net/u010568270/article/details/52965762*/

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1025;
const int MAXM = 1025 * 1025;
struct Edge
{
    int to,next;
}edge[MAXM];
int tot,head[MAXN];
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
int linker[MAXN];
bool used[MAXN];
int uN;
bool dfs(int u)
{
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(!used[v]) {
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v])) {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary()
{
    int res = 0;
    memset(linker,-1,sizeof(linker));
    for(int u = 1; u <= uN; u++) {
        memset(used,false,sizeof(used));
        if(dfs(u)) res++;
    }
    return res;
}
int main(void)
{
    int T,kase = 0,n,s;
    scanf("%d",&T);
    while(T--) {
        kase++;
        init();
        scanf("%d %d",&n,&s);
        if(s < n) swap(n,s);
        if(n >= 504) {
            printf("Case #%d: No\n",kase);
            continue;
        }
        else {
            uN = n;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if((i + s) % j == 0) {
                        addedge(i + n,j);
                        addedge(j,i + n);
                    }
                }
            }
            if(hungary() == n) printf("Case #%d: Yes\n",kase);
            else printf("Case #%d: No\n",kase);
        }
    }
    return 0;
}