bzoj 2661: [BeiJing wc2012]连连看

时间:2022-10-02 20:43:06
 #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]连连看的更多相关文章

  1. BZOJ 2661&colon; &lbrack;BeiJing wc2012&rsqb;连连看 费用流

    2661: [BeiJing wc2012]连连看 Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规则是,给出一个闭 ...

  2. 2661&colon; &lbrack;BeiJing wc2012&rsqb;连连看

    Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规则是,给出一个闭区间[a,b]中的全部整数,如果其中某两个数x,y( ...

  3. BZOJ2661&colon; &lbrack;BeiJing wc2012&rsqb;连连看

    2661: [BeiJing wc2012]连连看 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 483  Solved: 200[Submit][S ...

  4. &lbrack;BZOJ2661&rsqb;&lbrack;BeiJing wc2012&rsqb;连连看 费用流

    2661: [BeiJing wc2012]连连看 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1349  Solved: 577[Submit][ ...

  5. BZOJ&lowbar;2661&lowbar;&lbrack;BeiJing wc2012&rsqb;连连看&lowbar;费用流

    BZOJ_2661_[BeiJing wc2012]连连看_费用流 Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规 ...

  6. 【BZOJ2661】&lbrack;BeiJing wc2012&rsqb;连连看 最大费用流

    [BZOJ2661][BeiJing wc2012]连连看 Description 凡是考智商的题里面总会有这么一种消除游戏.不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏.我们的规则是,给 ...

  7. BZOJ 2662&colon; &lbrack;BeiJing wc2012&rsqb;冻结&lpar;最短路&rpar;

    这道题和 BZOJ 2763飞行路线 几乎一模一样..然后飞行路线我是1A,这道题WA了4次,我开始怀疑我的智商了.. ---------------------------------------- ...

  8. bzoj 2659&colon; &lbrack;Beijing wc2012&rsqb;算不出的算式

    2659: [Beijing wc2012]算不出的算式 Time Limit: 3 Sec  Memory Limit: 128 MB Description 算不出的算式背景:曾经有一个老掉牙的游 ...

  9. Bzoj 2662&colon; &lbrack;BeiJing wc2012&rsqb;冻结 dijkstra&comma;堆&comma;分层图&comma;最短路

    2662: [BeiJing wc2012]冻结 Time Limit: 3 Sec  Memory Limit: 128 MBSubmit: 647  Solved: 348[Submit][Sta ...

随机推荐

  1. Java Servlet&plus;Objective-c图上传 步骤详细

    一. Servlet 1.创建图片保存的路径 在项目的WebContent下创建一个上传图片的专属文件夹. 这个文件夹创建后,我们保存的图片就在该文件夹的真实路径下,但是在项目中是无法看到上传的图片的 ...

  2. iOS 设置状态栏的背景颜色

    设置状态栏的背景颜色 - (void)setStatusBarBackgroundColor:(UIColor *)color { UIView *statusBar = [[[UIApplicati ...

  3. Win10安装程序出现error code 2502 2503

    在Win10中,在安装msi安装包的时候常常会出现代码为2502.2503的错误.其实这种错误是由于安装权限不足造成的,可以这种msi的安装包不像其他exe的安装程序,在安装包上点击"右键& ...

  4. 常用SQL代码段

    代码使用时须测试. --聚合函数 use pubs go select avg(distinct price) --算平均数 from titles where type='business' go ...

  5. HTML空格符号 nbsp&semi; ensp&semi; emsp&semi; 介绍以及实现中文对齐的方法

    一:不同空格符合的区别   半角的不断行的空白格(推荐使用)    半角的空格    全角的空格 详细的含义:  :这是我们使用最多的空格,也就是按下space键产生的空格.在HTML中,如果你用空格 ...

  6. react-router简介

    Web应用中的路由的作用和原理:保证视图和URL的同步,可以把视图看成资源的一种表现.当用户在页面中进行操作时,应用会在若干个交互状态中切换,比如用户会单击浏览器的前进.后退按钮进行切换等.路由系统的 ...

  7. 基于数组的循环队列(C&plus;&plus;模板实现)

    循环队列使用数组实现的话,简单.方便.之前实现的队列,当尾端索引到达队列最后的时候,无论前面是否还有空间,都不能再添加数据了.循环队列使得队列的存储单元可以循环利用,它需要一个额外的存储单元来判断队列 ...

  8. Java基础其他

    1. 二进制 进制就是进位制,常见的有二进制.十进制.十六进制等 在进制中,可用符号的数量称为基数,基数为n就称为n进制,逢n进一位: 二进制:0 1 十进制:0 1 2 3 4 5 6 7 8 9 ...

  9. VIM 键盘符号

    :h key-notation //查询键盘符号说明<>> 等于shift + > % 是跳到对应的括号 x 是删除当前字符,即右括号 '' 是跳回左括号 x 删除左括号

  10. WebGoat 8安装、配置、使用教程(CentOS)

    一.说明 1.1 背景说明 之前只用过dvwa,听说WebGoat也是类似的平台后,想装来试试有没有什么异同. 看了下载文件,和网上官方的.非官方的安装教程,感觉很多都对不上: 最后发现WebGoat ...