列表

详情


NC24266. [USACO 2019 Feb P]Moorio Kart

描述

Bessie and Farmer John enjoy goat kart racing. The idea is very similar to Go-Kart racing that others enjoy, except the karts are pulled by goats and the track is made from nearby farmland. The farmland consists of N meadows and M roads, each connecting a pair of meadows.

Bessie wants to make a course from nearby farms. A farm is a subset of two or more meadows within which every meadow can reach every other meadow along a unique sequence of roads.

The nearby farmland may contain multiple farms. Suppose there are K farms. Bessie would like to make a goat kart loop by connecting all K farms by adding K roads of length X. Each farm should be visited exactly once and at least one road must be traversed inside each farm.

To make the course interesting for racers, the total length of the track should be at least Y. Bessie wants to know the sum, over all such interesting tracks, of the total track lengths. A track is different from another if there are two meadows which are adjacent (after adding the roads between farms) in one track but not the other. Please note that only the roads chosen matter, and not the direction the goat karts will travel along those roads.

输入描述

The first line of input contains N, M, X, and Y where 1≤N≤1500, 1≤M≤N−1, and 0≤X,Y≤2500.

Each of the M following lines describe roads. The lines are of the form: Ai Bi Di, meaning that meadows Ai and Bi are connected with a road of integer length Di (1≤Ai,Bi≤N, 0≤Di≤2500). Each meadow is incident to at least one road, and there are no cycles of roads.

In at least 70% of the test cases, it is also guaranteed that N≤1000 and Y≤1000.

输出描述

Output a single integer, giving the sum of track lengths over all interesting tracks. As the sum of track lengths can be quite large, print the sum of lengths modulo 10^9+7.

示例1

输入:

5 3 1 12
1 2 3
2 3 4
4 5 6

输出:

54

说明:

This example has 6 possible tracks

1 --> 2 --> 4 --> 5 --> 1 (length 11)

1 --> 2 --> 5 --> 4 --> 1 (length 11)

2 --> 3 --> 4 --> 5 --> 2 (length 12)

2 --> 3 --> 5 --> 4 --> 2 (length 12)

1 --> 2 --> 3 --> 4 --> 5 --> 1 (length 15)

1 --> 2 --> 3 --> 5 --> 4 --> 1 (length 15)

The answer is 12+12+15+15=54, adding up only the tracks where the length is at least 12.

Note that for this problem, the standard time limit is increased to 3 seconds per test case (6 seconds per case for Java and Python).

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 124ms, 内存消耗: 6404K, 提交时间: 2023-08-22 14:49:04

/**
 * 觉得xyx讲的非常好
就用一下他的写法吧
考虑用所有的路径减去不合法的路径的长度。
所有路径的长度是容易计算的,只需要考虑每一条边被统计了多少次。
不合法的路径即长度不足 Y 的路径,可以通过每一个联通块内路径的数组卷积得到。
注意到当且仅当联通块大小达到 的级别,
不足 Y 的所有路径长度才有可能被全部取到,
因此在卷积时特判数组中为 0的位置跳过即可。
所以我们暴力枚举即可
复杂度多一个根号:
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 1e9 + 7;
const int N = 2505;
int to[N << 1], nxt[N << 1], len[N << 1], fir[N], bel[N], fa[N], ecnt, cnt, x, y;
ll tot[N][N], f[N][2], g[N][2], sum[N][N], ans;
template <typename T> inline void upd(T &a, T b) {a = (a + b) % p;}
int find(int u) {return fa[u] = fa[u] == u ? u : find(fa[u]);}
void ae(int u, int v, int w) {to[++ecnt] = v; nxt[ecnt] = fir[u]; len[ecnt] = w; fir[u] = ecnt;}
void build(int u, int f, int id) {
    int v, i;
    bel[u] = id;
    for (i = fir[u]; i; i = nxt[i]) {
        v = to[i];
        if (v != f) build(v, u, id);
    }
}
void dfs(int u, int f, int l) {
    int v, w, i;
    if (f) {upd(sum[bel[u]][min(l, y)], 1ll * l); ++tot[bel[u]][min(l, y)];}
    for (i = fir[u]; i; i = nxt[i]) {
        v = to[i]; w = len[i];
        if (v != f) dfs(v, u, l + w);
    }
}
int main() {
    int n, m, now, u, v, w, i, j, k;
    scanf("%d%d%d%d", &n, &m, &x, &y);
    for (i = 1; i <= n; ++i) fa[i] = i;
    for (i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        ae(u, v, w); ae(v, u, w);
        fa[find(u)] = find(v);
    }
    for (i = 1; i <= n; ++i) if (i == find(i)) build(i, 0, ++cnt);
    for (i = 1; i <= n; ++i) dfs(i, 0, 0);
    now = min(cnt * x, y); f[now][0] = 1; f[now][1] = cnt * x;
    for (i = 1; i <= cnt; ++i) {
        for (j = now; j <= y; ++j) {g[j][0] = f[j][0]; g[j][1] = f[j][1]; f[j][0] = f[j][1] = 0;}
        for (j = 0; j <= y; ++j)
            if (tot[i][j])
                for (k = now; k <= y; ++k)
                    if (g[k][0]) {
                        upd(f[min(j + k, y)][0], 1ll * g[k][0] * tot[i][j]);
            			upd(f[min(j + k, y)][1], 1ll * g[k][0] * sum[i][j] + 1ll * g[k][1] * tot[i][j]);
                    }
    }
    ans = f[y][1];
    for (i = 1; i < cnt; ++i) ans = ans * i % p;
    printf("%lld\n", ans * 500000004 % p);
    return 0;
}

上一题