自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:05:27，当前版本为作者最后更新于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;
}