也是补完整场了。(虽然只有一题要补
A
模拟。
B
模拟。
C
模拟。
D
模拟。
E
E - 3 Team Division
还想了蛮久的。
题意：有三个队伍，各有一些人，人有能力值，人可以换队伍。
问三个队伍能力值相同最少需要让多少人交换队伍。
人数 \(\le 100\) ，值域 \(\le 1500\)
题目还是挺误导人的，如果你从原来的队伍上考虑怎么交换，或是一些贪心那基本上很难想出来。
但是可以从每个人最终去到哪个队伍上考虑。
这样就可以 \(DP\) 了。
发现我们只需要就记录一队和二队当前的能力值，三队可以用总和减去一加二，
于是有 \(DP\) ：\(f_{i,j,k}\) 表示 考虑 \([i,n]\) ，当前一队能力值为 \(j\) ,二队为 \(k\)。
枚举 \(i\) 去哪个队即可转移。
F
问题陈述
在 AtCoder 国家，有 \(N\) 座城市，编号为 \(1\) 至 \(N\) ；有 \(M\) 条道路，编号为 \(1\) 至 \(M\) 。
道路 \(i\) 双向连接城市 \(A_i\) 和 \(B_i\) ，长度为 \(C_i\) 。
给您 \(Q\) 个查询，请按顺序处理。这些查询有以下两种类型。
1 i:道路 \(i\) 关闭。2 x y：打印从城市 \(x\) 到城市 \(y\) 的最短距离，只使用未关闭的道路。如果从城市 \(x\) 无法到达城市 \(y\) ，则打印-1。
保证每个测试用例最多包含第一种类型的 \(300\) 个查询。
特别套路的一题，思路也很一眼。
倒着做是显然的，转化为加边 \(O(n^2)\) 维护最短距离，直接枚举 \(i,j\)，然后用新加的边更新 \(f_{i,j}\) 即可。
// Problem: F - Road Blocked
// Contest: AtCoder - Panasonic Programming Contest 2024（AtCoder Beginner Contest 375）
// URL: https://atcoder.jp/contests/abc375/tasks/abc375_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// Author: Eason
// Date:2024-10-12 20:38:51
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e5+5,M = 305;
int n,m,q;
struct node
{
int op ,x,y;
}Q[200005];
struct dao
{
int x,y,c;
}edge[N];
bool fk[N];
int f[M][M];
void solve()
{
cin >> n >> m >> q;
rep(i,1,m)
{
int x= rd(),y =rd(),c= rd();edge[i] = {x,y,c};
}
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
f[i][j] = 4e18;
rep(i,1,n) f[i][i] = 0;
for (int i = 1;i <= q;i++)
{
int op = rd();
if (op == 1)
{
int x =rd();fk[x] = 1;
Q[i] = {op,x,0};
}
else
{
int x= rd(),y =rd();
Q[i] = {op,x,y};
}
}
for (int i = 1;i <= m;i++)
if (!fk[i])
{
auto [x,y,c] = edge[i];
f[x][y] = f[y][x] = min(f[x][y],c);
}
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
vector<int>ans;
for (int i = q;i >= 1;i--)
{
if (Q[i].op == 2)
{
if (f[Q[i].x][Q[i].y] < 1e18)
ans.push_back(f[Q[i].x][Q[i].y]);
else ans.push_back(-1);
}
else
{
auto[x,y,c] = edge[Q[i].x];
//f[x][y] = f[y][x] = min(f[x][y],c);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
f[i][j] = min(f[i][j],f[i][x] + f[y][j]+c),
f[i][j] = min(f[i][j],f[i][y] + f[x][j]+c);
}
}
reverse(ans.begin(),ans.end());
for (auto it : ans) cout << it << endl;
}
signed main()
{
int t;t = 1;
while(t--)
{
solve();
}
return 0;
}
ABC375G
题意：问无向图中 \(1\) 到 \(n\) 的最短路经必经边
做法
考虑一条边 \((x,y)\) 在什么情况会选入最短路径。
当且仅当 \(dis_{1,x} + dis_{y,n} + c = dis_{1,n}\) 或 \(dis_{1,y} + dis_{x,n} + c = dis_{1,n}\) 。
我们将所有这样的边拎出来，构成一个新图。
此时这个图是所有最短路径的并集。
我们对这个新图分析一下，首先必经边在这个图内，
当我们删除一条必经边，由于所有最短路径都包含必经边，
而这张图又是所有最短路径的并集，因此这时该图不联通。
所以必经边为该图上的桥。
于是做完了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e5+5;
int n,m;
int dis[N];
int disn[N];
vector<PII> v[N],v2[N];
struct node
{
int x,y,c;
}edge[N];
bool vis[N];
void dij(int st)
{
memset(dis,INF,sizeof dis);
memset(vis,0,sizeof vis);
dis[st] = 0;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,st});
while (q.size())
{
auto [d,u] = q.top();q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [j,c] : v[u])
{
if (dis[j] > dis[u] + c)
{
dis[j] = dis[u] + c;
q.push({dis[j],j});
}
}
}
}
int low[N],dfn[N],tot,fk[N];
void tarjan(int x,int idx)
{
low[x] = dfn[x] = ++tot;
for (auto [y,id] : v2[x])
{
if (!dfn[y])
{
tarjan(y,id),low[x] = min(low[x],low[y]);
if (low[y] > dfn[x]) fk[id] = 1;
}
else if (idx != id) low[x] = min(low[x],dfn[y]);
}
}
void solve()
{
cin >> n >> m;
rep(i,1,m)
{
int x= rd(),y =rd(),c = rd();
edge[i] = {x,y,c};
addev(x,y,c);addev(y,x,c);
}
dij(1);
//cout << dis[2] << endl;
memcpy(disn,dis,sizeof disn);
dij(n);
swap(dis,disn);
// rep(i,1,n) cout << dis[i] << ' ';puts("");
// rep(i,1,n) cout << disn[i] << ' ';puts("");
int tot = 0;
rep(i,1,m)
{
auto [x,y,c] = edge[i];
if (dis[x] + disn[y] + c == dis[n] || disn[x] + dis[y] + c == dis[n])
{
++tot;
// cout << x<< ' ' << y << ' ' << i << endl;
v2[x].push_back({y,i});
v2[y].push_back({x,i});
}
}
tarjan(1,-1);
for (int i = 1;i <= m;i++) if (fk[i]) puts("Yes");
else puts("No");
}
signed main()
{
int t;t = 1;
while(t--)
{
solve();
}
return 0;
}