邻接矩阵例题

another_world · 2023-09-28 11:25:11 · 个人记录

邻接矩阵

• 例题：[HNOI2002] 公交车路线

1. 考虑朴素动态规划，设 dp[k][i] 表示在换乘 k 次后到达第 i 站的方案数，则有转移方程： dp[k][i]=\sum dp[k-1][j]，j 满足换乘 1 次从第 j 站到达第 i 站，题目里描述：j 即为点 i 在环上相邻的两点

2. 设矩阵 A[i][[j] 表示从第 i 站换乘 1 次能否到达第 j 站，则有： dp[k][i]=\sum dp[k-1][j] \times A[j][i]，观察形式，发现即为矩阵乘法，根据矩阵乘法结合律，直接矩阵快速幂优化，时间复杂度：O(8^3\log n)

Code:

#include<bits/stdc++.h> 
using namespace std;
#define mod 1000
const int N=10;
int n;
int f[N],a[N][N]; 
void mul(int f[],int a[][N]) {
    int c[N]={};
    for(int j=1; j<=8; j++)
        for(int k=1; k<=8; k++)
            c[j]=(c[j]+f[k]*a[k][j])%mod;
    memcpy(f,c,sizeof(c));
}
void mulself(int a[][N]) {
    int c[N][N]={};
    for(int i=1; i<=8; i++)
        for(int j=1; j<=8; j++)
            for(int k=1; k<=8; k++)
               c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
    memcpy(a,c,sizeof(c)); 
}
int main() {
    scanf("%d",&n);
    f[1]=1;
    for(int i=1; i<=8; i++) 
        for(int j=1; j<=8; j++) {
            if(i==5) continue;
            if((i==1 && j==8) || (i==8 && j==1) || abs(i-j)==1) a[i][j]=1;
        }
    while(n) {
        if(n&1) mul(f,a);
        mulself(a);
        n>>=1;
    }
    printf("%d",f[5]);
    return 0;
}

拆点 + 邻接矩阵

• 例题：[SCOI2009] 迷路

1. 不妨先考虑边权只有 0 和 1 的情况，那么与上道例题类似，设 dp[k][i] 表示在 k 时刻到达点 i 的方案数，同样设矩阵 A[i][j] 表示花费 1 单位时间能否从点 i 到达点 j，转移方程：dp[k][i]=\sum dp[k-1][j] \times A[j][i]，矩阵快速幂优化

2. 回到边权 w\in [0,9] \cap Z，由于边权可能大于 1，那么定义的矩阵 A 就无法进行转移，发现边权的范围较小，考虑将每个点拆成 9 个状态，转化成边权只有 0 和 1 的情况

3. 对于任意点 i 的 有序数对 (i,0) 表示点 i 本身，以此类推有序数对 (i,j)，j\in[1,8] \cap Z 表示与点 i 距离为 j 的点，注意这里只有 (i,0) 是原图中真实存在的点，其余的是虚构的点用来维护矩阵状态

4. 那么对于原图的边 (i,j,k)，则有有序数对 (i,0) 和 (j,k-1) 间连边，同样对于点 j 的其余状态点间也要连边 (转移边权的长度)

Code:

#include<bits/stdc++.h> 
using namespace std;
#define mod 2009
const int N=100;
int n,m,t;
char str[N];
int f[N],a[N][N];
int pos(int x,int y) {
    return x+y*n;
}
void mul(int f[],int a[][N]) {
    int c[N]={};
    for(int j=1; j<=m; j++)
        for(int k=1; k<=m; k++)
            c[j]=(c[j]+f[k]*a[k][j])%mod;
    memcpy(f,c,sizeof(c));
}
void mulself(int a[][N]) {
    int c[N][N]={};
    for(int i=1; i<=m; i++)
        for(int j=1; j<=m; j++)
            for(int k=1; k<=m; k++)
                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
    memcpy(a,c,sizeof(c));
}
int main() {
    scanf("%d%d",&n,&t);
    m=n*9;
    for(int i=1; i<=n; i++) {
        scanf("%s",str+1);
        for(int j=1; j<=n; j++) {
            int len=str[j]-'0';
            if(len>0) {
                a[pos(i,0)][pos(j,len-1)]=1;
                for(int k=len-1; k>=1; k--)
                    a[pos(j,k)][pos(j,k-1)]=1;
            }
        }
    }
    f[1]=1;
    while(t) {
        if(t&1) mul(f,a);
        mulself(a);
        t>>=1;
    }
    printf("%d",f[n]);
    return 0;
}

点边互换 + 邻接矩阵

• 例题：[SDOI2009] HH去散步

1. 先不考虑不能走反边的限制，那么显然直接基础邻接矩阵即可解决，再回到该限制，以及重边的存在，考虑将无向边拆成两条有向边，同样设矩阵 A[i][j] 表示花费 1 单位时间能否从第 i 条边到达第 j 条边，这样又转化为基础邻接矩阵问题了

2. 让边从 0 开始编号，通过异或判断任意两条边是否互为反边，是则可以转移，否则不可以转移

Code:

#include<bits/stdc++.h> 
using namespace std;
const int N=55;
const int M=125;
#define mod 45989
int n,m,t,st,ed;
struct EDGE { 
    int v,lt; 
}E[M];
int head[N],tot=0;
void add(int u,int v) {
    E[tot].v=v;
    E[tot].lt=head[u];
    head[u]=tot++;
}
int f[M],a[M][M];
bool flag[M];
void mul(int f[],int a[][M]) {
    int c[M]={};
    for(int j=0; j<tot; j++)
        for(int k=0; k<tot; k++)
            c[j]=(c[j]+f[k]*a[k][j])%mod;
    memcpy(f,c,sizeof(c));
}
void mulself(int a[][M]) {
    int c[M][M]={};
    for(int i=0; i<tot; i++)
        for(int j=0; j<tot; j++)
            for(int k=0; k<tot; k++)
                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
    memcpy(a,c,sizeof(c));
} 
int main() {
    memset(head,-1,sizeof(head));
    scanf("%d%d%d%d%d",&n,&m,&t,&st,&ed);
    t--; // 考虑单位 1 时刻位于始点为 st 的边上，目标单位 t 时刻位于终点为 ed 的边上 
    for(int x,y,i=1; i<=m; i++) { // 把无向边拆成有向边 
        scanf("%d%d",&x,&y);
        if(x==st) f[tot]=1; 
        if(y==ed) flag[tot]=1;
        add(x,y);
        if(y==st) f[tot]=1;
        if(x==ed) flag[tot]=1;
        add(y,x);
    }
    for(int i=0; i<tot; i++) {  
        int u=E[i].v;
        for(int j=head[u]; j!=-1; j=E[j].lt) {
            if(i!=(j^1)) {  // 保证不走反边 
                a[i][j]=1;
            }
        }
    }

    while(t) {
        if(t&1) mul(f,a);
        mulself(a);
        t>>=1;
    }
    int ans=0;
    for(int i=0; i<tot; i++)
        if(flag[i]) ans=(ans+f[i])%mod;
    printf("%d",ans); 
    return 0;
}

bitset 优化矩阵乘法

• 例题：CF576-D

• 矩阵乘法的时间复杂度多为 O(n^3\log k)，有时候需要 bitset 对矩阵乘法的部分进行优化

1. 贪心的考虑，将各边按 d 值从小到大排序，依次添边，先判断能否从点 1 到达点 n，若能，则求出答案最小值

2. 同样考虑设 dp[k][i] 表示走过了 k 条边能否从点 1 到达点 i，而对于解锁每条边 i 需要已经走过 d[i] 条边的限制，相当于将第一维状态划分成若干阶段，不同阶段解锁的边不同，也对应着不同的邻接矩阵

3. 具体实现，考虑当前解锁了前 i 条边，将要添加第 i+1 条边，还需再走 d[i+1]-d[i] 条边，即再进行 d[i+1]-d[i] 次状态转移，那么解锁第 i+1 条边后，在当前图上跑多源最短路，答案统计即为 \min(d[i+1]+dis[j][n])，且要求 dp[d[i+1]][j]=1

Code:

#include<bits/stdc++.h> 
using namespace std;
#define inf 0x3f3f3f3f
const int N=160;
int n,m,dis[N][N],ans=inf;; 
struct EDGE {
    int x,y,d; 
}edge[N];
inline bool cmp(EDGE a,EDGE b) { return a.d<b.d; }
bitset<N> f[N],a[N];  // f[k][j] 表示能否从点 1 走 k 步到达点 j，a[i][j] 表示点 i 到点 j的边是否解锁 
void mul(bitset<N> f[N],bitset<N> a[N]) {
    bitset<N> c[N]={};
    for(int i=1; i<=n; i++)
        for(int k=1; k<=n; k++)
            if(f[i][k])
                c[i]|=a[k];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f[i][j]=c[i][j];
}
int main() {
    freopen("flights.in","r",stdin);
    freopen("flights.out","w",stdout); 
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) 
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].d);
    sort(edge+1,edge+m+1,cmp);
    for(int i=1; i<=n; i++) {
        f[i][i]=1;
    }    
    for(int t=1; t<=m; t++) {
        for(int i=1; i<=n; i++) a[i].reset();
        for(int i=1; i<t; i++) {
            a[edge[i].x][edge[i].y]=1;
        }
        int b=edge[t].d-edge[t-1].d;
        while(b>0) { // 考虑解锁第 i 条边后，即总共走 edge[i].d 步的数组 f 的状态 
            if(b&1) mul(f,a);
            mul(a,a);
            b>>=1;
        }
        for(int i=1; i<=n; i++) 
            for(int j=1; j<=n; j++) 
                dis[i][j]=i==j?0:inf;
        for(int i=1; i<=t; i++) 
            dis[edge[i].x][edge[i].y]=1;
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

        for(int i=1; i<=n; i++)
            if(f[1][i]) ans=min(ans,edge[t].d+dis[i][n]); 
    }
    if(ans==inf) printf("Impossible");
    else printf("%d",ans); 
    return 0;
}

