题解：P11225 [COTS 2019] 疏散 Sklonište

Purslane · 2024-10-25 20:11:24 · 题解

Solution

CSP-S 2024 RP++！

非常没有趣味的缝合怪题目。

• 先预处理每个关键点到其他点的最短路。
• 二分答案，转化为二分图匹配模型。
• 左部点是原图中的点，右部点是避难所，那么对于任何一个左部点集合 S，都要求 |N(S)| \ge S，其中 N(S) 表示邻域。
• 显然枚举 S 是不靠谱的，我们枚举 T=N(S)，也就是求左部点有多少个的邻域完全包含在 T 内，可以使用高维前缀和解决。

复杂度 O((nk+k2^k) \log V)。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,MAXM=(1<<17)+10;
int n,m,k,vis[MAXN],pre[MAXM],a[20],s[20],dis[20][MAXN],sum[MAXM];
vector<pair<int,int>> G[MAXN];
struct Node {int u,dis;};
bool operator <(Node A,Node B) {return A.dis>B.dis;}
vector<int> calc(int s) {
    memset(vis,0,sizeof(vis));  
    priority_queue<Node> q;
    vector<int> ans;
    ffor(i,0,n) ans.push_back(0x3f3f3f3f3f3f3f3f);
    ans[s]=0,q.push({s,0});
    while(!q.empty()) {
        int u=q.top().u;
        q.pop();
        for(auto pr:G[u]) {
            int v=pr.first,w=pr.second;
            if(ans[u]+w<ans[v]) {
                ans[v]=ans[u]+w,q.push({v,ans[v]});
            }
        }
    }
    return ans;
}
int bel[MAXN];
int check(int w) {
    memset(bel,0,sizeof(bel)),memset(pre,0,sizeof(pre));
    ffor(i,1,k) ffor(j,1,n) if(dis[i][j]<=w) bel[j]|=(1<<i-1);
    ffor(i,1,n) pre[bel[i]]++;
    ffor(i,1,k) ffor(j,0,(1<<k)-1) if(j&(1<<(i-1))) pre[j]+=pre[j-(1<<i-1)];
    ffor(i,0,(1<<k)-1) if(pre[i]>sum[i]) return 0;
    return 1;
}
int bfind(int l,int r) {
    int ans=-1;
    while(l<=r) {
        int mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    ffor(i,1,m) {int u,v,w;cin>>u>>v>>w,G[u].push_back({v,w}),G[v].push_back({u,w});}
    ffor(i,1,k) cin>>a[i]>>s[i];
    ffor(i,1,(1<<k)-1) {ffor(j,1,k) if(i&(1<<j-1)) sum[i]+=s[j];}
    ffor(i,1,k) {
        auto vc=calc(a[i]);
        ffor(j,1,n) dis[i][j]=vc[j];
    }
    cout<<bfind(0,100000000000000);
    return 0;
}