将每个数拆点,互相连边,然后满足条件的数对之间互相连边,跑最大费用流,答案是流量和费用分别除以2。

一定要i->j、j->i都连上,否则可能会出现一个数在一边被选择了,在另一边的另一个匹配中又被选择的情况。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 2002
#define MAXM 500001
#define INF 2147483647
int S,T,n,A,B;
int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Array
bool inq[MAXN];
int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;
queue<int>q;
void Init_MCMF(){memset(first,-1,sizeof(first));en=0;S=0;T=(B<<1|1);}
void AddEdge(const int &U,const int &V,const int &W,const int &C)
{u[en]=U; v[en]=V; cap[en]=W; cost[en]=C; next[en]=first[U]; first[U]=en++;
u[en]=V; v[en]=U; cost[en]=-C; next[en]=first[V]; first[V]=en++;}
bool Spfa(int &Flow,int &Cost)
{
memset(d,0x7f,sizeof(d));
memset(inq,0,sizeof(inq));
d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);
while(!q.empty())
{
int U=q.front(); q.pop(); inq[U]=0;
for(int i=first[U];i!=-1;i=next[i])
if(cap[i] && d[v[i]]>d[U]+cost[i])
{
d[v[i]]=d[U]+cost[i];
p[v[i]]=i;
a[v[i]]=min(a[U],cap[i]);
if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}
}
}
if(d[T]>2100000000) return 0;
Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;
while(U!=S)
{
cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];
U=u[p[U]];
}
return 1;
}
int Mincost()
{
int Flow=0,Cost=0;
while(Spfa(Flow,Cost));
printf("%d %d\n",Flow>>1,(-Cost)>>1);
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int sqr(const int &x){return x*x;}
bool check(const int &a,const int &b)
{
int t=a*a-b*b;
if(sqr((int)sqrt(t))!=t) return 0;
if(gcd(b,(int)sqrt(t))==1) return 1;
return 0;
}
int main()
{
scanf("%d%d",&A,&B); Init_MCMF();
for(int i=A;i<=B;++i)
for(int j=A;j<i;++j)
if(check(i,j))
{
AddEdge(i,j+B,1,-i-j);
AddEdge(j,i+B,1,-i-j);
}
for(int i=A;i<=B;++i)
{
AddEdge(S,i,1,0);
AddEdge(i+B,T,1,0);
}
Mincost();
return 0;
}

  

最新文章

  1. javascript export excel
  2. dedecms /include/helpers/archive.helper.php SQL Injection Vul
  3. 从网页(WEB)登录SAP
  4. C# Socket编程(3)编码和解码
  5. java基础之 反射
  6. MySQL数据库系统概述
  7. 把一个窗体嵌入到WinForm中进行显示,以CMD窗口为例
  8. IAR Build from the command line 环境变量设置
  9. 【高级JSE技术】线程池
  10. 一次性关闭所有的Activity
  11. BSTR、char*和CString转换
  12. 分享一个PHP文件上传类
  13. 【cocos 2d-x】VS2012+win7+cocos2d-x3.0beta2开发环境配置
  14. 转:&lt;mvc:annotation-driven/&gt;的注解意义
  15. RNN回归
  16. word插入公式不自动斜体的解决办法
  17. 用HttpClient和用HttpURLConnection做爬虫发现爬取的代码少了的问题
  18. 潭州课堂25班:Ph201805201 python 模块 datetime,logging 第七课 (课堂笔记)
  19. genieacs Installation on Ubuntu14.04
  20. 华为交换机VRRP配置实例收集(转)

热门文章

  1. 1040: [ZJOI2008]骑士~基环外向树dp
  2. URAL - 1486 Equal Squares 二维哈希+二分
  3. POJ 3179 Corral the Cows
  4. flume高级组件及各种报错
  5. swift中_的用法,忽略默认参数名。
  6. 在Unity(C#)下实现Lazy Theta*寻路
  7. Kali Linux中前十名的Wifi攻击工具
  8. Linux 开机自动挂载windows分区
  9. cdp协议通信并发编程基础之进程
  10. 关于hrtimer_forward小段代码的分析【转】