题解 P5045 【[SCOI2003]蜘蛛难题】

shentao1 · 2019-05-29 20:48:03 · 题解

坑爹题目，毁我青春

首先有想法就是从起点往后按照出水管依次满足，但多个水域需要合起来求下一个最低出水口，所以并不是很好维护

所以最好按照时间模拟

先求出当前状态下的最低水平面，

然后看这些最低的面能不能通过出水口到达新的水坑，把这些水坑加入当前状态

然后再求一次当前状态下的最低水平面

然后再把他们依次灌1

直到蜘蛛所在的上一块被灌，输出上次的答案

然后就需要根据题目坑爹的描述特判：

1、第一个水坑的坑底的蜘蛛0秒被灌

2、正好在坑顶的蜘蛛会被灌

然后就做完啦

last but not least，代码闪亮登场：

//码风丑，不喜勿喷
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namesbace std;
int n,i,m,v[30],v2[30],x,y,yy,ans,minn,zd,sx[30],j,top,last;
bool vis[30];
struct la
{
    int x,y,yy;
}g[30];
vector<int>vv;
int tu[105],lt[30][205],sta[30];
bool cmp(la a,la b)
{
    return a.x<b.x;
}
void dfs(int o)
{
if(vis[lt[o][g[o].y+g[o].yy]]==0)
{
    vis[lt[o][g[o].y+g[o].yy]]=1;
    vv.push_back(lt[o][g[o].y+g[o].yy]);
    dfs(lt[o][g[o].y+g[o].yy]);     
}
} 
int main()
{vis[0]=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
   {
    scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].yy);   
   }
   scanf("%d",&m);
   for(i=1;i<=n;i++)tu[g[i].x]=i;
//   memset(v,0x7f,sizeof(v));
   for(i=1;i<=m;i++)
   {
    scanf("%d%d%d",&x,&y,&yy);
lt[tu[x-1]][y]=tu[x+yy];
lt[tu[x+yy]][y]=tu[x-1];   
   }
   minn=999999;
   scanf("%d%d",&zd,&yy);
   if(zd==1&&yy==g[1].y+g[1].yy)
   {
    printf("0");
    return 0;
   }
   vv.push_back(1);
   vis[1]=1;
   while(1)
   {
    //求出目前水位最低的
    int maxx=-1;
    top=0;
       for(i=0;i<vv.size();i++) 
        {   if(maxx==g[vv[i]].y+g[vv[i]].yy)
            {
                sta[++top]=vv[i];               
            }           
            if(g[vv[i]].y+g[vv[i]].yy>maxx)
            {
                top=0;
                maxx=g[vv[i]].y+g[vv[i]].yy;
                sta[++top]=vv[i];
            }
        }
   //如果加进去最终会流到哪 
for(i=1;i<=top;i++)
{
    dfs(sta[i]);
}
   //再求一遍当前最小 
   top=0;
           for(i=0;i<vv.size();i++) 
        {   if(maxx==g[vv[i]].y+g[vv[i]].yy)
            {
                sta[++top]=vv[i];               
            }           
            if(g[vv[i]].y+g[vv[i]].yy>maxx)
            {
                top=0;
                maxx=g[vv[i]].y+g[vv[i]].yy;
                sta[++top]=vv[i];
            }
        }
   //果断加水
   for(i=1;i<=top;i++)
   {
    if(sta[i]==zd&&g[sta[i]].y+g[sta[i]].yy==yy)
    {
    printf("%d",ans);
       return 0;        
    }
   }
       for(i=1;i<=top;i++)
       {
    g[sta[i]].yy--;
    ans++;
    if(g[sta[i]].yy<0) 
    {
    printf("-1");
    return 0;       
    }   
       }    
    //检验答案
       if(g[zd].y+g[zd].yy+1==yy)
       {
        printf("%d",last);
       return 0;
       }    
       last=ans;
   }
}