BZOJ 1875 [SDOI2009]HH去散步

题目描述

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径

输入

第一行：五个整数N，M，t，A，B。

N表示学校里的路口的个数

M表示学校里的路的条数

t表示HH想要散步的距离

A表示散步的出发点

B则表示散步的终点。

接下来M行

每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。

数据保证Ai ！= Bi,但不保证任意两个路口之间至多只有一条路相连接。

路口编号从0到N -1。

同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。

答案模45989。

N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

输出

一行，表示答案。

样例输入

样例输出

这t的范围上来就看到了矩阵乘带个log，最开始思路是把点之间关系作为矩阵中元素，怎么搞也搞不出来，考完后题解说把边的关系作为元素ヾ(｡｀Д´｡)，而且难调的一逼，快速幂是有多久没打，还打错了一遍，还有，千万不要重载[]，慢的一逼。

code：

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <queue>
#define MAXN 505
#define inf 0x3f3f3f3f
using namespace std;
int d1[9]={0,0,1,-1};
int d2[9]={-1,1,0,0};
bool vis[MAXN];
int h[MAXN][MAXN],n,m,Ans,len;
bool instack[MAXN][MAXN];
 
typedef pair<int,int> pa;
queue<pa>q;
 
 
void connect(pa o){
    int x = o.first,y=o.second;
    for(int i=0;i<4;i++){
        int x1=x+d1[i],y1=y+d2[i];
        if(h[x1][y1]<h[x][y]&&!instack[x1][y1])q.push(make_pair(x1,y1)),instack[x1][y1]=1;
    }
}
 
struct seg{
    int l,r;
    bool operator < (const seg &a)const{
        return l<a.l;
    }
    seg(){
        l=inf;r=-inf;
    }
}a[MAXN];
 
void bfs(int x){
    memset(instack,0,sizeof instack);
    ++ len;
    q.push(make_pair(1,x));
    while(!q.empty()){
        pa k = q.front();q.pop();
        if(k.first>n||k.first<1)continue;
        if(k.second>m||k.second<1)continue;
        if(k.first == n&&k.second<=m&&k.second>=1){
            vis[k.second]=1;
            a[len].r=max(a[len].r,k.second);
            a[len].l=min(a[len].l,k.second);
        }
        connect(k);
    }
}
 
void work(){
    sort(&a[1],&a[len+1]);
    int r=0,num=1,ans = 0;
    while(r<m&&num<=len){
        int maxn = 0;
        while(a[num].l<=r+1&&num<=len){
            maxn = max(maxn,a[num].r);
            num ++;
        }
        r=maxn;
        ans ++;
    }
    printf("1
%d
",ans);
}
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&h[i][j]);
    for(int i=1;i<=m;i++)
        if(h[1][i]>=h[1][i-1]&&h[1][i]>=h[1][i+1])
            bfs(i);
    for(int i=1;i<=m;i++)if(!vis[i])Ans++;
    if(Ans)printf("0
%d
",Ans);
    else work();
}