P2065 [TJOI2011]卡片

真·会了网络流，忘了匈牙利

一共两种颜色，很容易想到二分图劈配

虽然这题数据水

但是，数据强的话肯定会卡掉的。

为什么？我暴力质因数都过了

我们可以在两边的数与质因数相连。然后跑网络流。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

struct node

{

	int point;

	int value;

	int nxt;

};

node line[500000];

int head[500000],tail=-1;

void add(int x,int y,int dis,int base)

{

	line[++tail].point=y;

	if(base)

		line[tail].value=dis;

	line[tail].nxt=head[x];

	head[x]=tail;

	return ;

}

int read()

{

	int s=0;

	char in=getchar();

	while(in<'0'||in>'9')

		in=getchar();

	while(in>='0'&&in<='9')

	{

		s=(s<<1)+(s<<3)+in-'0';

		in=getchar();

	}

	return s;

}

int blue[500000],red[500000];

int pos[500000];

int cur[500000];

queue<int>q;

int dep[500000];

int tot;

bool bfs(int begin,int end)

{

	for(int i=0;i<=tot;i++)

		cur[i]=head[i];

	while(!q.empty())

		q.pop();

	memset(dep,0,sizeof(dep));

	dep[begin]=1;

	q.push(begin);

	while(!q.empty())

	{

		int pas=q.front();q.pop();

		for(int i=head[pas];i!=-1;i=line[i].nxt)

			if(!dep[line[i].point]&&line[i].value)

			{

				dep[line[i].point]=dep[pas]+1;

				q.push(line[i].point);

			}

	}

	if(dep[end])

		return true;

	return false;

}

int dfs(int now,int aim,int limte)

{

	if(now==aim||!limte)

		return limte;

	int flow=0,f;

	for(int i=cur[now];i!=-1;i=line[i].nxt)

	{

		cur[now]=i;

		if(dep[line[i].point]==dep[now]+1&&(f=dfs(line[i].point,aim,min(limte,line[i].value))))

		{

			limte-=f;

			flow+=f;

			line[i].value-=f;

			line[i^1].value+=f;

			if(!limte)

				break;

		}

	}

	return flow;

}

int dinic(int begin,int end)

{

	int res=0;

	while(bfs(begin,end))

		res+=dfs(begin,end,0x7fffffff);

	return res;

}

bool not_prime[1100000];

int prime[100000],_tail;

void work()

{

	not_prime[0]=not_prime[1]=true;

	for(int i=2;i<=1000000;i++)

	{

		if(!not_prime[i])

			prime[++_tail]=i;

		for(int j=1;j<=_tail;j++)

		{

			if(prime[j]*i>=1000000)

				break;

			not_prime[prime[j]*i]=true;

			if(prime[j]%i==0)

				break;

		}

	}

	return ;

}

int main()

{

	int t=read();

	work();

	while(t--)

	{

		tot=0;

		memset(head,-1,sizeof(head));

		memset(pos,0,sizeof(head));

		int m=read(),n=read();

		tot=m+n+1;

		int now=1;

		for(int i=1;i<=m;i++)

		{

			blue[i]=read();

			add(0,now,1,1);

			add(now,0,1,0);

			now+=1;

		}

		for(int i=1;i<=n;i++)

		{

			red[i]=read();

			add(now,tot,1,1);

			add(tot,now,1,0);

			now+=1;

		}

		now=1;

		for(int i=1;i<=m;i++)

		{

			for(int j=1;blue[i]!=1;j++)

			{

				if(!(blue[i]%prime[j]))

				{

					if(!pos[prime[j]])

						pos[prime[j]]=++tot;

					add(now,pos[prime[j]],1,1);

					add(pos[prime[j]],now,1,0);

					while(!(blue[i]%prime[j]))

						blue[i]/=prime[j];

				}

			}

			now+=1;

		}

		for(int i=1;i<=n;i++)

		{

			for(int j=1;red[i]!=1;j++)

			{

				if(!(red[i]%prime[j]))

				{

					if(!pos[prime[j]])

						pos[prime[j]]=++tot;

					add(pos[prime[j]],now,1,1);

					add(now,pos[prime[j]],1,0);

					while(!(red[i]%prime[j]))

						red[i]/=prime[j];

				}

			}

			now+=1;

		}

		int ans=dinic(0,m+n+1);

		printf("%d\n",ans);

	}

}

巴特西

P2065 [TJOI2011]卡片

真·会了网络流，忘了匈牙利

最新文章

热门文章