同学聚会怎么样做网站,seo教程论坛,企业网站制作的方法,网站建设公司佛山number#xff1a;数学二分图匹配 首先#xff0c;如果SN,那么S1#xff0c;S2...N这些数直接放在S1,S2...N的位置上(如果其他数x放在这些位置上面#xff0c;这些数不放在对应位置#xff0c;那么x一定能放在这些数放的位置#xff0c;所以直接交换即可)所以可以直接…number数学二分图匹配 首先如果SN,那么S1S2...N这些数直接放在S1,S2...N的位置上(如果其他数x放在这些位置上面这些数不放在对应位置那么x一定能放在这些数放的位置所以直接交换即可)所以可以直接将S和N调换缩小N。接着看N个连续的数如果这里面有两个素数则肯定无解而在1e9的范围内素数间隔最大是低于600的我们就可以通过二分图匹配si与其因数建边求出最大匹配若最大匹配为N则为Yes。实际上能满足的N其实最大为30多而菜菜的jyb只枚举到了很多20多的答案所以为了卡掉暴力匹配的做法但还是很良心地给了5个点不得不多设置了很多数据组数。 迷之数学规律n600时就会至少有两个素数出现不符合题意然后我们一下子就将1e9的数据变成了n600之后进行裸的二分图匹配即可代码如下 #includebits/stdc.h
using namespace std;
const int maxn1010;
const int N605;
bool vis[maxn];
int match[maxn];
int ditu[N][N];
int T,n,s;
bool dfs(int x)//匈牙利算法
{if(x0){return false;}for(int i1;in;i){if(!vis[i] ditu[i][x]){vis[i]true;if(!match[i]||dfs(match[i])){match[i]x;return true;}}}return false;
}
int main()
{freopen(number.in,r,stdin);freopen(number.out,w,stdout);scanf(%d,T);while(T--){scanf(%d%d,n,s);if(sn){swap(s,n);}if(n600){printf(No\n);continue;}memset(ditu,0,sizeof(ditu));for(int i1;in;i){for(int j1;jn;j){if((is)%j0)//能够整除的数之间建边这段代码的灵魂所在{ditu[i][j]1;}}}memset(match,0,sizeof(match));int ans0;for(int i1;in;i){memset(vis,0,sizeof(vis));if(dfs(i)){ans;}}if(ansn){printf(Yes\n);}else{printf(No\n);}}return 0;
} 转载于:https://www.cnblogs.com/LJB666/p/10665230.html
