「CodeForces-498C」Array and Operations(数论+网络流)_C

概述「CodeForces-498C」Array and Operations 给定n个点和m个边集，每次 *** 作可以将相连边的两个点值同时除以一个公约数，问最大 *** 作次数题意给定一个长为$n$的数组，以及$m$对下标为$(a,b)$的点对，且满足下标a+b为奇数（即奇数点只与偶数点匹配），每次 *** 作可以将同一组的两个数同时除以一个公约数，问最多能进行多少次 *** 作。解法显然题目所给的是一个二分图。对于

「CodeForces-498C」Array and Operations
给定n个点和m个边集，每次 *** 作可以将相连边的两个点值同时除以一个公约数，问最大 *** 作次数

题意

给定一个长为$n$的数组，以及$m$对下标为$(a,b)$的点对，且满足下标a+b为奇数（即奇数点只与偶数点匹配），每次 *** 作可以将同一组的两个数同时除以一个公约数，问最多能进行多少次 *** 作。

解法

显然题目所给的是一个二分图。

对于每个质因数分开考虑。对于奇数点，向源点连接一个容量为该因子个数的边；对于偶数点，则向汇点建立一个容量为因子数的边；对于有边相连的点对，建立容量为$inf$的边。

对于题给的数组$a[i]$，通过分解质因数的方式计算每个质因数所建图的最大流，求和即为所求解。

代码


#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX_V=200+10;
const int INF=0x3f3f3f3f;


struct {int to,cap,rev;};

vector<edge> G[MAX_V];	//图的邻接表表示
int level[MAX_V];	//顶点到源点的距离标号
int iter[MAX_V];	//当前弧

voID add(int from,int to,int cap)
{
	G[from].push_back((edge){to,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
}

//计算从源点出发的距离标号
voID bfs(int s)
{
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty())
	{
		int v=que.front();que.pop();
		for(int i=0;i<G[v].size();i++)
		{
			edge &e=G[v][i];
			if(e.cap>0&&level[e.to]<0)
			{
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}

//通过DFS寻找增广路
int dfs(int v,int t,int f)
{
	if(v==t) return f;
	for(int &i=iter[v];i<G[v].size();i++)
	{
		edge &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to])
		{
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0)
			{
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}

//求解从s到t的最大流
int max_flow(int s,int t)
{
	int flow=0;
	for(;;)
	{
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter,sizeof(iter));
		int f;
		while((f=dfs(s,INF))>0) flow+=f;
	}
}

int n,m,a[105],u[105],v[105],s,ans=0;

voID solve(int x)
{
    for(int i=0;i<MAX_V;i++) G[i].clear();
    for(int i=1;i<=n;i++)
    {
        int tot=0;
        while(a[i]%x==0) a[i]/=x,tot++;
        if(i%2) add(s,i,tot);
        else add(i,tot);
    }
    for(int i=0;i<m;i++) add(u[i],v[i],INF);
    ans+=max_flow(s,t);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        if(v[i]&1) swap(u[i],v[i]);
    }
    s=0,t=n+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j*j<=a[i];j++)
            if(a[i]%j==0) solve(j);
        if(a[i]>1) solve(a[i]);
    }
    printf("%dn",ans);
    return 0;
}