首页 > 其他分享 >P8906 [USACO22DEC] Breakdown P [最短路]

P8906 [USACO22DEC] Breakdown P [最短路]

时间:2024-11-08 21:09:17浏览次数:1  
标签:Breakdown int P8906 st 枚举 复杂度 USACO22DEC 条边 短路

P8906 [USACO22DEC] Breakdown P

Solution

  • 经典 trick,删边比较难处理,转换成加边,倒着处理。

  • 那我们接下来要考虑,怎么记录状态,以及,每加一次边要如何更新状态。

  • 还是比较套路地,我们可以求出 \(1\) 到某个点 \(i\) 经过 \(k/2\) 条边的最短路,再求出 \(i\) 到 \(n\) 经过 \(k-k/2\) 条边的最短路。根据这种思想,我们可能会思考折半搜索,分治之类的算法来解决这道题。

  • 如果我们要求 \(k/2\),就要求 \(k/4\),然后又要求 \(k/8\)。注意数据范围 \(k\le 8\),这种数据范围可能会成为解题的关键。那么,\(k/2\le 4\),\(k/4\le 2\),\(k/8\le 1\)。\(1\) 显然就是边界,就等于两点间的边权。如何求 \(2\) 呢?是不是只需要合并两条边。求 \(4\) 只需要把 \(2\) 的答案合并。这样一来,我们要记录的信息就非常少,不需要去写分治之类的递归程序。

  • 至于怎么合并。我们先考虑 \(1\) 到某一点 \(i\) 的情况,\(i\) 到 \(n\) 同理。我们设 \(f_i\) 表示 \(1\) 到 \(i\) 经过 \(k/2\) 条边的最短路,设 \(g_{i,j}\) 表示 \(i\) 到 \(j\) 只经过两条边的最短路。为啥 \(f\) 只记录终点,\(g\) 要记录起点和终点,因为 \(f\) 显然只有终点才是有用的,\(g\) 的话要记录起点和终点才能合并给 \(f\),不然咋合并?

  • 先大致口胡一遍算法。

    • 如果 \(k/2=4\),那 \(g+g\to f\)。
    • 如果 \(k/2=3\),那么 \(g+w\to f\),\(w\) 是边权。
    • 如果 \(k/2=2\),那么 \(g\to f\)。
    • 如果 \(k/2=1\),那么 \(w\to f\)。
  • 那我们接下来考虑如何更新状态,且是在正确的复杂度内。

  • 先考虑如何更新 \(g\)。假设当前加的是边 \((u\to v)\),那么 \(i\to u\to v\) 这条路径可能被更新 (\(i\) 是任意点),\(O(n)\) 枚举一个 \(i\),路径 \(u\to v\to j\) 也可能被更新,再 \(O(n)\) 枚举一个 \(j\)。更新 \(g\) 的总复杂度 \(O(n)\)。

  • 考虑如何更新 \(f\),这里以 \(k/2=4\) 为例。

    • 假设 \(f_i\) 经过的是这样一条边 \(1\to u\to v\to j\to i\)。

    • 如果当前加的边是 \(j\to i\),那么只需要 \(O(n)\) 枚举一个 \(v\),然后 \(g_{1,v}+g_{v,i}\to f_i\) 即可。

    • 如果当前加的边是 \(v\to j\),只需要 \(O(n)\) 枚举 \(i\),然后 \(g_{1,v}+g_{v,i}\to f_i\)。

    • 如果当前加的边是 \(u\to v\),\(O(n)\) 枚举 \(i\),然后也是 \(g_{1,v}+g_{v,i}\to f_i\)。(欸,怎么写起来都是一样的,不管了qwq)

    • 以上情况的总复杂度都是 \(O(n)\)。

    • 那如果当前加入的是 \(1\to u\) 呢?我们肯定要 \(O(n^2)\) 枚举 \(v\) 和 \(i\),但是注意到,起点为 \(1\) 的边只有 \(O(n)\) 条,于是均摊复杂度只有 \(O(n^3)\),还是能过的。

  • 综上,总复杂度 \(O(n^3)\),于是就可以愉快地 coding 了。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 3e2 + 5, M = N * N, inf = 0x3f3f3f3f;

int n, m, k, w[N][N], ans[M];

void Min(int &a, int b) {return a = min(a, b), void();}

struct Edge {int u, v;} e[M];

struct Worker {
    int f[N]; // st(起点) 到 i 的经过 k 条边的最短路
    int g[N][N]; // i 到 j 经过 2 条边的最短路
    int w[N][N]; // 边权
    int st, k;
    void init(int _st, int _k) {
        st = _st, k = _k;
        memset(f, 0x3f, sizeof(f));
        memset(g, 0x3f, sizeof(g));
        memset(w, 0x3f, sizeof(w));
    }
    void add(int u, int v, int _w) {
        w[u][v] = _w;
        if (k == 1) {
            if (u == st) f[v] = w[u][v];
            return;
        }
        for (int i = 1; i <= n; i++) {
            Min(g[i][v], w[i][u] + w[u][v]);
            Min(g[u][i], w[u][v] + w[v][i]);
        }
        if (k == 2) {
            for (int i = 1; i <= n; i++) f[i] = g[st][i];
            return;
        }
        if (k == 3) {
            if (u == st) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        Min(f[i], g[u][j] + w[j][i]);
                    }
                }
            } else {
                for (int i = 1; i <= n; i++) {
                    Min(f[i], w[st][u] + g[u][i]);
                    Min(f[i], w[st][v] + g[v][i]);
                    // Min(f[u], w[st][i] + g[i][u]); 该情况不会被更新
                    Min(f[v], w[st][i] + g[i][v]);
                }
            }
        }
        if (k == 4) {
            if (u == st) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        Min(f[i], g[u][j] + g[j][i]);
                    }
                }
            } else {
                for (int i = 1; i <= n; i++) {
                    Min(f[i], g[st][u] + g[u][i]);
                    Min(f[i], g[st][v] + g[v][i]);
                    // Min(f[u], g[st][i] + g[i][u]); 该情况不会被更新
                    Min(f[v], g[st][i] + g[i][v]);
                }
            }
        }
    }
}work1, workn;