分组矩阵

• 例题：[ZJOI2005] 沼泽鳄鱼

1. 由于鳄鱼的最大运动周期为 lcm(2,3,4)=12 ，考虑建立单位周期的邻接矩阵，而非单位时间的邻接矩阵，依据单位周期进行矩阵快速幂优化，对于不满 1 单位周期的直接暴力矩阵乘法

Code:

#include<bits/stdc++.h> 
using namespace std;
#define mod 10000
const int N=60;
int n,m,st,ed,t,fish,p[N],mp[N][N];
int a[20][N][N],A[N][N]; // 周期最大为 12，考虑一个周期内的邻接矩阵，依据周期快速幂，不满一个周期的直接矩阵乘 
int f[N];
void mul(int f[N],int a[N][N]) {
    int c[N]={};
    for(int j=0; j<n; j++)
        for(int k=0; k<n; k++)
            c[j]=(c[j]+f[k]*a[k][j])%mod;
    memcpy(f,c,sizeof(c));
}
void mulself(int a[N][N],int b[N][N]) {
    int c[N][N]={};
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            for(int k=0; k<n; k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
    memcpy(a,c,sizeof(c)); 
}
int main() {
    scanf("%d%d%d%d%d",&n,&m,&st,&ed,&t);
    for(int x,y,i=1; i<=m; i++) {
        scanf("%d%d",&x,&y);
        mp[x][y]=1;
        mp[y][x]=1;
        for(int j=1; j<=12; j++)
            a[j][x][y]=a[j][y][x]=1;
    }    
    scanf("%d",&fish);
    for(int T,i=1; i<=fish; i++) {
        scanf("%d",&T);
        for(int j=0; j<T; j++) {
            scanf("%d",&p[j]);  
        }
        for(int j=1; j<=12; j++) {
            for(int k=0; k<n; k++)
                a[j][k][p[j%T]]=0; 
        }
    }
    for(int i=0; i<n; i++) A[i][i]=1;
    for(int i=1; i<=12; i++) 
        mulself(A,a[i]);  
    f[st]=1;
    int b=t/12;     
    while(b) {
        if(b&1) mul(f,A); 
        mulself(A,A);
        b>>=1;
    } 
    int c=t%12;
    for(int i=1; i<=c; i++)
        mul(f,a[i]);
    printf("%d",f[ed]);
    return 0;
}

重定义矩阵乘法

• 例题：[USACO07NOV] Cow Relays G

• 观察 Folyd 的核心转移式：c[i][j]=\min(c[i][j],a[i][k]+b[k][j])，分析其是否满足结合律，从而进行矩阵快速幂优化，证明：

1. 设 D=(A \times B) \times C，则有 D_{i,j}=\min_{p=1}^{n}(\min_{q=1}^{n}(A_{i,q},B_{q,p}),C_{p,j})，依据所求，原式式等价于 \min_{p=1}^{n}\min_{q=1}^{n}(A_{i,q},B_{q,p},C_{p,j})

2. 则 D=A \times (B \times C)，同理等价于 \min_{p=1}^{n}\min_{q=1}^{n}(A_{i,q},B_{q,p},C_{p,j})

• 对于矩阵 A 和 B，有新矩阵 C=A*B

Code:

#include<bits/stdc++.h> // 多源最短路的转移表达式满足结合律，可以矩阵快速幂优化 
using namespace std;
#define inf 0x3f3f3f3f
const int N=210;
int n,m,t,st,ed,x[N],y[N],z[N],num[N],cnt;
int dis[N],a[N][N]; // dis[i][k] 表示走 k 步到达点 i 的最短路 
void mul(int f[N],int a[N][N]) {
    int c[N];
    memset(c,inf,sizeof(c));
    for(int j=1; j<=m; j++)
       for(int k=1; k<=m; k++)
           c[j]=min(c[j],f[k]+a[k][j]);
    memcpy(f,c,sizeof(c));
}
void mulself(int a[N][N],int b[N][N]) {
    int c[N][N];
    memset(c,inf,sizeof(c));
    for(int i=1; i<=m; i++)
        for(int j=1; j<=m; j++)
            for(int k=1; k<=m; k++)
                c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
    memcpy(a,c,sizeof(c));
}
int main() {
    freopen("relays.in","r",stdin);
    freopen("relays.out","w",stdout);
    scanf("%d%d%d%d",&n,&t,&st,&ed);
    for(int i=1; i<=t; i++) {
        scanf("%d%d%d",&z[i],&x[i],&y[i]);
        num[++cnt]=x[i];
        num[++cnt]=y[i];
    } 
    sort(num+1,num+cnt+1);
    m=unique(num+1,num+cnt+1)-num-1;
    st=lower_bound(num+1,num+m+1,st)-num;
    ed=lower_bound(num+1,num+m+1,ed)-num;
    for(int i=1; i<=m; i++)
        for(int j=1; j<=m; j++)
            a[i][j]=inf; // 注意这里初始矩阵 a 表示转移 1 步，所以当 i==j 时无法转移(无法从自己走向自己)，赋值正无穷 
    for(int i=1; i<=t; i++) {
        x[i]=lower_bound(num+1,num+m+1,x[i])-num;
        y[i]=lower_bound(num+1,num+m+1,y[i])-num;
        a[x[i]][y[i]]=a[y[i]][x[i]]=z[i];
    } 

    for(int i=1; i<=m; i++) dis[i]=i==st?0:inf;
    while(n) {
        if(n&1) mul(dis,a);
        mulself(a,a);
        n>>=1;
    }
    printf("%d",dis[ed]);
    return 0;
}

二进制优化矩阵乘法

• 例题：[NOI Online 提高组] 魔法值

1. 考虑重定义矩阵乘法，对于矩阵 A 和 B，有新矩阵 C=A*B

2. 那么对于每次询问进行矩阵快速幂，时间复杂度 O(qn^3\log k)

3. 不妨对于每次询问 q_{i} 进行二进制拆分，预处理所有 2^p 的邻接矩阵，这样时间复杂度优化至 O(n^3\log k+ qn^2\log k)

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=110;
const int t=35;
int n,m,q,w[N];
int f[N];
struct Matrix {
    int mat[N][N];
}a[t];
Matrix mulself(Matrix A,Matrix B) {
    Matrix C;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) C.mat[i][j]=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++)
                C.mat[i][j]^=A.mat[i][k]*B.mat[k][j];
    return C; 
}
void mul(int f[],Matrix a) {
    int c[N]={};
    for(int j=1; j<=n; j++)
        for(int k=1; k<=n; k++)
            c[j]^=f[k]*a.mat[k][j];
    memcpy(f,c,sizeof(c)); 
}
signed main() {
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) a[0].mat[i][j]=0;
    for(int i=1; i<=n; i++) scanf("%lld",&w[i]);
    for(int x,y,i=1; i<=m; i++) {
        scanf("%lld%lld",&x,&y);
        a[0].mat[x][y]=a[0].mat[y][x]=1;
    }
    for(int i=1; i<t; i++)
        a[i]=mulself(a[i-1],a[i-1]);
    for(int x,i=1; i<=q; i++)   {
        scanf("%lld",&x);
        for(int j=1; j<=n; j++) f[j]=w[j];
        for(int j=0; j<t; j++)
            if((x>>j)&1) mul(f,a[j]);
        printf("%lld\n",f[1]); 
    }
    return 0;
}

