我要招人

去企业版

首页 > 试题广场 >

奇异长度

[编程题]奇异长度

热度指数：75 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给你一个图，0节点连接这一个联通块a，1节点连接着一个联通块b,ab仅由01这条边相连。现在我们定义奇异路径为恰好经过0-1这条边一次的路径。在这个图中有无数条奇异路径，问第k长的奇异路径长度是多少？

输入描述:

输入若干行，第一行有三个正整数n,m,k,表示有n个节点，0~n-1,有m条边，问第k长，接下来有m行u,v,表示边，保证0-1边只出现一次,保证a,b联通块只通过0-1相连。
5<=n<=100,k<2^40

输出描述:

输出一行表示答案

示例1

输入

输出

备注:

据推测，此题的奇异路径应只算经过“从0到1”这条边一次的路径，即经过“从1到0”一次的路径是不算的。

算法知识视频讲解

bit_line

思路：

1. 因为0-1这条边是“桥”，所以任何路径都可以分成左右两段来看，即“断开” 0-1这条边，分别看2边的长度。例如长度为20的路径，可以分别考虑从0开始，在联通块a中长度为i的路径数x_i，在b中长度为j的路径数y_j（i和j满足i+j=19），则长度为20的路径共有 $\sum_{i=0}^{19}x_i * y_{19-i}$ 种，更通用地，长度为t的路径数量为 $\sum_{i=0}^{t}x_i * y_{t-i}$ 。

2. 从长度为1开始，假设长度为1、2、3、4、...的路径数分别有s_1,s_2,s_3,s_4,...种，则我们希望求出t，使得 $\sum_{i=1}^{t}s_i \ge k$ 且 $\sum_{i=1}^{t-1}s_i < k$ ，通俗地说就是前t项和“恰好”达到了k

3. 我们考虑依次枚举t=1,2,3,...并按1中的方法求出对应长度的路径数总和，一旦总和达到k，此时t即为所求

4. 现在我们考虑怎么求1中的 $\sum_{i=0}^{t}x_i * y_{t-i}$ ，我们可以分别求解 $x_i$ 和 $y_{t-i}$ ，容易发现，0-1断开后，a和b2个连通块分别独立。于是问题简化为求解 $x_i$ 。

5. 设vis[u][len]表示：从顶点u出发，长度为len的路径数量，则 $vis[u][len] = \sum_{i=0}^{r}{vis[v_i][len-1]}$ ，其中v_i表示和顶点u相连的第i个顶点，即从顶点u出发，长度为len的路径数，等于从u的邻接节点出发，长度为len-1的路径数之和。于是问题得解。实际实现时，我们每次可以记录一下当前得到的vis[u][len]，避免出现重复计算。

最后，我们分析一下时间复杂度，包括上述枚举的长度的上界。

I. 假设a和b中，节点0和1任一点的度（拆开看，将0-1这条边除外）大于等于2，那么我们可以发现vis[u][len]可以以指数速度扩散，长度为len时，路径数至少为 $2^{len/2}$ ，此时len的上限是 $log_2{k_{max}}*2$ ，我们记忆化vis[u][len]后（否则会有重复计算），计算这一步的空间复杂度为 $O(n * \log k)$ ，时间复杂度为 $O(n^2 * \log k)$ ，整体时间复杂度为 $O(n^2 * \log^2 k)$

II. 假设a和b中，0和1任一点的度都不大于2（为0或1），那么上述求解方***导致时间复杂度退化为O(k)，所以实际上我们需要对这种情形特殊考虑一下。当然，本题的测试数据并没有特意卡这种case，我也没在代码中特判，不过还是应该知道这一点

#include <cstdio>
#include <cstring>
#include <vector>
using std::vector;
 
typedef long long ll;
 
const int MAX = 102;
vector<int> G[MAX];
ll vis[MAX][MAX<<8];
int n, m;
ll k;
 
ll get(int idx, int len) {
    if (vis[idx][len] > 0) {
        return vis[idx][len];
    }
    if (len == 0) {
//      printf("vis[%d][%d]=1\n", idx, len);
        return vis[idx][len] = 1;
    }
    if (len == 1) {
//      printf("vis[%d][%d]=%d\n", idx, len, G[idx].size());
        return vis[idx][len] = (ll)G[idx].size();
    }
 
    ll s = 0LL;
    for (auto it: G[idx]) {
        ll val = get(it, len-1);
        s += val;
//      printf("vis[%d][%d]+=<%d,%d,%lld>=%lld\n", idx, len, it, len-1, val, s);
    }
//  printf("vis[%d][%d]=%lld\n", idx, len, s);
    return vis[idx][len] = s;
}
 
int main() {
    while (~scanf("%d%d%lld", &n, &m, &k)) {
        for (int i = 0; i < n; i++) {
            G[i].clear();
        }
        int u, v;
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &u, &v);
            if ((u == 0 && v == 1) || (u == 1 && v == 0)) {
                continue;
            }
            G[u].push_back(v);
            G[v].push_back(u);
        }
        memset(vis, 0, sizeof(vis));
         
        if (k == 1) {
            puts("1");
            continue;
        }
 
        int ans = 0;
        while (k > 0) {
            ans++;
            for (int i = 0; i <= ans-1; i++) {
                k -= get(0, i) * get(1, ans - 1 - i);
//              printf("ans=%d,k=[%lld],i=<%d,%lld>,ans-i=<%d,%lld>\n", ans, k, i, get(0, i), ans-i, get(1, ans-i));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

编辑于 2019-08-21 01:30:45 回复(3)

ac_q

我还是不太理解，怎么就无限个奇异路径，样例中不就给了4条线吗，

发表于 2020-04-16 12:05:06 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 2018 PHP工程师 360集团 Java工程师

上传者：小小

难度：

2条回答 34收藏 2852浏览

通过挑战的用户

牛客18772...

2021-04-17 10:43:24
七层楼

2021-03-23 16:05:28
牛客20339...

2020-09-11 11:07:31
。201903...

2020-09-10 19:56:44
槡槡

2020-06-03 13:30:08

奇异长度

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题