S08577 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-19 21:45:32
$(y-1)^2+(x-3+y)^2+(2x+y-6)^2$
令 $t=x-3$ 得，原式为 $(y-1)^2+(t+y)^2+(2t+y)^2$
展开得 $y^2-2y+1+t^2+2ty+y^2+4t^2+4ty+y^2$
即 $3y^2-2y+6ty+5t^2+1$
令 $f(x)=3y^2-2y+6ty+5t^2+1$
列出其对 $y$ 的偏导方程得
$$f'(x)=6y-2+6t $$
列出其对 $t$ 的偏导方程得
$$f'(x)=6y+10t$$
依题意，$f(x)$ 要取得最小值，即 $f'(x)=0$
将上方二式联立 $$f'(x)=6y-2+6t $$ $$f'(x)=6y+10t$$
解得 $y= \frac{5}{6}$ ，$t=-\frac{1}{2}$
即 $x=2.5$
带回原式得，最小值为 $\frac{1}{6}$
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-12 11:11:45
给定一个有向图，再给定 $k$ 个重要点，$q$ 次询问，每次询问包含 $u,v$，询问从 $u$ 点到 $v$ 点必须经过重要点的最短路径，请输出 $q$ 次询问的最短路径长度之和。
显然，一开始的想法是dij，发现2e4*2e4开不下，不难发现 $k \leq 200$ 于是我们可以利用离散化的思想，把 $k$ 个重要点编号就做完了。
void dij1(int s,int st){
priority_queue<node> q;
for(int i=0;i<=N-10;i++){
dis1[i][st]=Max;
}
dis1[s][st]=0;
q.push({s,0});
while(!q.empty()){
node t=q.top();
q.pop();
int u=t.p;
if(vis[u]) continue;
for(int i=0;i<ve[u].size();i++){
int v=ve[u][i].fi,w=ve[u][i].se;
if(dis1[v][st]>dis1[u][st]+w){
dis1[v][st]=dis1[u][st]+w;
q.push({v,dis1[v][st]});
}
}
}
}
void dij2(int s,int st){
priority_queue<node> q;
for(int i=0;i<=N-10;i++){
dis2[i][st]=Max;
}
dis2[s][st]=0;
q.push({s,0});
while(!q.empty()){
node t=q.top();
q.pop();
int u=t.p;
if(vis[u]) continue;
for(int i=0;i<ve[u].size();i++){
int v=ve[u][i].fi,w=ve[u][i].se;
if(dis2[v][st]>dis2[u][st]+w){
dis2[v][st]=dis2[u][st]+w;
q.push({v,dis2[v][st]});
}
}
}
}
signed main(){
\/\/ freopen("a.in","r",stdin);
\/\/ freopen("a.out","w",stdout);
cin>>n>>m>>k>>q;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i]>>w[i];
}
for(int i=1;i<=k;i++){
cin>>a[i];
mp[a[i]]=i;
}
for(int i=1;i<=m;i++){
ve[u[i]].push_back({v[i],w[i]});
}
for(int i=1;i<=k;i++){
dij1(a[i],mp[a[i]]);
}
for(int i=1;i<=n;i++){
ve[i].clear();
}
for(int i=1;i<=m;i++){
ve[v[i]].push_back({u[i],w[i]});
}
memset(vis,0,sizeof vis);
for(int i=1;i<=k;i++){
dij2(a[i],mp[a[i]]);
}
int sum=0,cnt=0;
while(q--){
int l,r;
cin>>l>>r;
int minn=Max;
if(mp[l]){
minn=min(minn,dis1[r][mp[l]]);
}
if(mp[r]){
minn=min(minn,dis2[l][mp[r]]);
}
if(minn==Max){
for(int i=1;i<=k;i++){
minn=min(minn,dis1[r][i]+dis2[l][i]);
}
}
if(minn==Max) continue;
cnt++;
sum+=minn;
}
cout<<cnt<<endl;
cout<<sum<<endl;
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-14 17:04:49
A是B中k=2的特殊情况。
设 $f_i$ 表示跳到第 $i$ 个台阶的最小代价。
首先，在第 $i$ 个台阶我们可以从 $i-1,i-2,....,i-k$ 转移过来。
不难列出转移方程
$$f_i=\min_{j=\max(1,i-k)}^{i} f_j+|h_i-h_j|$$
$dp_1=0$
不难想到状态，设 $f_{i,1/2/3}$ 表示第 $i$ 天选择第 $1/2/3$ 种活动可获得的最大总幸福度。
很好转移。
$$f_{i,1}=a_i+\max(f_{i-1,2},f_{i-1,3})$$ $$f_{i,2}=b_i+\max(f_{i-1,1},f_{i-1,3})$$ $$f_{i,3}=c_i+\max(f_{i-1,2},f_{i-1,1})$$
答案即为 $\max(f_{n,1/2/3})$
简单背包
设 $f_i$ 表示背包容量为 $i$ 的时候最大价值。
转移 $$f_j=\max(f_j,f_{j-w_i}+v_i)$$
输出 $f_m$ 即可。
最大范围为 $10^9$，D的状态不再适合此题。
可以将价值和重量交换
设 $f_i$ 表示取价值为 $i$ 的物品的最小重量。
不难转移 $$f_j=\max(f_j,f_{j-v_i}+w_i)$$
答案只需要统计最大的价值使得其重量符合题目要求即可。
最长公共子序列。
设 $f_{i,j}$ 为 $s$ 的前 $i$ 项与 $t$ 的前 $j$ 项的LCS长度。
若 $s_i=t_j$，则 $f_{i,j}=f_{i-1,j-1}+1$
否则，则 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1})$
输出 $f_{s.size(),t.size()}$
给定一个dag，求最长路。
$f_i$ 表示遍历到第 $i$ 个点的最长路。
若有一条边 $j \to i$，那么 $f_i=\max(f_i,f_j+1)$
dfs即可。
设 $f_{i,j}$ 表示走到 $(i,j)$ 这个点。
类似金字塔转移即可。
设 $f_{i,j}$ 表示到第 $i$ 个硬币有 $j$ 个向上的概率。
不难转移 $$f_{i,j}=f_{i-1,j-1} \times p_i +f_{i-1,j} \times (1-p_i)$$
输出 $\sum_{j>n-j} f_{n,j}$ 即可。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-16 08:27:11
好题。
从kruscal的本质出发，我们是贪心连权值最小的边，如果出现环那么这条边就不连。
这道题也是类似，贪心考虑，不出现环的情况下，肯定是把一行或者一列全部连起来，代价是 $w*(n-1)$
但是如果出现环怎么办，考虑什么时候会出现环，当我们连的行数和列数都大于等于2时，会出现环。因为我们贪心连边，所以删边肯定是删当前边而不是前面的边。
考虑会删几条边，肯定是连了这一列或一行多出现的环，以连了一列为例，那么多出的环肯定是 连的行数 减一。因为考虑我们连的第一条行与第一条列是不被删除的，所以我们只要再连就肯定会出现新环。
所以少的代价就是 $(y-1) \times a[i].x$。
行同理。
struct node{
int x;
int id;
}a[N];
bool cmp(node a,node b){
return a.x<b.x;
}
signed main(){
\/\/ freopen("a.in","r",stdin);
\/\/ freopen("a.out","w",stdout);
fst
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i].x;
a[i].id=1;
}
for(int i=n+1;i<=n+m;i++) {
cin>>a[i].x;
a[i].id=2;
}
sort(a+1,a+1+n+m,cmp);
int x=0,y=0;
int res=0;
for(int i=1;i<=n+m;i++){
if(a[i].id==1){
res+=a[i].x*(m-1);
if(x<n) x++;
else x=n;
if(x>=2&&y>=2) res-=(y-1)*a[i].x;
}
if(a[i].id==2){
res+=a[i].x*(n-1);
if(y<m) y++;
else y=n;
if(x>=2&&y>=2) res-=(x-1)*a[i].x;
}
}
cout<<res<<endl;
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-16 19:07:48
分层图。
考虑建分层图，因为题目只说加2条边，所以我们可以建3个图，我们加边时，可以将第一层图的点u连到下一层图的点v上，因为只用加两条边，所以我们建三层图完全够用。
注意这里要建单向边，因为你不能从下面的图走到上面。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
const int N=2e5+10;\/\/注意修改
const int mod=1e9+7;
const int Max=0x3f3f3f3f3f3f3f;
vector<pii> ve[N*3];
int n,m;
struct node{
int a,b,c,d;
}a[N];
int vis[30005];
int dis[30005];
struct id{
int p,d;
bool operator < (const id &b)const{
return d>b.d;
}
};
void dij(int s){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
dis[s]=0;
priority_queue<id> q;
q.push({s,0});
while(!q.empty()){
int u=q.top().p;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto v:ve[u]){
if(dis[v.fi]>dis[u]+v.se){
dis[v.fi]=dis[u]+v.se;
q.push({v.fi,dis[v.fi]});
}
}
}
}
signed main(){
\/\/ freopen("a.in","r",stdin);
\/\/ freopen("a.out","w",stdout);
fst
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i].a>>a[i].b>>a[i].c>>a[i].d;
if(a[i].d==0){
ve[a[i].a].push_back({a[i].b,a[i].c});
ve[a[i].b].push_back({a[i].a,a[i].c});
}
}
dij(1);
\/\/ for(int i=1;i<=n;i++){
\/\/ cout<<dis[i]<<' ';
\/\/ }
\/\/ cout<<endl;
int dis1=dis[n];
for(int i=1;i<=n;i++) ve[i].clear();
for(int i=1;i<=m;i++){
if(a[i].d==1){
for(int j=0;j<=1;j++){
ve[a[i].a+j*n].push_back({a[i].b+(j+1)*n,a[i].c});
\/\/ve[a[i].b+(j)*n].push_back({a[i].a+(j+1)*n,a[i].c});
}
}else{
for(int j=0;j<=2;j++){
ve[a[i].a+j*n].push_back({a[i].b+j*n,a[i].c});
ve[a[i].b+j*n].push_back({a[i].a+j*n,a[i].c});
}
}
}
dij(1);
int dis2=min({dis[n],dis[2*n],dis[3*n]});
cout<<dis1-dis2;
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-21 08:43:13
观察可得，汉语操作实质上是在 N 后面插入 V，英语操作为在 N 前面或后面插入 V。所以，汉语和英语都不合法的情况只有有两个连续的 N 或者字符串全为 V。汉语还有一种不合法的情况是第一个字符为 V。
void solve(){
string s;
cin>>s;
int a=1,b=1;
if(s[0]=='V'){
b=0;
}
int ff=0;
for(int i=0;i<s.size();i++){
if(s[i]=='N') ff=1;
}
if(!ff){
cout<<"0 0\n";
return ;
}
for(int i=0;i<s.size()-1;i++){
if(s[i]=='N'&&s[i+1]=='N'){
a=b=0;
break;
}
}
cout<<a<<' '<<b<<endl;
}
考虑dp，设 $dp_{i,j}$ 为走到 $(i,j)$ 的最小翻转次数。
我们考虑什么时候会产生贡献，不难发现，如果我们走的这一步是从0走到1，必须翻转一次矩阵使得能走。
所以dp转移方程为：
$$dp_{i,j}=\min(dp_{i-1,j}+[a_{i-1,j}=0 \land a_{i,j}=1],dp_{i,j-1}+[a_{i,j-1}=0 \land a_{i,j}=1] )$$
最后输出 $dp_{n,m}$ 即可。
但是，题目中有个条件，是翻转面积大于1的矩形，那么我们需要特判所有 $n=1$ 的情况。
void solve(){
memset(dp,0x3f,sizeof dp);
cin>>n>>m;
int f=0;
int cnt0=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) {
cin>>a[i][j];
if(a[i][j]==1) cnt0++;
}
}
if((n==1&&m==1&&a[1][1]==1)||(n==1&&m==2&&cnt0==1)||(m==1&&n==2&&cnt0==1)){
cout<<"Impossible\n";
return ;
}
if(n==1){
if(m>=3){
if(cnt0==1){
cout<<2<<endl;
return ;
}
}
}
if(m==1){
if(n>=3){
if(cnt0==1){
cout<<2<<endl;
return ;
}
}
}
dp[0][1]=dp[1][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=min(dp[i][j],dp[i-1][j]+(!a[i-1][j]&&a[i][j]));
dp[i][j]=min(dp[i][j],dp[i][j-1]+(!a[i][j-1]&&a[i][j]));
}
}
cout<<dp[n][m]<<endl;
}
这道题的代码还没有写。
不妨我们首先考虑对操作次数分讨。
如果不进行操作，那么答案就是树的直径。
如果进行一次操作，考虑删掉根节点与其儿子的一条边，然后再连，观察特殊性质可得，进行一次的答案即为根节点子树中的最大直径与从根节点到最低端的一个最长链。
如果进行两次操作，即把两个直径改成了链，所以我们找出两个子树最长直径即可。
还有一种情况是两个直径在一个子树内。
树形dp解决即可。
只会 $h=1$ 的情况。
由于题目中说明了输入的图的黑色联通块一定为四联通，所以只有两种情况，一种为全是黑点，另一种为其他情况。
全是黑点很好考虑，无论几级分型都只有一个联通块。
其他情况，设输入的图中有 $c$ 个黑点，求 $k$ 级分型，那么答案即为 $c^{k-1}$。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-21 18:55:16
经过 @Dtw_ 和 @cybrex 的讲解之后，印象十分深刻，很多题解没有写清楚。
由于 $n \leq 2 \times 10^5$，dp状态肯定只能设一维，不妨从最简单的状态开始考虑，我们设 $f_i$ 为考虑前 $i$ 个元素的得分最大值。
首先考虑朴素dp，考虑从 $j$ 转移，便于理解，这里钦定从 $j$ 转移是合法的（其实就是一个条件，$a_i=a_j$）。
说明：红色和绿色各是一种颜色，蓝色为不确定的涂色。
这里，有一个很显然的转移：
$$f_i=f_j+val(j+1,i-1)$$
$val(x,y)$ 表示令 $[x,y]$ 是一个同色区间，其贡献是多少。
这里我们可以用前缀和来优化。令 $sum_i$ 表示区间 $[1,i]$ 的贡献，则 $sum_i=sum_{i-1}+a_i \times [a_i=a_{i-1}]$。
这样方程就优化到了 $O(n^2)$ 的复杂度，可以通过50分。
但是，不幸的告诉你，转移方程出现了一点错误。
如果上图中的蓝色为绿色，那么 $j+1$ 这个点会对 $j-1$ 这个点产生贡献，贡献不能简单的用 $val$ 来计算，因为如果用 $val$ 计算，$j+1$ 的代价一定为0（因为一定 $a_{j+1}\ne a_j$）。所以，转移方程不妨这么写：
$$f_i=a_i+val(j+2,i-1)+f_{j+1}=a_i+sum_{i-1}-sum_{j+1}+f_{j+1}$$
这是正确的转移方程。
考虑将 $O(n^2)$ 优化为 $O(n)$。
这里需要发现一个小性质，$i$ 只会从 最近的 使得 $a_i=a_j$ 的 $j$ 转移过来。
绿色的是只能填同色，而红色是随意填。
不难发现，上面的是从 $k$ 转移，下面的是从 $j$ 转移 （这里钦定从 $i$，$j$，$k$ 转移都是合法的转移）。
观察可得，区间 $[i,j]$ 的贡献一样，下面浅红色区间 $[1,k)$ 的贡献一定不劣于上面深红色区间 $[1,k)$ 的。而下面浅红色区间 $(k,j)$ 显然不劣于上面的绿色区间 $(k,j)$。
（可以这么考虑，同色的贡献只有相邻两个 $a_i$ 相同的情况，而随便填的贡献一定不比同色少）。
性质成立，所以不需要枚举 $j$，只需要记录上一个与 $a_i$ 相同的 $j$ 的位置，记为 $lst_{a_i}$。
最终的转移方程即为：
$$f_i=a_i+sum_{i-1}-sum_{lst_{a_i}+1}+f_{lst_{a_i}+1}$$
这里有个小细节 如果 $lst_{a_i}=i-1$，那么前缀和就祭了。处理也很好处理，下标与 $i-1$ 取最小值即可。
最后最后的转移方程为：
$$f_i=a_i+sum_{i-1}-sum_{\min(i-1,lst_{a_i}+1)}+f_{lst_{a_i}+1}$$
void solve(){
memset(f,0,sizeof f); memset(lst,0,sizeof lst);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++)
if(a[i]==a[i-1]) sum[i]=sum[i-1]+a[i];
else sum[i]=sum[i-1];
for(int i=1;i<=n;i++){
f[i]=f[i-1];
if(lst[a[i]]) f[i]=max(f[i],a[i]+f[lst[a[i]]+1]+(sum[i-1]-sum[min(i-1,lst[a[i]]+1)]));
lst[a[i]]=i;
}
cout<<f[n]<<endl;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-04 17:14:19
个人认为细节很多，且不好想出来。
给定每个矩形的宽度和高度，求里面有多少个子矩形。
不妨考虑用单调栈维护（这里很难考虑到），最后我们处理单调递增的矩形肯定是好处理的，这里最后再说。
我们设栈顶的矩形高度为 $h1$，要加入的矩形的高度为 $h2$，栈顶下面的矩形高度为 $h3$，当 $h1 \leq h2$ 时，显然直接加入即可，否则，我们将 $h1$ 削到 $\max(h2,h3)$ 的高度，计算被削掉矩形的贡献即可。
现在，我们主要的问题就是计算被削掉矩形的贡献。考虑贡献即为只有 4个点都在削掉的矩形里面 或者 只有2个点在削掉的矩形里面的矩形个数。
这个如何计算呢，不妨考虑容斥，只需要将整个矩形里面的子矩形个数减去被删去的矩形中子矩形的个数。
不难发现，高度为 $h$，宽度为 $w$ 的矩形中子矩形的个数为 $\frac{h\times (h+1)}{2} \times \frac{w\times (w+1)}{2}$ 个。
最后，我们还要加入一个高度为0的矩形，目的是为了将单调栈清空。
步骤见下图：
int f(int x){
return (x*(x+1)\/2)%mod;
}
signed main(){
\/\/ freopen("a.in","r",stdin);
\/\/ freopen("a.out","w",stdout);
fst
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++) cin>>w[i];
int ans=0;
st.push(0);
for(int i=1;i<=n+1;i++){
int d=st.top();
int sum=0;
while(h[i]<h[st.top()]){
d=st.top();
st.pop();
(sum+=w[d])%=mod;
(ans+=(f(h[d])-f(max(h[st.top()],h[i]))+mod%mod)*f(sum)%mod)%=mod;
}
(w[i]+=sum)%=mod;
st.push(i);
}
cout<<(ans+mod)%mod;
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-05 14:35:57
题意很简单，求一个图中有多少最小生成树。
试着发现一些性质，对于同一个图的两颗最小生成树，这两颗树的每种边权的边数是一样的。
证明一下，考虑kruskal的过程：将所有边按照边权从小到大排序，一条一条加，如果出现环就不加。直到所有点都在一个联通块内。
如果出现环就不加这一步，也可以是如果出现环，将环上最大边权的边随机选一条边删去。所以，每种边权的边数是一样的。
注意题目中的这条要求，具有相同权值的边不会超过 10 条。 也就是说，可以暴力 $2^k$ 枚举我们加入哪些边，使得加入那些边之后最小生成树仍然合法。
合法的条件是什么？根据上面的性质，每一种边权的边数应相同，所以可以一开始跑一遍最小生成树，把每个边权在其中的出现次数预处理出来。并且加入那些边之后最小生成树不能出现环。
然后就做完了。
#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
const int N=2e6+10;\/\/注意修改
const int mod=31011;
const int Max=0x3f3f3f3f3f;
int n,m;
struct edge{int u,v,w;}e[N];
bool cmp(edge a,edge b){return a.w<b.w;}
map<int,int> c;\/\/每个边权在最小生成树中的出现个数
int fa[N],faa[N];
int findf(int x){return x==fa[x]?x:fa[x]=findf(fa[x]);}
int findff(int x){return x==faa[x]?x:faa[x]=findff(faa[x]);}
struct col{int l,r,w;}a[N];\/\/每个边权的出现区间
bool check(int x,int p){
int cnt=0;
while(x){
if(x&1) cnt++;
x>>=1;
}
return cnt!=p;
}
signed main(){
\/\/ freopen("a.in","r",stdin);
\/\/ freopen("a.out","w",stdout);
fst
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e[i]={u,v,w};
}
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m,cmp);
int tot=0;
for(int i=1;i<=m;i++){
int u=findf(e[i].u),v=findf(e[i].v);
if(u==v) continue;
fa[v]=u;
tot++;
c[e[i].w]++;
}
if(tot!=n-1){
cout<<0;
return 0;
}
int cnt=0;
for(int i=1;i<=m;i++){
if(e[i].w!=e[i-1].w){
a[cnt].r=i-1;
a[++cnt].l=i;
a[cnt].w=e[i].w;
}
}
for(int i=1;i<=n;i++) fa[i]=faa[i]=i;
a[cnt].r=m;
int ans=1,sum=0;
for(int i=1;i<=cnt;i++){
sum=0;
for(int k=0;k<(1<<(a[i].r-a[i].l+1));k++){
if(check(k,c[a[i].w])) continue;
\/\/cout<<k<<' ';
for(int i=1;i<=n;i++) fa[i]=faa[i];
int f=0;
for(int j=a[i].l;j<=a[i].r;j++){
int d=j-a[i].l;
if((k>>d)&1){
int u=findf(e[j].u),v=findf(e[j].v);
if(u==v) f=1;
fa[v]=u;
}
}
if(!f) sum++;
}
if(sum!=0) ans=(ans*sum)%mod;
sum=0;
for(int j=a[i].l;j<=a[i].r;j++){
int u=findff(e[j].u),v=findff(e[j].v);
if(u==v) continue;
faa[v]=u;
}
}
cout<<ans;
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-06 19:35:20
不难发现，最终整张图全部点燃的时间为 $\max(\min dis_i)$。其中，$dis_i$ 表示点 $i$ 到最近着火点的距离。
设 $T$ 为初始状态整张图全部点燃的时间。
不难发现，对于任意一个非着火点，如果其到一个着火点的距离小于等于 $T$，那么加入这个着火点一定是合法的。
设集合 $S$ 为合法的着火点，那么 $S$ 里的点，只要任选一个就合法。
发现这么直接操作是非常困难的，不妨考虑 $S$ 的补集 $S'$，对于 $S'$，其子集都不合法。
然后就做完了。
#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=2e5+10;
const int Max=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
struct node{
int p,d;
bool operator< (const node &b) const{
return d>b.d;
}
};
int n,m,s;
vector <pii> ve[N];
int d[41][N],vis[N],k,a[N];
void dij(int s,int k){
memset(vis,0,sizeof vis);
d[k][s]=0;
priority_queue<node > q;
q.push({s,0});
while(!q.empty()){
int u=q.top().p;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int j=0;j<ve[u].size();j++){
pii e=ve[u][j];
int v=e.fi,w=e.se;
if(d[k][v]>d[k][u]+w){
d[k][v]=d[k][u]+w;
q.push({v,d[k][v]});
}
}
}
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res%mod;
}
int dis[N];
\/*
*\/
int f[N*10];
signed main(){
freopen("flame.in","r",stdin);
freopen("flame.out","w",stdout);
cin>>n>>m>>k;
memset(d,0x3f,sizeof d);
memset(dis,0x3f,sizeof dis);
for(int i=1;i<=k;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
ve[u].push_back(make_pair(v,w));
ve[v].push_back({u,w});
}
for(int i=1;i<=k;i++) dij(a[i],i);
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
dis[i]=min(dis[i],d[j][i]);
\/\/cout<<d[j][i]<<' ';
}
\/\/ cout<<dis[i]<<' ';
}
\/\/ cout<<endl;
int maxx=0;
for(int i=1;i<=n;i++) maxx=max(maxx,dis[i]);
int tot=(1<<k)-1;
for(int i=1;i<=n;i++){
int S=0;
for(int j=1;j<=k;j++){
if(d[j][i]<=maxx) S|=(1<<(j-1));
}
f[tot^S]=1;
}
for(int i=tot;i>=0;i--){
for(int j=k-1;j>=0;j--){
if((i>>j)&1){
int t=i^(1<<j);
f[t]|=f[i];
}
}
}
int cnt=0;
for(int i=0;i<=tot;i++) if(!f[i]) cnt++;
cout<<cnt*ksm(tot+1,mod-2)%mod;
return 0;
}
鲁ICP备2025150228号