救救孩子,思路是第一篇题解,马蜂相似,悬两关
查看原帖
救救孩子,思路是第一篇题解,马蜂相似,悬两关
800499
suzhikz楼主2024/10/17 19:12
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
#define int long long
using namespace std;
//void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=105;
int head[N],to[N<<1],w[N<<1],nex[N<<1],cnt;
int mp[N][N];
int n,m,k;
int is[N],in[N],ins[N],co;//是不是城堡,在环上的点
ll summ[2*N]; 
int vis[N];
int tmp1[N],pre[N];
void add(int u,int v,int ww){
//	cout<<u<<' '<<v<<' '<<ww<<endl;
	cnt++;nex[cnt]=head[u];to[cnt]=v;w[cnt]=ww;head[u]=cnt;
}
void dfs1(int x,int fa){
//	cout<<x<<endl;
	vis[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)continue;
		if(vis[to[i]])continue; 
		dfs1(to[i],x);
	}
}
bool dfs2(int x,int fa){
//	cout<<x<<' '<<vis[x]<<endl;
	bool c=0;
	vis[x]=2;
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
//		cout<<vis[y]<<endl; 
		if(y==fa){
			if(!c){
				c=1;continue;
			}
//			cout<<x<<endl<<fa<<endl;
			in[x]=1;in[fa]=1;
			ins[++co]=x;ins[++co]=fa;return 1;
		}
		if(vis[y]==1){
			pre[y]=x;
			if(dfs2(y,x))return 1;
		}else{
			int j=x;
			pre[y]=x;
			do{
//				cout<<j<<endl;
				ins[++co]=j;
				in[j]=1;
				j=pre[j];
			}while(j!=x);
			return 1;
		}
	}
	return 0;
}
int fr;
void pppp(){
	for(int i=1;i<=co;i++)ins[co+i]=ins[i];
	for(int i=1;i<=co*2;i++){
//		cout<<ins[i]<<' ';
		summ[i+1]=summ[i]+mp[ins[i]][ins[i+1]];
//		cout<<summ[i]<<endl;
	}
}
int l,mid,r,ans,hhh,minnnnn;
struct node{
	int ql,qr;
}z[N*2];
bool cmp(node a,node b){
	return a.qr<b.qr;
}
void add(int l,int r){
//	cout<<l<<' '<<r<<endl;
	hhh++;
	z[hhh].ql=l;z[hhh].qr=r;
}
int qt,minn[N],maxx[N];//最近的城堡,最远的未被覆盖的点 
void dfs(int x,int fa){
	minn[x]=998244353,maxx[x]=0;
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(in[y])continue;
		if(y==fa)continue;
		dfs(y,x);
		minn[x]=min(minn[x],minn[y]+w[i]);
		maxx[x]=max(maxx[x],maxx[y]+w[i]);
	}
	if(is[x]){
		minn[x]=0;
	}
	if(minn[x]+maxx[x]<=mid){
		maxx[x]=-998244353;
	}
	if(maxx[x]+mp[x][fa]>mid){
//		cout<<maxx[x]<<' '<<mp[x][fa]<<"abcd"<<endl;
		minn[x]=0;maxx[x]=-1;
//		cout<<114514;
//cout<<x<<endl;
		ans++;
	}
}
int st;
void solve(){
//	cout<<endl;
	//st~st+co-1 
//	cout<<mid<<endl;
	hhh=0;
	for(int i=st;i<=st+co-1;i++){
		dfs(ins[i],0);
	}
	for(int i=st;i<=st+co-1;i++){
		int al=i,ar=i;
		if(maxx[ins[i]]!=-998244353){
			int fg=0;
			while(al>=st&&summ[i]-summ[al]<=mid-maxx[ins[i]]){
				if(is[ins[al]]||minn[ins[al]]+summ[i]-summ[al]+maxx[ins[i]]<=mid){
					fg=1;
				}
				al--;
			}
			al++;
			while(ar<=st+co-1&&summ[ar]-summ[i]<=mid-maxx[ins[i]]){
				if(is[ins[ar]]||minn[ins[ar]]+summ[ar]-summ[i]+maxx[ins[i]]<=mid)fg=1;ar++;
			}
			ar--;
			if(!fg)
			add(al,ar);
		}
	}
	sort(z+1,z+1+hhh,cmp);
	int r=0; 
	for(int i=1;i<=hhh;i++){
		if(r<z[i].ql){
			r=z[i].qr;
			ans++;
		}
	}
}
signed main(){
	minnnnn=998244353;
	memset(mp,0x3f,sizeof(mp));
	read(n);read(m);read(k);
	for(int i=1;i<=n;i++){
		read(tmp1[i]);tmp1[i]++;
	}
	for(int i=1;i<=n;i++){
		mp[i][i]=0;
		mp[i][0]=0;
		read(tmp1[0]);add(i,tmp1[i],tmp1[0]);add(tmp1[i],i,tmp1[0]);
		mp[i][tmp1[i]]=mp[tmp1[i]][i]=min(mp[tmp1[i]][i],tmp1[0]);
	}
	for(int u,i=1;i<=m;i++){
		read(u);is[u+1]=1;
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		dfs1(i,0);
		dfs2(i,0);
	}
	pppp();
	l=0,r=500000000;
	while(l<=r){
//		cout<<l<<' '<<r<<endl; 
		mid=(l+r)/2;
		ans=0;
		int cm=998244353;
		for(int i=1;i<=co;i++){
			st=i;
			ans=0;
			solve();
			cm=min(ans,cm);
		}
//		cout<<mid<<' '<<cm<<endl;
		if(cm>k){
			l=mid+1;
		}else{
			r=mid-1;minnnnn=mid;
		}
	}
	cout<<minnnnn;
	return 0;
}

2024/10/17 19:12
加载中...