拆点 + 重定义矩阵乘法 + 二进制优化

• 例题：[NOI2020] 美食家

1. 作为一道练习题，简单讲一下大体思路：拆点处理，构建邻接矩阵，重定义矩阵乘法，在美食节之间进行转移，对于美食节当天直接加上额外的贡献即可，现在时间复杂度 O((5n)^3k\log T)，由于美食节之间的转移可以二进制优化，那么最终时间复杂度优化至 O((5n)^3\log T+(5n)^2k\log T)

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
const int maxn=210;
const int N=55;
int n,m,T,k,c[N],id[N][5],cnt;
ll f[N*5];
struct node {
    int tim,x,y;
}v[maxn];
inline bool cmp(node x,node y) { return x.tim<y.tim; }
struct Matrix {
    ll mat[N*5][N*5];
    Matrix() { memset(mat,-inf,sizeof(mat)); }
}a[32];
Matrix mulself(Matrix A,Matrix B) {
    Matrix C;
    for(int i=1; i<=cnt; i++)
        for(int j=1; j<=cnt; j++)
            for(int k=1; k<=cnt; k++)
                C.mat[i][j]=max(C.mat[i][j],A.mat[i][k]+B.mat[k][j]);
    return C;
}
void mul(ll f[],Matrix a) {
    ll c[N*5];
    for(int i=1; i<=cnt; i++) c[i]=-inf;
    for(int j=1; j<=cnt; j++) 
        for(int k=1; k<=cnt; k++)
            c[j]=max(c[j],f[k]+a.mat[k][j]);
    for(int i=1; i<=cnt; i++) f[i]=c[i];
}
int pos(int i,int j) { return id[i][j]==0?id[i][j]=++cnt:id[i][j]; }
int main() {
    scanf("%d%d%d%d",&n,&m,&T,&k);
    for(int i=1; i<=n; i++) scanf("%d",&c[i]);
    cnt=n;
    for(int i=1; i<=n; i++) id[i][0]=i;
    for(int x,y,z,i=1; i<=m; i++) {
        scanf("%d%d%d",&x,&y,&z);
        for(int j=0; j<z-1; j++) 
            a[0].mat[pos(x,j)][pos(x,j+1)]=0;
        a[0].mat[pos(x,z-1)][pos(y,0)]=c[y];
    }
    for(int i=1; i<=k; i++) 
        scanf("%d%d%d",&v[i].tim,&v[i].x,&v[i].y);

    sort(v+1,v+k+1,cmp);
    v[0]=(node){0,0,0},v[k+1]=(node){T,0,0};
    for(int i=1; i<=30; i++) a[i]=mulself(a[i-1],a[i-1]);
    for(int i=1; i<=cnt; i++) f[i]=-inf;
    f[1]=c[1];
    Matrix b;
    for(int i=1; i<=k+1; i++) {
        int t=v[i].tim-v[i-1].tim;
        for(int j=0; j<=30; j++) {
            if((t>>j)&1) mul(f,a[j]);
        }
        f[v[i].x]+=v[i].y;
    }
    printf("%lld",f[1]<0?-1:f[1]);
    return 0;
}