96分模拟退火求助
查看原帖
96分模拟退火求助
481851
Withers楼主2022/9/1 23:25
#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define Withers using
#define AK namespace
#define IOI std;
//#define ACM __gnu_pbds 
Withers AK IOI;
//Withers AK ACM;
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
int n,m,u,v,w,x,y,z,l,r,minn=INT_MAX,maxx=INT_MIN,k;
int tst;
int a[200010];
char s[200010];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
char t[200010];
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define endl '\n'
static char buf[1<<18],*paa=buf,*pddd=buf;
static char buf2[1<<18],*pppp=buf2;
#define getchar() paa==pddd&&(pddd=(paa=buf)+fread(buf,1,1<<18,stdin),paa==pddd)?EOF:*paa++
inline void pc(char ch){
	if(pppp-buf2==1<<18) fwrite(buf2,1,1<<18,stdout),pppp=buf2;
	*pppp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pppp-buf2,stdout);
	pppp=buf2;
}
inline void rd(int &n){
	int w=1;
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	n=w*x;return;
}
inline void write(int x){
	if(x<0) pc('-'),x=-x;
	static int sta[20];int top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while(top) pc(sta[--top]+48);
}
inline void we(int x){
	write(x);
	pc('\n');
}
inline void ws(int x){
	write(x);
	pc(' ');
}
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
#define deb(x) cout<<#x<<"="<<x<<" ";
#define pb push_back
#define fi first
#define se second
#define mx3(a,b,c) ((a>b?a:b)>c?(a>b?a:b):c)
#define mn3(a,b,c) ((a<b?a:b)<c?(a<b?a:b):c)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
int get(char s[])
{
	char ch='=';
	int cnt=0;
	int len=strlen(s+1);
	for(int i=1;i<=len;i++) s[i]=0;
	while(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'))) ch=getchar();
	while((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9')) s[++cnt]=ch,ch=getchar();
	return cnt;
}
void put(char s[])
{
	int len=strlen(s+1);
	for(int i=1;i<=len;i++) pc(s[i]);
}
void get(string &s)
{
	s="";
	char ch='=';
	while(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'))) ch=getchar();
	while((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9')) s.push_back(ch),ch=getchar();
	return;
}
void put(string s)
{
	int len=s.size();
	for(int i=0;i<len;i++) pc(s[i]);
}
void file(string s)
{
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
int dis[110][110];
bool vis[100010];
int nowen=inf;
int can[110];
int cnt=0;
int cal()
{
	//memset(vis,0,sizeof(vis));
	if(k==cnt) return 0;
	for(int i=1;i<=k;i++) vis[can[i]]=1;
	int mn=-1,rmn=inf;
	for(int i=k+1;i<=cnt;i++)
	{
		rmn=inf;
		for(int j=1;j<=n;j++)
		{
			if(vis[j]) rmn=min(rmn,dis[can[i]][j]);
		}
		mn=max(mn,rmn);
	}
	for(int i=1;i<=k;i++) vis[can[i]]=0;
	return mn;
}
void sa()
{
	double T=5000;
	while(clock()<CLOCKS_PER_SEC*0.7)
	{
		int l=rand()%n+1,r=rand()%(cnt-k)+k+1;
		swap(can[l],can[r]);
		int tmp=cal();
		if(tmp<nowen) nowen=tmp;
		else if(exp(nowen-tmp)/T<(double)rand()/RAND_MAX) swap(can[l],can[r]);
		T*=0.998;
	}
}
void solve()
{
	//do something
	rd(n);rd(m);rd(k);
	memset(dis,0x3f,sizeof(dis));
	if(m+n==k){cout<<0;return;}
	for(int i=1;i<=n;i++) rd(a[i]),++a[i];
	for(int i=1;i<=n;i++)
	{
		rd(u);
		dis[i][a[i]]=dis[a[i]][i]=min(dis[i][a[i]],u);
		dis[i][i]=0;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
			}
		}
	}
	for(int i=1;i<=m;i++) rd(x),vis[++x]=1;
	for(int i=1;i<=n;i++) if(!vis[i]) can[++cnt]=i;
	shuffle(can+1,can+cnt+1,rnd);
	nowen=cal();
	sa();
	cout<<nowen;
}
void multi()
{
	//(tst);
	tst=1;
	while(tst--)
	{
		solve();
	}
	pcc();
}
signed main()
{
	srand(19260817);srand(rand());srand(rand());
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	multi();
}
// POWERED BY WITHERS
// THINK ONCE, CODE TWICE
/*things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <= , - or =
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. if you don't know where the bug is , try to clear some parts of the code
 and check each part seperately.
13. ...
*/
 
/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not 正难则反 or few affect?
*/

RT

2022/9/1 23:25
加载中...