(AtCoder Beginner Contest 375) 题解（下）

一、题解

第 E 题 3 Team Division

一眼看像背包，观察数据范围，合法的总能力值 $\le 500$，那么我们可以设计一个背包DP：

int dp[110][510][510];
//dp[i][j][k] 表示前 i 个人，分给第一组的能力值是 j，第二组是 j最小换人次数。

那么可得转移：

dp[i][j][k]=min(dp[i-1][j-b[i]][k]+1-(a[i]==1));
dp[i][j][k]=min(dp[i-1][j][k-b[i]]+1-(a[i]==2));
dp[i][j][k]=min(dp[i-1][j][k]+1-(a[i]==3));

那么接下来就很简单了：

#include <bits/stdc++.h>
using namespace std;
int dp[110][510][510],a[510],b[510];
signed main(){
    memset(dp,0x3f,sizeof(dp));
    int n,sum=0; cin>>n; dp[0][0][0]=0;
    for (int i=1; i<=n; i++){
        cin>>a[i]>>b[i]; sum+=b[i];
    }if (sum%3!=0){
        cout<<-1; return 0;
    }for (int i=1; i<=n; i++){
        for (int j=0; j<=sum/3; j++){
            for (int k=0; k<=sum/3; k++){
                if (j>=b[i]) dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-b[i]][k]+1-(a[i]==1));
                if (k>=b[i]) dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-b[i]]+1-(a[i]==2));
                dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+1-(a[i]==3));
            }
        }
    }cout<<(dp[n][sum/3][sum/3]>1e8?-1:dp[n][sum/3][sum/3]);
    return 0;
}

第 F 题 Road Blocked

我们发现，我们删除条边跑最短路是 $O(n^3)$ 的，但是我们加入一条边，影响的最短路
需要经过这条边，通过优化可降至 $O(n^2)$。
$newdi{s}_{i,j}=min(di{s}_{i,j},di{s}_{i,u}+di{s}_{v,j}+w,di{s}_{i,v}+disu,j+w)$。

利用这个公式，我们可以处理加边最短路了！

接下来我们可以倒序处理询问即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Q 200010
int dis[310][310],ans[Q];
int type[Q],x[Q],y[Q];
int u[Q],v[Q],w[Q];
signed main(){
    set <int> st;
    memset(dis,0x3f,sizeof(dis));
    int n,m,q; cin>>n>>m>>q;
    for (int i=1; i<=n; i++) dis[i][i]=0;
    for (int i=1; i<=m; i++){
        cin>>u[i]>>v[i]>>w[i];
    }for (int i=1; i<=q; i++){
        cin>>type[i]>>x[i];
        if (type[i]==2) cin>>y[i];
        else st.insert(x[i]);
    }for (int i=1; i<=m; i++){
        if (!st.count(i)){
            dis[u[i]][v[i]]=w[i];
            dis[v[i]][u[i]]=w[i];
        }
    }for (int k=1; k<=n; k++){
        for (int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }for (int i=q; i>=1; i--){
        if (type[i]==1){
            int U=u[x[i]],V=v[x[i]],W=w[x[i]];
            for (int a=1; a<=n; a++){
                for (int b=1; b<=n; b++){
                    dis[a][b]=min({dis[a][b],dis[a][U]+dis[V][b]+W,dis[a][V]+dis[U][b]+W});
                }
            }ans[i]=-2;
        }else ans[i]=(dis[x[i]][y[i]]>1e15?-1:dis[x[i]][y[i]]);
    }for (int i=1; i<=q; i++) if (ans[i]!=-2) cout<<ans[i]<<"\n";
    return 0;
}

第 G 题 Road Blocked 2

题意是给你一个图，问固定一条边，最短路十分变化。

我们固定边的公式与加边相同，详见 F 题。

注意到，变化 只会变大，下面我们仔细考虑变大的条件：

• 固定边最短路和最短路相同。
• 固定边最短路数量和最短路数量相同。

最短路数量可以在 Dijkstra 中记录。

现在考虑一个问题，最短路数量可能达到 $2^{\frac{n}{3}}$，其实我们将数量对 $998244353$ 取膜即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200010
#define M 998244353
vector <pair<int,int>> vc[N];
int cnt[N][2],vis[N][2],dis[N][2],n,u[N],v[N],w[N];
void dijkstra(int op){
    priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({0,(op?n:1)}); dis[(op?n:1)][op]=0; cnt[(op?n:1)][op]=1;
    while (!q.empty()){
        int id=q.top().second; q.pop();
        if (vis[id][op]) continue; vis[id][op]=1;
        for (auto x:vc[id]){
            int u=x.first,w=x.second;
            if (dis[id][op]+w<dis[u][op]){
                dis[u][op]=dis[id][op]+w;
                cnt[u][op]=cnt[id][op];
                q.push({dis[u][op],u});
            }else if (dis[id][op]+w==dis[u][op]){
                cnt[u][op]+=cnt[id][op];
                cnt[u][op]%=M;
            }
        }
    }
}signed main(){
    memset(dis,0x3f,sizeof(dis));
    int m,hs1,hs2; cin>>n>>m;
    for (int i=1; i<=m; i++){
        cin>>u[i]>>v[i]>>w[i];
        vc[u[i]].push_back({v[i],w[i]});
        vc[v[i]].push_back({u[i],w[i]});
    }dijkstra(0); dijkstra(1);
    for (int i=1; i<=m; i++){
        hs1=cnt[n][0];
        int x=dis[u[i]][0]+dis[v[i]][1]+w[i];
        int y=dis[v[i]][0]+dis[u[i]][1]+w[i];
        if (x<y) hs2=cnt[u[i]][0]*cnt[v[i]][1]%M;
        else if (x>y) hs2=cnt[v[i]][0]*cnt[u[i]][1]%M;
        else hs2=cnt[u[i]][0]*cnt[v[i]][1]%M+cnt[v[i]][0]*cnt[u[i]][1]%M;
        if (hs1%M==hs2%M&&min(x,y)==dis[n][0]) cout<<"Yes\n";
        else cout<<"No\n";
    }return 0;
}