[ZOJ1021 The Willy Memorial Program]【狗狗40题】【特别特别坑爹】

规模十分之小，但是特别特别坑T_T

一定要看清楚这一段话：

As an example, if we set the target point to level 4 in the left pipe in the figure above, the elapsed time for water to reach that target is assumed to be 5 (not 2), Also note that if the water reaches to the top of a pipe (say in level x), it won’t pour out outside the pipe until empty spaces in connected pipes below level x are filled (if can be filled, i.e. the level of water reaches the connecting links). (Note that there may be some links at level x, to which water is entered). After all such spaces are filled; the water level would not go up further.

然后别的怎么暴力都0MS……

搜狗V5啊，在学校上不了ZOJ，用了搜狗的全网加速就上得了啦……其实就是个代理T_T

const int N=55;
const int INF=0x7FFFFFFF;
int n,m,Target_i,Target_level;
struct Pipe{int x,y,h;}P[N];
struct Link{int p1,p2,y;}L[N];
int level[N];

void gao(){
    int i,j,k,ans=0;
    fill(level,level+n+1,INF);
    level[1]=P[1].y+P[1].h;
    while (1){ //退出条件：1、满了 2、达到target
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
            for (k=1;k<=m;k++)if (L[k].p1==j || L[k].p2==j){
              int x,y;
              if (L[k].p1==j) { x=L[k].p2; y=j; }
                         else { x=L[k].p1; y=j; }
              if (level[x]==INF && level[y]==L[k].y) level[x]=P[x].y+P[x].h;
            }
        int cnt=0,Max=-INF;
        bool check=true;
        for (i=1;i<=n;i++)
          if (level[i]!=INF && level[i]>Max)
              Max=level[i];
        for (i=1;i<=n;i++)
          if (level[i]!=INF && level[i]==Max)
            if (level[i]>P[i].y){
              cnt++;
              level[i]–;
            }
            elseif (level[i]==P[i].y)
              check=false;
        if (!check) cnt=0;
        if (cnt==0){
            puts("No Solution");
            return;
        }
        if (level[Target_i]            cout << ans << endl;
            return;
        }
        ans+=cnt;
    }
}

void add(int k,int x,int y,int l){
    int p1=0,p2=0;
    for (int i=1;i<=n;i++){
      if (y>=P[i].y && y<=P[i].y+P[i].h && P[i].x+1==x) p1=i;
      if (y>=P[i].y && y<=P[i].y+P[i].h && P[i].x==x+l) p2=i;
    }
    L[k].p1=p1;
    L[k].p2=p2;
    L[k].y=y;
}

int main(){
    int Tc,x,y,l;
    cin >> Tc;
    while (Tc–){
        cin >> n;
        for (int i=1;i<=n;i++) cin >> P[i].x >> P[i].y >> P[i].h;
        cin >> m;
        for (int i=1;i<=m;i++){
            cin >> x >> y >> l;
            add(i,x,y,l);
        }
        cin >> Target_i >> Target_level;
        if (Target_level<=P[Target_i].y || Target_level>P[Target_i].y+P[Target_i].h)
            puts("No Solution");
        else
            gao();
    }
}

一些数据：

3

7
10 4 6
7 0 13
12 0 13
3 2 8
0 7 6
1 0 6
5 5 7
13
2 1 5
2 3 1
1 9 2
1 12 4
4 8 1
11 10 1
8 13 4
8 2 4
4 4 3
8 5 2
4 6 1
6 7 1
6 11 1
7 12

3
0 0 1
2 1 1
4 1 2
2
1 1 1
3 2 1
2 2

2
0 0 3
2 3 1
1
1 3 1
1 3