lijyya's Blog
0%

Codeforces Round 677

发表于 更新于 分类于 ， ，

Codeforces Round 677

D. 构造

D. Districts Connection

F. DP, 背包

F. Zero Remainder Sum

G. Dijkstra, 图论

G. Reducing Delivery Cost

D. Districts Connection

题目大意

给定 n 个点，每个点对应一个 a_i ，当且仅当 a_i != a_j 时 i 和 j 之间可以连一条无向边，判断是否能连成一棵树，如果不行输出 NO ，否则输出 YES 并输出每条连边的点对。

题解

首先，判断是否每个数都相等，如果是直接输出 NO ，否则一定能生成树，输出 YES

接着，先选出 a_i != a_j 的一对点 i 和 j 并输出，对于其他的点 k ，如果 a_i = a_k ，与 i 连，否则与 j 连。

F. Zero Remainder Sum

题目大意

给定一个 n \times m 的矩阵（ n 行 m 列），对于每一行可以选择不多于 \left \lfloor \frac{m}{2} \right \rfloor （可以是 0 次）的元素，要求是它们的和（指的是所有行加起来的和）能被 k 整除，要使它们的和最大。

题解

这显然是一题 DP 。

令 f[x][y][cnt][rem] 表示当前位置在 a_{x, y} ，第 x 行已经选了 cnt 个元素，剩余量为 rem 的最大的可能的和。

然后就转换成背包问题。

当 cnt \leq \left \lfloor \frac{m}{2} \right \rfloor 时，可以取也可以不取。如果 a_{x,y} 不是当前行的最后一个元素，状态转移方程可以写成：

不取： f[x][y + 1][cnt][rem] = max (f[x][y + 1][cnt][rem], f[x][y][cnt][rem])

取： f[x][y + 1][cnt + 1][(rem + a_{x,y}) \% k)] = max(f[x][y + 1][cnt + 1][(rem + a_{x,y}) \% k], f[x][y][cnt][rem]+a_{x,y})

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 7e1 + 5;

int n, m, k;
int a[MAXN][MAXN];
int f[MAXN][MAXN][MAXN][MAXN];
int ans;

int main() {
    memset(f, -1, sizeof f);

    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &a[i][j]);
            f[i][j][0][0] = 0;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int cnt = 0; cnt <= m / 2; ++cnt) {
                for (int res = 0; res < k; ++res) {
                    if (f[i][j][cnt][res] == -1) continue;

                    int ni = (j == m) ? i + 1 : i;
                    int nj = (j == m) ? 1 : j + 1;

                    if (i != ni) {
                        f[ni][nj][0][res] = max(f[ni][nj][0][res], f[i][j][cnt][res]);
                    } else {
                        f[ni][nj][cnt][res] = max(f[ni][nj][cnt][res], f[i][j][cnt][res]);
                    }

                    if (cnt <= m / 2 - 1) {
                        int nres = (res + a[i][j]) % k;

                        if (i != ni) {
                            f[ni][nj][0][nres] = max(f[ni][nj][0][nres], f[i][j][cnt][res] + a[i][j]);
                        } else {
                            f[ni][nj][cnt + 1][nres] = max(f[ni][nj][cnt + 1][nres], f[i][j][cnt][res] + a[i][j]);
                        }
                    }
                }
            }
        }
    }

    printf("%d\n", max(0, f[n + 1][1][0][0]));
}

G. Reducing Delivery Cost

题目大意

给定一个 n 点 m 边的无向图，第 i 条边连接 x_i 和 y_i ，费用为 w_i 。

有 k 条传输路径，第 i 条传输路径从 a_i 到 b_i ，信使总是会挑选最便宜的路径使货物从 a_i 运输到 b_i 。路径有可能从一点出发又回到这一点，有些路径可能重合，而你必须将他们分别独立计算。

你可以使最多一条边的费用变成 0 。

令 d(x,y) 表示从 x 到 y 的最小费用，你的任务是找到选择了一条边（最佳方案）使其费用变成 0 后所有信使传输路径的费用总和的最小值。也就是说，求出选择了一条边（最佳方案）使其费用变成 0 后尽可能最小的 \sum_{i=1}^{k}d(a_i,b_i) 。

题解

大体思路：预处理之后尝试着用 0 来代替每条边的费用。

预处理：跑 n 次 dijkstra 处理出两点之间的最短路。

每条边 (x, y) 对于每条路径 (a,b) 来说，有三种不同情况：

  1. 替换前后都不在最短路上
  2. 替换前不在替换后在
  3. 替换前就在最短路上（本质上来说和第二种是一样的）

状态转移方程：

  1. d(a, b) = d(a, b)
  2. d(a, b) = min(d(a, x) + d(y, b), d(a, y) + d(x, b))
  3. 同 2

因此如果替换的是边 (x, y) ，那么当前答案答案就是： \sum_{i = 1} ^ k min(d(a_i, b_i), d(a_i, x) + d(y, b_i), d(a_i, y) + d(x, b_i))

枚举比较后即可得到最终答案。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 5;
const int INF = 0x3f3f3f3f;

int n, m, k;

vector<vector<int> > d;
vector<vector<pair<int, int> > > g;

void dijkstra(int s, vector<int> &d) {
    d = vector<int>(n, INF);
    d[s] = 0;

    set<pair<int, int> > st;
    st.insert({d[s], s});

    while (!st.empty()) {
        int v = st.begin() -> second;
        st.erase(st.begin());
        for (auto u : g[v]) {
            int to = u.first;
            int w = u.second;
            if (d[to] > d[v] + w) {
                auto it = st.find({d[to], to});
                if (it != st.end())
                    st.erase(it);
                d[to] = d[v] + w;
                st.insert({d[to], to});
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    g = vector<vector<pair<int, int> > >(n);
    for (int i = 0; i < m; ++i) {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        --x;
        --y;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    vector<pair<int, int> > r(k);
    for (auto &u : r) {
        scanf("%d %d", &u.first, &u.second);
        --u.first;
        --u.second;
    }

    d = vector<vector<int> > (n);
    for (int v = 0; v < n; ++v) {
        dijkstra(v, d[v]);
    }

    int ans = INF;
    for (int v = 0; v < n; ++v) {
        for (auto u : g[v]) {
            int to = u.first;
            int w = u.second;
            int cur = 0;
            for (auto p : r) {
                int a = p.first;
                int b = p.second;
                cur += min({d[a][b], d[a][v] + d[to][b], d[a][to] + d[v][b]});
            }
            ans = min(ans, cur);
        }
    }

    printf("%d\n", ans);
}