这俩是一个题。

拿「千钧一发」说吧,你会发现显然如果对于一个i,如果a_i是偶数的话,他一定满足条件2,反过来如果a_i是奇数的话,他一定满足条件1,很好证明,就不说了。

然后你会发现这样一件事情:二分图

我们考虑补集转化,求最少的必须不选的b_i们,这大概……就是一个最小割。

最小割。怎么建图?源点汇点分别连所有奇数/偶数,边权b_i,然后奇偶之间互相连边,边权\rm{INF}

为什么是\rm{INF}?

因为……呃……表示这条边一定不会被割掉,那我们假设他连接了u \; , \; v两个结点,你需要挑一个,把他和源点或者汇点的边割掉。也就意味着最小割增加了b_u或者b_v的权,也就是不选其中一个。

然后这样就形成了超级复杂的关系网络然后就瞎跑Dinic就可以过了

注意!邻接表要开很大,而且两个题范围不一样!

(但是奇怪的是范围较大的\rm{Number}却跑得快

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;

struct ed { int capx,pre,to; }edge[2500010]={0};
int nodenum=0,at=1,pointer[2010]={0},fx,tx,cx,ss,tt;

int nodev[2010]={0},seq[2010]={0},n;
int codex[2010]={0};

queue<int> que;
int level[2010]={0},cache1; bool vis[2010]={0};
ll ans=0,ansb=0;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}
inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	edge[at].capx=cx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline ll gcd(ll a,ll b)
{
	if (!b) return a;
	return gcd(b,a%b);
}
inline bool check(ll a,ll b)
{
	ll t=sqrt(a*a+b*b);
	if (t*t==a*a+b*b) return true;
	return false;
}

inline bool BFS()
{
	memset(vis,0,sizeof(vis)); memset(level,0,sizeof(level));
	level[ss]=1; vis[ss]=true; que.push(ss);
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		for (int prex=pointer[cache1];prex;prex=edge[prex].pre)
		{
			if (!vis[edge[prex].to] && edge[prex].capx)
			{
				level[edge[prex].to]=level[cache1]+1;
				vis[edge[prex].to]=true; que.push(edge[prex].to);
			}
		}
	}
	return vis[tt];
}
inline int DFS(int nownode,int minf)
{
	if ((!minf) || nownode==tt) return minf;
	int sumf=0,needf=0;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
	{
		if (level[edge[prex].to]==level[nownode]+1)
		{
			if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))
			{
				sumf+=needf; minf-=needf;
				edge[prex].capx-=needf; edge[prex^1].capx+=needf;
				if (!minf) break;
			}
		}
	}
	return sumf;
}

inline void init1()
{
	fx=ss;
	for (int i=1;i<=n;i++) if (!(seq[i]%2))
	{
		nodenum++; codex[i]=nodenum;
		tx=nodenum; cx=nodev[i]; Insert();
	}
	tx=tt;
	for (int i=1;i<=n;i++) if (seq[i]%2)
	{
		nodenum++; codex[i]=nodenum;
		fx=nodenum; cx=nodev[i]; Insert();
	}
}

int main()
{
	readx(n); ss=n+1; tt=n+2;
	for (int i=1;i<=n;i++) readx(seq[i]);
	for (int i=1;i<=n;i++) { readx(nodev[i]); ansb+=nodev[i]; }
	
	init1();
	
	cx=2*1e9;
	for (int i=1;i<=n;i++) if (!(seq[i]%2))
	{
		fx=codex[i];
		for (int j=1;j<=n;j++) if (seq[j]%2)
			if (check(seq[i],seq[j]) && gcd(seq[i],seq[j])==1) { tx=codex[j]; Insert(); }
	}
	
	while (BFS()) ans+=DFS(ss,2*1e9);
	printf("%lld\n",ansb-ans);
	return 0;
}
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;

struct ed { int capx,pre,to; }edge[4300010]={0};
int nodenum=0,at=1,pointer[6010]={0},fx,tx,cx,ss,tt;

int nodev[6010]={0},n;
int codex[6010]={0};

queue<int> que;
int level[6010]={0},cache1; bool vis[6010]={0};
ll ans=0,ansb=0;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}
inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	edge[at].capx=cx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline ll gcd(ll a,ll b)
{
	if (!b) return a;
	return gcd(b,a%b);
}
inline bool check(ll a,ll b)
{
	ll t=sqrt(a*a+b*b);
	if (t*t==a*a+b*b) return true;
	return false;
}

inline bool BFS()
{
	memset(vis,0,sizeof(vis)); memset(level,0,sizeof(level));
	level[ss]=1; vis[ss]=true; que.push(ss);
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		for (int prex=pointer[cache1];prex;prex=edge[prex].pre)
		{
			if (!vis[edge[prex].to] && edge[prex].capx)
			{
				level[edge[prex].to]=level[cache1]+1;
				vis[edge[prex].to]=true; que.push(edge[prex].to);
			}
		}
	}
	return vis[tt];
}
inline int DFS(int nownode,int minf)
{
	if ((!minf) || nownode==tt) return minf;
	int sumf=0,needf=0;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
	{
		if (level[edge[prex].to]==level[nownode]+1)
		{
			if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))
			{
				sumf+=needf; minf-=needf;
				edge[prex].capx-=needf; edge[prex^1].capx+=needf;
				if (!minf) break;
			}
		}
	}
	return sumf;
}

inline void init1()
{
	fx=ss;
	for (int i=1;i<=n;i++) if (!(nodev[i]%2))
	{
		nodenum++; codex[i]=nodenum;
		tx=nodenum; cx=nodev[i]; Insert();
	}
	tx=tt;
	for (int i=1;i<=n;i++) if (nodev[i]%2)
	{
		nodenum++; codex[i]=nodenum;
		fx=nodenum; cx=nodev[i]; Insert();
	}
}

int main()
{
	readx(n); ss=n+1; tt=n+2;
	for (int i=1;i<=n;i++) { readx(nodev[i]); ansb+=nodev[i]; }
	
	init1();
	
	cx=2*1e9;
	for (int i=1;i<=n;i++) if (!(nodev[i]%2))
	{
		fx=codex[i];
		for (int j=1;j<=n;j++) if (nodev[j]%2)
			if (check(nodev[i],nodev[j]) && gcd(nodev[i],nodev[j])==1) { tx=codex[j]; Insert(); }
	}
	
	while (BFS()) ans+=DFS(ss,2*1e9);
	printf("%lld\n",ansb-ans);
	return 0;
}

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.