Noip2017宝藏(提高d2t2)

模拟退火吼啊!

阅读全文大概需要 9分钟
本文总阅读量
Posted by yjjr's blog on October 13, 2018

标签:模拟退火,搜索剪枝,状压DP

题目

[题目传送门](https://www.luogu.org/problemnew/show/P3959)

题目描述

参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 \(n\) 个深埋在地下的宝藏屋, 也给出了这 \(n\) 个宝藏屋之间可供开发的\(m\) 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远, 也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路 则相对容易很多。

小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。

在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。

新开发一条道路的代价是:

\[\mathrm{L} \times \mathrm{K}\]

L代表这条道路的长度,K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋) 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代 价最小,并输出这个最小值。

输入输出格式

输入格式

第一行两个用空格分离的正整数 \(n,m\),代表宝藏屋的个数和道路数。

接下来 \(m\) 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏 屋的编号(编号为 \(1-n\)),和这条道路的长度 \(v\)。

输出格式

一个正整数,表示最小的总代价。

输入输出样例

输入样例#1

4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 1 

输出样例#1

4

输入样例#2

4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 2  

输出样例#2

5

说明

【样例解释1】

小明选定让赞助商打通了\(1\) 号宝藏屋。小明开发了道路 \(1 \to 2\),挖掘了 \(2\) 号宝 藏。开发了道路 \(1 \to 4\),挖掘了 \(4\) 号宝藏。还开发了道路 \(4 \to 3\),挖掘了\(3\)号宝 藏。工程总代价为:\(1 \times 1 + 1 \times 1 + 1 \times 2 = 4\)

【样例解释2】

小明选定让赞助商打通了\(1\) 号宝藏屋。小明开发了道路 \(1 \to 2\),挖掘了 \(2\) 号宝 藏。开发了道路 \(1 \to 3\),挖掘了 \(3\) 号宝藏。还开发了道路 \(1 \to 4\),挖掘了\(4\)号宝 藏。工程总代价为:\(1 \times 1 + 3 \times 1 + 1 \times 1 = 5\)

【数据规模与约定】

对于\(20\%\)的数据: 保证输入是一棵树,\(1 \le n \le 8\),\(v \le 5000\) 且所有的 \(v\)都相等。

对于 \(40\%\)的数据: \(1 \le n \le 8\),\(0 \le m \le 1000\),\(v \le 5000\) 且所有的\(v\)都相等。

对于\(70\%\)的数据: \(1 \le n \le 8\),\(0 \le m \le 1000\),\(v \le 5000\)

对于\(100\%\)的数据: \(1 \le n \le 12\),\(0 \le m \le 1000\),\(v \le 500000\)

题解

考场上写了45pts的prim假算法

事实上加个模拟退火就AC了

写个模拟退火,总比去硬肝状压DP要划算吧

可惜去年NOIP我还不会模拟退火GG

code

45pts prim

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=1e5+6;
struct edge{int to,self,w;}e[maxn<<1];
int dis[maxn],vis[maxn],n,m,cnt=0;
ll ans=1844387848,sum=0;
void dfs()
{
    ll s=1,sum=0;
    while(s<=n-1){
        ll mi=1844387848,num;
        rep(i,1,cnt)
            if(vis[e[i].self]&&((ll)((dis[e[i].self]+1)*e[i].w)<mi)&&!vis[e[i].to]){
                mi=e[i].w*(dis[e[i].self]+1);
                num=i;
            }
        vis[e[num].to]=1;
        dis[e[num].to]=dis[e[num].self]+1;
        sum+=mi;
        s++;
    }
    ans=min(ans,sum);
}
int main()
{
    //freopen("treasure.in","r",stdin);
    //freopen("treasure.out","w",stdout);
    n=read(),m=read();
    rep(i,1,m){
        int x=read(),y=read(),z=read();
        e[++cnt]=(edge){y,x,z};
        e[++cnt]=(edge){x,y,z};
    }
    rep(i,1,n){
        mem(vis,0);mem(dis,0);
        vis[i]=1;dis[i]=0;
        dfs();
    }
    cout<<ans<<endl;
    return 0;
}

模拟退火AC代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
const int maxn=16;
int n,m,Map[maxn][maxn],deep[maxn],vis[maxn],ans=inf;
struct edge{int u,v;}e,et,past[maxn];
inline bool operator < (edge a,edge b){return deep[a.u]*Map[a.u][a.v]>deep[b.u]*Map[b.u][b.v];}

inline int search(int x){
	mem(deep,0);mem(vis,0);mem(past,0);int p=0,cost=0;e.u=0,e.v=0;et.u=0,et.v=0;
	priority_queue<struct edge>heap;
	deep[x]=1;vis[x]=1;
	rep(i,1,n)if(Map[x][i]<inf)e.u=x,e.v=i,heap.push(e);
	rep(i,1,n-1){
		e=heap.top();heap.pop();
		while(!heap.empty()&&((vis[e.v]||rand()%n<1))){
			if(!vis[e.v])past[p++]=e;
			e=heap.top();heap.pop();
		}
		vis[e.v]=1;deep[e.v]=deep[e.u]+1;
		if(p-->0)while(p>=0){heap.push(past[p]);p--;}
		p=0;
		rep(i,1,n)
			if(Map[e.v][i]<inf&&!vis[i]){
				et.u=e.v;et.v=i;
				heap.push(et);
			}
		cost+=Map[e.u][e.v]*deep[e.u];
	}
	return cost;
}
int main()
{
	n=read(),m=read();
	mem(Map,0x3f3f3f);
	rep(i,1,m){
		int x=read(),y=read(),z=read();
		Map[x][y]=Map[y][x]=min(z,Map[x][y]);
	}
	srand(1125);
	rep(j,1,600){
		rep(i,1,n)ans=min(ans,search(i));
	}
	cout<<ans<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr