BZOJ1092 : [SCOI2003]蜘蛛难题
难题 蜘蛛
2023-09-11 14:15:04 时间
按时间一步一步模拟。
每一次,首先将所有没有水但是可以被灌到水的管子标记为有水,然后求出有水的管子里水面高度的最小值。
如果$a$号管有水且最小值为$b$,那么说明此时蜘蛛碰到了水。
如果有管子溢出且最小值就是它,那么说明此时无论如何水面都不会再上涨,即无解。
然后往所有高度等于最小值的管子里灌上一高度的水即可。
#include<cstdio> const int N=25,M=110; int n,m,i,j,x,y,z,A,B,T,g[N],v[M],w[M],nxt[M],ed; struct P{int x,y,h,v;}a[N]; int getid(int x){for(int i=1;i<=n;i++)if(a[i].x==x)return i;} void add(int x,int y,int z){ v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed; v[++ed]=x;w[ed]=z;nxt[ed]=g[y];g[y]=ed; } int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].h),a[i].h+=a[i].y,a[i].v=i==1; scanf("%d",&m); while(m--)scanf("%d%d%d",&x,&y,&z),add(getid(x-1),getid(x+z),y); scanf("%d%d",&A,&B); while(1){ for(x=1;x;)for(x=0,i=1;i<=n;i++)if(a[i].v) for(j=g[i];j;j=nxt[j])if(a[i].h<=w[j]&&!a[v[j]].v)a[v[j]].v=x=1; for(m=0,i=1;i<=n;i++)if(a[i].v&&a[i].h>m)m=a[i].h; if(a[A].v&&m==B)return printf("%d",T),0; for(i=1;i<=n;i++)if(a[i].v&&a[i].y==a[i].h&&a[i].y==m)return puts("-1"),0; for(i=1;i<=n;i++)if(a[i].v&&a[i].h==m)a[i].h--,T++; } }
相关文章
- Windows Phone 8 面临吸引开发者难题
- hdu 1251 统计难题 前缀出现次数
- 44 道 JavaScript 难题
- Java实现桐桐的数学难题
- 如何用一个插件解决 Serverless 灰度发布难题?
- KubeMeet 直播 | 现场直击大规模集群、混合环境下的云原生应用交付难题
- 如何面对传统媒体运用大数据时遇到的三大难题
- 大数据征信六大难题待解
- 如何面对传统媒体运用大数据时遇到的三大难题
- 数仓、湖仓、数据中台都没解决的企业数字化难题,却被它解决了
- 有了这个告警系统,DBA提前预警不是难题
- 生活中的这些难题,数据库开发者可为你解决!
- 遇到联邦计算数据碰撞难题怎么办?不妨试一试PSI
- 业界难题-“跨库分页”的四种方案
- 二分查找 难题汇总 模板验证 二分答案 本质上是答案在一段range里,然后根据该range去二分搜索!
- 【多线程】Java并行流一次解决多线程编程难题
- 数仓、湖仓、数据中台都没解决的企业数字化难题,却被它解决了
- 解决高基数难题,云原生时序数据库 TDengine 3.0 荣获 IT168 2022 年度技术卓越奖
- 解决异构系统集成难题,富融银行这样做