首页 > 试题广场 > 奇异长度
[编程题]奇异长度

给你一个图,0节点连接这一个联通块a1节点连接着一个联通块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

输入

5 4 10
0 1
0 2
1 3
1 4

输出

4

备注:
据推测,此题的奇异路径应只算经过“从0到1”这条边一次的路径,即经过“从1到0”一次的路径是不算的。
思路:
1. 因为0-1这条边是“桥”,所以任何路径都可以分成左右两段来看,即“断开” 0-1这条边,分别看2边的长度。例如长度为20的路径,可以分别考虑从0开始,在联通块a中长度为i的路径数x_i,在b中长度为j的路径数y_j(i和j满足i+j=19),则长度为20的路径共有种,更通用地,长度为t的路径数量为
2. 从长度为1开始,假设长度为1、2、3、4、...的路径数分别有s_1,s_2,s_3,s_4,...种,则我们希望求出t,使得,通俗地说就是前t项和“恰好”达到了k
3. 我们考虑依次枚举t=1,2,3,...并按1中的方法求出对应长度的路径数总和,一旦总和达到k,此时t即为所求
4. 现在我们考虑怎么求1中的,我们可以分别求解x_i,容易发现,0-1断开后,a和b2个连通块分别独立。于是问题简化为求解x_i
5. 设vis[u][len]表示:从顶点u出发,长度为len的路径数量,则 ,其中v_i表示和顶点u相连的第i个顶点,即从顶点u出发,长度为len的路径数,等于从u的邻接节点出发,长度为len-1的路径数之和。于是问题得解。实际实现时,我们每次可以记录一下当前得到的vis[u][len],避免出现重复计算。

最后,我们分析一下时间复杂度,包括上述枚举的长度的上界。
I. 假设a和b中,节点0和1任一点的度(拆开看,将0-1这条边除外)大于等于2,那么我们可以发现vis[u][len]可以以指数速度扩散,长度为len时,路径数至少为,此时len的上限是,我们记忆化vis[u][len]后(否则会有重复计算),计算这一步的空间复杂度为时间复杂度为,整体时间复杂度为
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 回复(1)