一、题解

第 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;
}