[文章目录]
Description
凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。1<=a,b<=1000
黑白染色，将合法的x,y连边，发现是二分图，直接最大费用最大流即可。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1100
bool vis[1001000],flag=true;
int s,t,a,b,head[N],to[N*N],nxt[N*N],f[N*N],w[N*N],cnt,col[N];
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
inline void add(int x,int y,int ff,int ww)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=ff; w[cnt]=ww;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0; w[cnt]=-ww;
}
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
void dfs(int x)
{
for(int i=head[x];i;i=nxt[i])
{
if(col[to[i]]==-1) col[to[i]]=col[x]^1,dfs(to[i]);
else if(col[to[i]]==col[x]) flag=false;
}
}
int dis[N],path[N];
bool iq[N];
queue<int>q;
bool spfa()
{
memset(dis,0xef,sizeof dis);
memset(iq,0,sizeof iq);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; iq[s]=1; int i,x;
while(!q.empty())
{
x=q.front(); q.pop(); iq[x]=0;
for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]<dis[x]+w[i])
{
dis[to[i]]=dis[x]+w[i];
path[to[i]]=i^1;
if(!iq[to[i]]) iq[to[i]]=1,q.push(to[i]);
}
}
return dis[t]!=0xefefefef;
}
int main()
{
int i,j;
for(i=1;i<=1000;++i) vis[i*i]=1;
for(i=1;i<=1000;++i)
for(j=i+1;j<=1000;++j)
if(gcd(i,j)==1&&vis[j*j-i*i])
add(i,j),add(j,i);
memset(col,-1,sizeof(col));
for(i=1;i<=1000;++i) if(col[i]==-1) col[i]=0,dfs(i);
//if(!flag) puts("WAAAAAAAA!");
memset(head,0,sizeof head); cnt=1;
scanf("%d%d",&a,&b); s=b+1; t=s+1;
for(i=a;i<=b;++i)
{
if(col[i]) add(i,t,1,0);
else add(s,i,1,0);
for(j=i+1;j<=b;++j)
if(gcd(i,j)==1&&vis[j*j-i*i])
{
if(col[i]) add(j,i,1,i+j);
else add(i,j,1,i+j);
}
}
int ans1=0,ans2=0;
while(spfa())
{
int flow=0x3f3f3f3f;
for(i=t;i!=s;i=to[path[i]]) flow=min(flow,f[path[i]^1]);
ans1+=flow;
for(i=t;i!=s;i=to[path[i]])
{
f[path[i]]+=flow;
f[path[i]^1]-=flow;
ans2+=flow*w[path[i]^1];
}
}
printf("%d %d\n",ans1,ans2);
return 0;
}