HDOJ 5943 Kingdom of Obsession【2016杭州现场赛】【二分图匹配暴力】

现场赛的铜牌题，没有搞出来挺遗憾的

题意：如果i%j==0，那么说（i，j）是可以匹配的

题目问：（s+1，s+2，……，s+n），（1，2，……，n）这两个数组能否找到某种对应方式，使得完全匹配（也就是说等于n）

一开始的思路是：素数是很特殊的数，当值很大的时候，（s+1，s+2，……，s+n）不能出现两个素数

但是这个判定条件其实很奇怪：因为不知道怎么定义值很大

那么：想着小数据打表：什么叫做小数据呢？

n很小：因为二分图匹配的算法是O（NM），所以不妨定在1000

这个范围内的直接跑算法

那么当n比较大的时候呢？直接输出no吗？

思路接近了，但是有一种很极端的情况

n=1001，s=1

这组数据的意思是：（2，3，4，……，1002）来匹配（1，2，3，4，……，1001）

发现什么了吗？中间有很多个数都是重复的！重复的数是一定可以自己匹配自己的

那么这组算大数据吗？！不算：因为s很小

所以，如果n很大，s很小，会有很多个重叠的部分：先删去重叠的，然后暴力匹配

当n很大，s也很大：直接输出no

其实是有理论依据的：因为n和s都是大于1000的

在1e9的范围内，相邻两个素数的最大距离是300+

那么意味着，在（s+1，s+2，……，s+n）中，删去与（1，2，……，n）重复的部分，肯定是有两个素数的，他们是不可能同时匹配到1的

理论上的一个文字证明吧

代码如下：（我的ccpc的铜牌，桑心）

#include<bits/stdc++.h>
using namespace std;

const int maxn=1050;
int uN,vN;
int T,n,s;
int g[maxn][maxn];
int linker[maxn];
bool used[maxn];

bool dfs(int u){
    for(int v=0;v<vN;v++)
    if (g[u][v]&&!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=0;u<uN;u++){
        memset(used,false,sizeof(used));
        if (dfs(u)) res++;
    }
    return res;
}

int main(){
    scanf("%d",&T);
    for(int Case=1;Case<=T;Case++){
        scanf("%d%d",&n,&s);
        memset(g,0,sizeof(g));
        if (n<=1000){
            uN=vN=n;
            for(int i=s+1;i<=s+n;i++)
                for(int j=1;j<=n;j++)
                    if (i%j==0)
                        g[i-s-1][j-1]=1;
            if (hungary()==n)
                printf("Case #%d: Yes\n",Case);
            else
                printf("Case #%d: No\n",Case);
        }
        else if (s<=1000){
            uN=vN=s;
            for(int i=n+1;i<=n+s;i++)
                for(int j=1;j<=s;j++)
                    if (i%j==0)
                        g[i-n-1][j-1]=1;
            if (hungary()==s)
                printf("Case #%d: Yes\n",Case);
            else
                printf("Case #%d: No\n",Case);
        }
        else
            printf("Case #%d: No\n",Case);
    }
    return 0;
}