#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define M 10000
#define inf 2139062143
using namespace std;
int cnt=,n,m,T,d[M],q[*M],f[M],head[M],next[*M],u[*M],v[*M],w[*M],fro[*M],fr[M];
int ans,sum;
void jia1(int a1,int a2,int a3,int a4)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
fro[cnt]=a1;
u[cnt]=a2;
v[cnt]=a3;
w[cnt]=a4;
}
void jia(int a1,int a2,int a3,int a4)
{
jia1(a1,a2,a3,a4);
jia1(a2,a1,,-a4);
return;
}
bool spfa()
{
memset(d,,sizeof(int)*(T+));
d[]=;
f[]=;
q[]=;
int h=,t=;
for(;h<t;)
{
h++;
int p=q[h];
f[p]=;
for(int i=head[p];i;i=next[i])
if(v[i]&&d[u[i]]>d[p]+w[i])
{
d[u[i]]=d[p]+w[i];
fr[u[i]]=i;
if(!f[u[i]])
{
f[u[i]]=;
t++;
q[t]=u[i];
}
}
}
if(d[T]!=inf)
return ;
return ;
}
void mcf()
{
int mx=inf;
for(int i=fr[T];i;i=fr[fro[i]])
mx=min(mx,v[i]);
for(int i=fr[T];i;i=fr[fro[i]])
{
v[i]-=mx;
v[i^]+=mx;
ans+=mx*w[i];
}
sum+=mx;
return;
}
int gcd(int a1,int a2)
{
int a3=a1%a2;
for(;a3;)
{
a1=a2;
a2=a3;
a3=a1%a2;
}
return a2;
}
int main()
{
scanf("%d%d",&n,&m);
T=;
for(int i=n;i<=m;i++)
{
jia(,i,,);
jia(i+,T,,);
}
for(int i=n;i<=m;i++)
for(int j=n;j<i;j++)
{
double a1=sqrt(i*i-j*j);
int a2=floor(a1);
if(a2==a1&&gcd(a2,j)==)
{
jia(i,j+,,-i-j);
jia(j,i+,,-i-j);
}
}
for(;spfa();)
mcf();
printf("%d %d\n",sum/,-ans/);
return ;
}
网络流如果满足条件,x向y‘连费用为z的边,y向x’连费用为z的边,最后除2便是答案。
bzoj 2661: [BeiJing wc2012]连连看的更多相关文章
-
BZOJ 2661: [BeiJing wc2012]连连看 费用流
2661: [BeiJing wc2012]连连看 Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规则是,给出一个闭 ...
-
2661: [BeiJing wc2012]连连看
Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规则是,给出一个闭区间[a,b]中的全部整数,如果其中某两个数x,y( ...
-
BZOJ2661: [BeiJing wc2012]连连看
2661: [BeiJing wc2012]连连看 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 483 Solved: 200[Submit][S ...
-
[BZOJ2661][BeiJing wc2012]连连看 费用流
2661: [BeiJing wc2012]连连看 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1349 Solved: 577[Submit][ ...
-
BZOJ_2661_[BeiJing wc2012]连连看_费用流
BZOJ_2661_[BeiJing wc2012]连连看_费用流 Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规 ...
-
【BZOJ2661】[BeiJing wc2012]连连看 最大费用流
[BZOJ2661][BeiJing wc2012]连连看 Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规则是,给 ...
-
BZOJ 2662: [BeiJing wc2012]冻结(最短路)
这道题和 BZOJ 2763飞行路线 几乎一模一样..然后飞行路线我是1A,这道题WA了4次,我开始怀疑我的智商了.. ---------------------------------------- ...
-
bzoj 2659: [Beijing wc2012]算不出的算式
2659: [Beijing wc2012]算不出的算式 Time Limit: 3 Sec Memory Limit: 128 MB Description 算不出的算式背景:曾经有一个老掉牙的游 ...
-
Bzoj 2662: [BeiJing wc2012]冻结 dijkstra,堆,分层图,最短路
2662: [BeiJing wc2012]冻结 Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 647 Solved: 348[Submit][Sta ...
随机推荐
-
Java Servlet+Objective-c图上传 步骤详细
一. Servlet 1.创建图片保存的路径 在项目的WebContent下创建一个上传图片的专属文件夹. 这个文件夹创建后,我们保存的图片就在该文件夹的真实路径下,但是在项目中是无法看到上传的图片的 ...
-
iOS 设置状态栏的背景颜色
设置状态栏的背景颜色 - (void)setStatusBarBackgroundColor:(UIColor *)color { UIView *statusBar = [[[UIApplicati ...
-
Win10安装程序出现error code 2502 2503
在Win10中,在安装msi安装包的时候常常会出现代码为2502.2503的错误.其实这种错误是由于安装权限不足造成的,可以这种msi的安装包不像其他exe的安装程序,在安装包上点击"右键& ...
-
常用SQL代码段
代码使用时须测试. --聚合函数 use pubs go select avg(distinct price) --算平均数 from titles where type='business' go ...
-
HTML空格符号 nbsp; ensp; emsp; 介绍以及实现中文对齐的方法
一:不同空格符合的区别 半角的不断行的空白格(推荐使用) 半角的空格 全角的空格 详细的含义: :这是我们使用最多的空格,也就是按下space键产生的空格.在HTML中,如果你用空格 ...
-
react-router简介
Web应用中的路由的作用和原理:保证视图和URL的同步,可以把视图看成资源的一种表现.当用户在页面中进行操作时,应用会在若干个交互状态中切换,比如用户会单击浏览器的前进.后退按钮进行切换等.路由系统的 ...
-
基于数组的循环队列(C++模板实现)
循环队列使用数组实现的话,简单.方便.之前实现的队列,当尾端索引到达队列最后的时候,无论前面是否还有空间,都不能再添加数据了.循环队列使得队列的存储单元可以循环利用,它需要一个额外的存储单元来判断队列 ...
-
Java基础其他
1. 二进制 进制就是进位制,常见的有二进制.十进制.十六进制等 在进制中,可用符号的数量称为基数,基数为n就称为n进制,逢n进一位: 二进制:0 1 十进制:0 1 2 3 4 5 6 7 8 9 ...
-
VIM 键盘符号
:h key-notation //查询键盘符号说明<>> 等于shift + > % 是跳到对应的括号 x 是删除当前字符,即右括号 '' 是跳回左括号 x 删除左括号
-
WebGoat 8安装、配置、使用教程(CentOS)
一.说明 1.1 背景说明 之前只用过dvwa,听说WebGoat也是类似的平台后,想装来试试有没有什么异同. 看了下载文件,和网上官方的.非官方的安装教程,感觉很多都对不上: 最后发现WebGoat ...