11.6 LCA C. 冻符「Perfect Freeze」（完美冻结）

· · 题解

题意

题目

思路

不难发现，最终整张图全部点燃的时间为 \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;
}