【BZOJ1077】天平(差分约束)
2024-08-30 16:04:21
【BZOJ1077】天平(差分约束)
题面
题解
利用矩阵可以很容易得到两个点之间的最大差和最小差,再利用这个信息判断即可。差分约束用\(Floyd\)计算。时间复杂度\(O(n^3)\)。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 55
int dmn[MAX][MAX],dmx[MAX][MAX];
int n,A,B,c1,c2,c3;
char ch[MAX];
int main()
{
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i<=n;++i)
{
scanf("%s",ch+1);
for(int j=1;j<=n;++j)
{
if(ch[j]=='='||i==j)dmn[i][j]=dmx[i][j]=0;
else if(ch[j]=='+')dmn[i][j]=1,dmx[i][j]=2;
else if(ch[j]=='-')dmn[i][j]=-2,dmx[i][j]=-1;
else dmn[i][j]=-2,dmx[i][j]=2;
}
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(i==j||j==k||k==i)continue;
dmn[i][j]=max(dmn[i][j],dmn[i][k]+dmn[k][j]);
dmx[i][j]=min(dmx[i][j],dmx[i][k]+dmx[k][j]);
}
for(int i=1;i<=n;++i)
if(i!=A&&i!=B)
for(int j=1;j<i;++j)
{
if(j==A||j==B)continue;
if(dmn[A][i]>dmx[j][B]||dmn[B][i]>dmx[j][A])++c1;
if(dmn[i][A]>dmx[B][j]||dmn[i][B]>dmx[A][j])++c3;
if(dmn[A][i]==dmx[A][i]&&dmn[j][B]==dmx[j][B]&&dmn[A][i]==dmn[j][B])++c2;
else if(dmn[B][i]==dmx[B][i]&&dmn[j][A]==dmx[j][A]&&dmn[B][i]==dmn[j][A])++c2;
}
printf("%d %d %d\n",c1,c2,c3);
return 0;
}
最新文章
- git push不用重复输入用户名和密码(解决方案)
- JavaScript类型判断instanceof与typeof对比
- Visor 隐藏应用之一 CSS3 生成器
- BlocksKit初见:一个支持将delegate转换成block的Cocoa库
- [ASP.NET MVC] 使用Bootstrap套件
- ios学习笔记之block在ios开发中的应用
- JS设计模式——5.单体模式
- mybatis缓存清除方法
- BDD
- Windows下MySQL分步安装图解及问题总结
- 在Unix系统中,主存索引节点和辅存索引节点从内容上比较有什么不同,为什么要设置主存索引节点?
- C#之Redis所欲为
- C/C++ 数据结构之算法
- 小程序使用阿里巴巴TTF字体文件以及图标
- MySQL中间件之ProxySQL(4):多层配置系统
- 观察者模式与.NET的delegate、event机制
- 4-cookie 简介
- 11-20 bom 浏览器对象模型
- MySQL删除命令_DELETE
- JVMj机制
热门文章
- Docker一键部署Hadoop心得(一)
- [NOI2003]Editor &; [AHOI2006]文本编辑器editor BZOJ1507&;BZOJ1269
- struts2_文件上传的功能
- 20155223 Exp2 后门原理与实践
- 奔跑吧Linux
- 汇编 inc 和 dec 指令
- SQL Server 全文搜索
- 小白之selenium+python关于cookies绕开登录2
- 《Macro-Micro Adversarial Network for Human Parsing》论文阅读笔记
- linux一切皆文件之tty字符设备(深入理解sshd创建pty的过程) (五)