int main() {
    cin >> n >> k;
    m = n * n;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> w[i][j];
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v;
    int k1 = k / 2, kn = k - k1;
    work1.init(1, k1), workn.init(n, kn);
    for (int i = m; i >= 1; i--) {
        ans[i] = inf;
        for (int j = 1; j <= n; j++) ans[i] = min(ans[i], work1.f[j] + workn.f[j]);
        work1.add(e[i].u, e[i].v, w[e[i].u][e[i].v]);
        workn.add(e[i].v, e[i].u, w[e[i].u][e[i].v]);
    }
    for (int i = 1; i <= m; i++) cout << (ans[i] == inf ? -1 : ans[i]) << "\n";
    return 0;
}```

标签:Breakdown,int,P8906,st,枚举,复杂度,USACO22DEC,条边,短路
From: https://www.cnblogs.com/chenwenmo/p/18535931

相关文章

  • [USACO22DEC] Palindromes P 题解
    T3[USACO22DEC]PalindromesP郝题。首先考虑给定一个串\(S\)怎么求出要换多少次。易得,不可能交换两个本来就相同的字符。不妨观察\(\textttG\)的回文关系,一对\(\textttG\)回文当且仅当第一个\(\textttG\)前面的\(\textttH\)数量等于第二个\(\textttG\)后面的......
  • [USACO22DEC] Making Friends P 题解
    T2[USACO22DEC]MakingFriendsP考虑删除一个点,会有如下的点相连接:题目要求如果两两个点建立联系,只会建立一次。所以,神奇地,我们取出当前待删的点所连接的最小的点,将它和剩下的点连接。手摸一下会发现这样就巧妙地给每个改建的边都建了一次。所以用一个set启发式合并就做完......
  • [USACO22DEC] Breakdown P 题解
    T1[USACO22DEC]BreakdownP比较显然的一点是,一次加一条边/一次删一条边,显然转化,这是显然的一条套路。这题的\(K\le8\),很有意思的数据范围,然后调用我们聪明的人类大脑得知需要用到折半搜索。所以我们只考虑\(K\le4\)的情况,令\(\mathit{st}\)表示折半搜索中考虑的起点。维......
  • P8908 [USACO22DEC] Palindromes P 题解
    P8908[USACO22DEC]PalindromesP题解算是好题,虽然没什么人做(简单地,我们考虑如何将一个字符串改变为回文串。显然如果我们判定所有\(\texttt{G}\)组成的是回文串,那么整个串一定是回文的。于是我们只考虑改变\(\texttt{G}\)的位置。那么由这类题的套路不难知道最优的变换......
  • P8907 [USACO22DEC] Making Friends P 题解
    P8907[USACO22DEC]MakingFriendsP题解我们考虑维护每个\(i\),在\(i\)的后面有多少个点和它有朋友关系。初步的想法是每删掉一个人就给集合里所有的点连边。但是我们发现这样太不优了,有很多边会重复连很多次。优化的想法是对于\(i\),删去之后连的边就成了一个完全图,于是......
  • P8906 [USACO22DEC] Breakdown P 题解
    P8906[USACO22DEC]BreakdownP题解显然的套路是删边转化为加边。考虑到维护整条路径不好维护,于是考虑转化维护\(f_{i,k},g_{i,k}\)分别表示\(1,n\)到\(i\)走了\(k\)步时的最短路。那么此时\(k\le4\)。我们先考虑\(f\)的转移,\(g\)的转移是等价的。那么对于\((......
  • P8907 [USACO22DEC] Making Friends P
    题目思路我们可以统计出所有点对之间应该有的边的数量然后再减去之前的\(m\)。对于每个点维护一个集合,统计该点应该连接的点。对于每条初始边,我们将其看作从编号小的点连向编号大的点,并在编号小的集合中放入编号大的点。处理删除\(i\)点操作,答案加上目前集合\(i\)的大......
  • P8901 [USACO22DEC] Circular Barn S
    原题链接题解真tm麻烦先考虑只有一个数的情况假如我是后手,由于每次可以减123,无论对手减多少,我总可以使这一轮这个数总共减去的值为四的倍数恰好当n位4的时候先手必败,所以如果一个数为四的倍数时,先手必败考虑多个数数组里,有的数是4的倍数,有的不是。此时假设我是先手,遇到四......
  • F - Breakdown
    F-BreakdownProblemStatementYouaregivenasimpleundirectedgraphconsistingof$N$verticesand$M$edges.For$i=1,2,\ldots,M$,the$i$-thedgeconnectsvertices$u_i$and$v_i$.Also,for$i=1,2,\ldots,N$,vertex$i$isassignedapos......
  • P8907 [USACO22DEC] Making Friends P 题解
    明明看着不难的题目,却意外的卡人。思路考虑两头奶牛可以成为朋友条件是什么。存在一条路径连接这两头奶牛。且除去端点外的路径上的所有点的编号小于两端点的较小值。充分必要性都比较显然。如何维护。我们可以从小到大加入点,维护这些路径。对于每个点维护一个\(\text{se......