P1613

Aryper · 2021-11-09 18:08:40 · 个人记录

跑路

其实还是蛮有思维含量的。

首先明确题意：让我们求所有 1\to n 的路径中长度拆分为二进制数后 1 的个数最少为多少。

这仍然是一个让我们求最优路径的问题，那么我们先转化一下题目基础，让这个题变得比较可做。

首先，我们直接按照路径长度来做肯定是不好做的，发现对答案的贡献单位是每一个长度为 2^k 的路径，我们就很容易想到把每条长度为 2^k 的路径作为基础。

所以说，可以定义一个邻接矩阵 path(i,j,k)，表示是否存在 i\to j 且长度为 2^k 的路径。显然 k=0 可以直接得到，更大的 k 可以通过这些拓展，一个非常好的方法就是 Floyd。（说是倍增其实没有问题，吧。）

然后我们可以知道，所有 path(i,j,k) 为 1 的 dis(i,j) 都为 1，然后直接跑最短路即可。

时间复杂度 O(n^3\log \operatorname{maxlongint})。

做法不难，但是真的很有趣。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e2;

ll n,m,u,v;

ll path[N+5][N+5][N+5],dis[N+5][N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();
        path[u][v][0]=1;
    }

    for(ll p=1;p<=64;p++) {
        for(ll k=1;k<=n;k++) {
            for(ll i=1;i<=n;i++) {
                for(ll j=1;j<=n;j++) {
                    path[i][j][p]=path[i][j][p]||
                    (path[i][k][p-1]&&path[k][j][p-1]);
                }
            }
        }
    }

    memset(dis,0x3f,sizeof(dis));
    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=n;j++) {
            for(ll k=0;k<=64;k++) {
                if(path[i][j][k]) {
                    dis[i][j]=1;break;
                }
            }
        }
    }

    for(ll k=1;k<=n;k++) {
        for(ll i=1;i<=n;i++) {
            for(ll j=1;j<=n;j++) {
                if(dis[i][j]>dis[i][k]+dis[k][j]) {
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }

    write(dis[1][n]);

    return 0;
}