2022 CCPC 绵阳站 E题 （图上DP，根号分治）

2022 CCPC 绵阳站 E题 （图上DP，根号分治）

题意

有一个由$n$城市组成的国家，城市之间由一条权值为$w$的边连接，共m条这样的边，并且保证整个国家是连通的。每个城市中有$a_i$ 个居民。

在接下来的q天，每天都会有一个城市遭受灾难$b_1,b_2,...,b_q$，你必须将该城市的所有人都转移到其它城市才能避免居民受到灾难，转移一个居民到相邻城市的代价为两个城市之间路径的权值w。

请问你最少需要多少代价才能让所有居民都安全度过q天的灾难。

思路

我们不必管每个城市中有多少个人，我们只需要求出每个城市中转移一个人的最小代价，在最终计算总代价时再乘上人数即可。很容易想到一个暴力的DP解法如下：

令$f(i,j)$ 表示在第$j$号点，第$i$天后所有的操作中最小的代价。那么有 f ( i , j ) = M I N ( v , w ) ∈ e d g e b i { w + f ( i + 1 , v ) } f(i,j) = MIN_{(v,w) \in edge_{b_i}}\{w+f(i+1,v)\} f(i,j)=MIN(v,w)∈edgebi​​​{w+f(i+1,v)} 。

我们发现每天只会更新一个dp值，于是我们可以直接省去f的第一维，然后倒序枚举天数 $i $ 从$q$到$1$ 。 总的时间复杂度为$O({\sum }_{i=1}^{q}deg(b_i)$ ,我们发现当$b_i$ 的度较大时，复杂度会退化到$O(qn)$ 这是不被允许的。

于是考虑根号分治，设分治边界为$SQ$ ,那么当$deg(b_i)\le SQ$ 时，枚举他的所有边来更新dp， 如果$deg(b_i)>SQ$ 那么我们为这个节点建立一个multiset ，存储所有邻边的$dp[v]+w$ 的值，则multiset的第一项即为当前最小的dp值。每当一个节点的dp值更新时，将与他相邻的$deg(v)>SQ$的点更新。

当$SQ=\sqrt{2\times m\times logn}$ 时，复杂度为$O(q\sqrt{m\times logn})$

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int a[100005];
vector<PII> edge[100005];
vector<PII> edgeB[100005];
int deg[100005];
int que[100005];
int dp[100005];
multiset<int> mulst[100005];
const int mod = 998244353;
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    int SQ = sqrt(2LL * m * log2(n));
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    for(int i = 1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,w});
        deg[v]++;deg[u]++;
    }
    for(int u = 1;u<=n;u++){
        if(deg[u] > SQ){
            for(auto [v,w] : edge[u]){
                if(deg[v] > SQ){
                    edgeB[u].push_back({v,w});
                }
                mulst[u].insert(w);
            }
        }
    }
    for(int i = 1;i<=q;i++){
        cin>>que[i];
    }
    for(int i = q;i>=1;i--){
        int u = que[i];
        if(deg[u] <= SQ){
            int cost = INF;
            for(auto [v,w] : edge[u]){
                cost = min(cost,dp[v]+w);
            }
            for(auto [v,w] : edge[u]){
                if(deg[v] > SQ){
                    mulst[v].erase(mulst[v].find(w+dp[u]));
                    mulst[v].insert(w+cost);
                }
            }
            dp[u] = cost;
        }else{
            int cost = *mulst[u].begin();
            for(auto [v,w] : edgeB[u]){
                if(deg[v] > SQ){
                    mulst[v].erase(mulst[v].find(w+dp[u]));
                    mulst[v].insert(w+cost);     
                }
            }
            dp[u] = cost;
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        ans = (ans + dp[i] * a[i]) %mod; 
    }
    cout<<ans;
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/qq_66608435/article/details/143752924

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！