博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ1092 : [SCOI2003]蜘蛛难题
阅读量:5891 次
发布时间:2019-06-19

本文共 1036 字,大约阅读时间需要 3 分钟。

按时间一步一步模拟。

每一次,首先将所有没有水但是可以被灌到水的管子标记为有水,然后求出有水的管子里水面高度的最小值。

如果$a$号管有水且最小值为$b$,那么说明此时蜘蛛碰到了水。

如果有管子溢出且最小值就是它,那么说明此时无论如何水面都不会再上涨,即无解。

然后往所有高度等于最小值的管子里灌上一高度的水即可。

 

#include
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++; }}

  

转载地址:http://qmysx.baihongyu.com/

你可能感兴趣的文章
SILK 的 Tilt的意思
查看>>
IPC通信:Posix共享内存2
查看>>
GB2312转成UTF-8
查看>>
C#打开chm定位到特定页面
查看>>
[CareerCup][Google Interview] 寻找动态的中位数
查看>>
javascript操作iframe的那些事
查看>>
servlet相关 jar包位置 BAE上部署web应用
查看>>
路徑 z
查看>>
cpu分析简介
查看>>
1.备忘录模式
查看>>
Html学习笔记3
查看>>
杭州见闻
查看>>
What is Xeround?
查看>>
[转载]jQuery上传插件Uploadify使用详解
查看>>
算法学习的轨迹(转)
查看>>
asmx-web-service-basic-authentication
查看>>
Excel转换成图片的操作方法
查看>>
MFC中读取和设置文件状态
查看>>
分页显示
查看>>
iOS中安全结束 子线程 的方法
查看>>