P2151 [SDOI2009]HH去散步解题报告

解题报告

P2151 [SDOI2009]HH去散步解题报告：

更好的阅读体验

这篇题解用图片讲述了点边互换的小trick和其意义，如果不会矩阵加速请看其他的题解（

前置知识

• 矩阵加速图上问题
• 基本的码力

题意

题意：给定一张$n$个点$m$条边的无向图，问长度为$k$，起点为$s$，终点为$t$的路径有多少条（不可以走过一条边后立即走这条边回来）。

数据范围：$1\leqslant n\leqslant 50$，$1\leqslant m\leqslant 60$，$1\leqslant k\leqslant 2^{30}$。

分析

这是一道点边互换，矩阵加速图上问题的好题。

我们发现这个走一条边不能立即走回来非常不好处理，这个时候我们需要用到一个小trick：点边互换（大家都说这个trick很常用，但是我只见过这道题用，看来是我太菜了）！

我们把所有有向边看做点（无向边转两条有向边），并连出一些边。两条边代表的点连起来，当且仅当一条边的终点为另一条边的起点。经过连边之后会形成一个有向图，比如，我们看一个无向图：

这张无向图会转换为下面的有向图（边权为边的编号，这里默认1为从序号小的点指向序号大的点，2为其反边）：

然后，我们把所有的边变为点，并进行连边。

然后我们考虑这张有向图的真正意义是什么，每一个点都代表在某一条边上，$s$到$t$的路径长度为$k$在这张图上表现为：$s$射出的边在图中的所有结点到射向$t$的所有边在图中的所有结点之间的路径长度为$k-1$（因为每一个结点实际上是一条边，这两条边之间的结点数量是这条路径的长度减一）。

然后考虑怎么处理之前的限制条件：走一条边不能立即走回来，发现在点边互换的有向图中很好处理，只需要将反边代表的结点之间的边去掉就可以了，即：

这样，我们就可以在上面跑矩阵快速幂了，具体可以见P2233 [HNOI2002]公交车路线这一题。

代码

#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=125,maxm=55,mod=45989;
int i,j,k,m,n,e,s,t,p,tot;
int to[maxn];
vector<int>v[maxm],w[maxm]; 
struct matrix{
    int len,wid;
    int mt[maxn][maxn];
}st;
matrix mul(matrix a,matrix b){
    matrix res;
    res.len=a.len,res.wid=b.wid;
    for(int i=1;i<=res.len;i++)
        for(int j=1;j<=res.wid;j++)
            res.mt[i][j]=0;
    for(int i=1;i<=a.len;i++)
        for(int j=1;j<=b.wid;j++)
            for(int k=1;k<=a.wid;k++)
                res.mt[i][j]=(res.mt[i][j]+a.mt[i][k]*b.mt[k][j]%mod)%mod;
    return res;
}
int calc(int x,int y,int b){
    int cnt=0;
    matrix a=st,res;
    res.len=1,res.wid=tot;
    for(int i=1;i<=tot;i++)
        res.mt[1][i]=0;
    for(int i=0;i<v[x].size();i++)
        res.mt[1][v[x][i]]=1;
    b--;
    while(b){
        if(b&1)
            res=mul(res,a);
        a=mul(a,a),b>>=1;
    }
    for(int i=0;i<w[y].size();i++)
        cnt=(cnt+res.mt[1][w[y][i]])%mod;
    return cnt;
}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&p,&s,&t);
    s++,t++;
    for(i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x++,y++;
        tot++,v[x].push_back(tot),w[y].push_back(tot),to[tot]=y;
        tot++,v[y].push_back(tot),w[x].push_back(tot),to[tot]=x;
    }
    st.len=st.wid=tot;
    for(i=1;i<=n;i++)
        for(j=0;j<w[i].size();j++)
            for(k=0;k<v[i].size();k++)
                st.mt[w[i][k]][v[i][j]]=1;
    for(i=1;i<=tot;i+=2)
        st.mt[i][i+1]=st.mt[i+1][i]=0;
    printf("%d\n",calc(s,t,p));
    return 0;
}