LightOJ - 1356 Prime Independence（质因数分解，二分图最大独立集）_综合

链接：LightOJ - 1356 Prime Independence

题意：

定义：若 $a$ 是 $b$ 的质数倍，即 $a=k\times b$ （其中 $k$ 为质数），则称 $a$ 、 $b$ 相关联；

给出 $N\,(1\le N\le 40000)$ 个正整数 $x\in [1,500000]$ ，求最大独立集的元素个数？（独立集中任意两个元素均无关联）

分析：

最大独立集问题可以想办法转化为二分图求解，将正整数 按照其质因数分解形式，可以分为 奇数个质数相乘 和 偶数个质数相乘，显然 所有奇数个质数相乘的正整数两两之间，必定无关联，偶数个的同理。

于是，就可以将 $1$ ~ $500000$ 的正整数根据其质因数分解的个数奇偶染色，划分为二分图，再根据关联两两连边，最后求解最大独立集。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int maxn=5e5+10;
int s=0,t=maxn-1;
int head[maxn],cnt;
struct edge
{
    int w;           //边的流量（残量）int to;          //该边通向的结点vint next;        //点u邻接表的下一条边
}e[maxn*2];
void add_edge(int u,int v,int w)   //添加一条u->v，最大容量为w的边
{
    //建立正向边e[cnt].w=w;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;cnt++;//建立反向边e[cnt].w=0;e[cnt].to=u;e[cnt].next=head[v];head[v]=cnt;cnt++;
}
int dis[maxn];     //dis数组记录层次
bool bfs()         //利用BFS建立分成图，从而可以多次DFS增广
{
    memset(dis,-1,sizeof(dis));     //初始化dis数组queue<int> q;q.push(s);dis[s]=0;      //源点层次为0while(!q.empty()){
    int u=q.front();q.pop();for(int i=head[u];i!=-1;i=e[i].next){
    int v=e[i].to;if(e[i].w>0&&dis[v]==-1)     //可达&&未分层{
    dis[v]=dis[u]+1;         //分层if(v==t)                 //若到达汇点，则分层结束，返回truereturn true;q.push(v);}}}return false;  //运行到此处，说明汇点已不可达，返回false
}
int cur[maxn];     //弧优化：cur数组用于记录上一次DFS增广时u已经增广到第几条边，从而优化时间
int dfs(int u,int flow)       //flow代表流入u点的最大流量
{
    if(u==t)return flow;          //到达汇点，直接返回flowfor(int &i=cur[u];i!=-1;i=e[i].next){
                             //注意i前面用&引用，这样就可以直接改变cur[u]int v=e[i].to;if(dis[v]==dis[u]+1&&e[i].w>0)   //v为u的下一层&&可达{
    int k=dfs(v,min(flow,e[i].w));if(k>0){
    e[i].w-=k;         //正向边-=ke[i^1].w+=k;       //反向边+=kreturn k;}}}return 0;       //无法继续增广，返回0
}
int dinic()
{
    int ans=0;      //记录总流量while(bfs())    //分层{
    for(int i=0;i<maxn;i++)    //初始化cur数组，即将head数组赋给cur数组cur[i]=head[i];while(int k=dfs(s,INF))    //增广ans+=k;}return ans;
}
int prime[maxn],tot;
bool vis[maxn];
void get_prime()       //欧拉筛
{
    memset(vis,0,sizeof(vis));tot=0;for(int i=2;i<=5e5;i++){
    if(!vis[i])prime[++tot]=i;for(int j=1;j<=tot&&i*prime[j]<=5e5;j++)   //筛去i*已有质数{
    vis[i*prime[j]]=true;if(i%prime[j]==0)    //控制筛选范围，防止重复筛选break;}}
}
int n;
bool flag[maxn],col[maxn];
int main()
{
    get_prime();col[1]=0;for(int i=1;i<=5e5;i++)for(int j=1;j<=tot&&i*prime[j]<=5e5;j++)    //染色col[i*prime[j]]=!col[i];int T,kase=0;scanf("%d",&T);while(T--){
    memset(head,-1,sizeof(head));memset(flag,0,sizeof(flag));cnt=0;scanf("%d",&n);for(int i=1;i<=n;i++){
    int x;scanf("%d",&x);flag[x]=true;}for(int i=1;i<=5e5;i++){
    if(!flag[i])continue;if(!col[i]){
    add_edge(s,i,1);for(int j=1;j<=tot&&i*prime[j]<=5e5;j++){
    if(flag[i*prime[j]])add_edge(i,i*prime[j],INF);}}else{
    add_edge(i,t,1);for(int j=1;j<=tot&&i*prime[j]<=5e5;j++){
    if(flag[i*prime[j]])add_edge(i*prime[j],i,INF);}}}printf("Case %d: %d\n",++kase,n-dinic());}return 0;
}