啊这题竟然在POJ上有……

枚举套餐子集是肯定的啦，但接下来呢？有的同学或许会想直接Kruskal求MST。但是估计会T。

有一个很有效的优化：先求一遍不加套餐的MST，然后接下来每次求MST的时候都只考虑这[tex]n-1[/tex]条边，这样就很快了。

需要注意的是，这[tex]n-1[/tex]以外的边就算加入了套餐也不会被考虑。因为无论加不加套餐，这些更大的边所能连接的连通分量总是可以被以前更小的边连接，所以这条边无论如何也不会被考虑啦……

代码写起来容易让人崩溃……所以说这个题很能锻炼代码能力和Debug能力。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1005,maxq=8;
int n;

int p[maxn],rank[maxn];
int find_set(int x){
	if(p[x]==x)
		return x;
	else
		return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
	if(rank[x]>rank[y]){
		p[y]=x;
	}else{
		p[x]=y;
		if(rank[x]==rank[y])
			rank[y]++;
	}
}
inline void union_set(int x,int y){
	link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
	return find_set(x)==find_set(y);
}
inline void init_set(){
	register int i;
	for(i=1;i<=n;i++)
		p[i]=i;
	memset(rank,0,sizeof(rank));
}

int Cost[maxq];
vector<int> V[maxq];
struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
vector<Edge> bj;
vector<Edge> E;
vector<Edge> garbage;
int MST(int cnt,vector<Edge>& E,vector<Edge>& to){
	if(!cnt)
		return 0;
	register int i,ans=0;
	to.clear();
	for(i=0;i<E.size();i++){
		if(!is_same(E[i].u,E[i].v)){
			union_set(E[i].u,E[i].v);
			ans+=E[i].d;
			to.push_back(E[i]);
			if(!(--cnt))
				break;
		}
	}
	return ans;
}

int zb[maxn][2];
inline int EucSqr(int x,int y){
	int t1=zb[x][0]-zb[y][0],t2=zb[x][1]-zb[y][1];
	t1*=t1;
	t2*=t2;
	return t1+t2;
}
int main(){
	int T,q,num,u;
	register int i,j,k,cnt,temp,ans;
	scanf("%d%d",&n,&q);
	for(i=0;i<q;i++){
		scanf("%d%d",&num,&Cost[i]);
		V[i].clear();
		while(num--){
			scanf("%d",&u);
			V[i].push_back(u);
		}
	}
	for(i=1;i<=n;i++){
		scanf("%d%d",&zb[i][0],&zb[i][1]);
	}
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++){
			bj.push_back((Edge){i,j,EucSqr(i,j)});
		}
	init_set();
	sort(bj.begin(),bj.end());
	ans=MST(n-1,bj,E);
	for(i=0;i<(1<<q);i++){
		init_set();
		temp=0;
		cnt=n-1;
		for(j=0;j<q;j++)
			if(i&(1<<j)){
				temp+=Cost[j];
				for(k=1;k<V[j].size();k++){
					if(!is_same(V[j][k],V[j][0])){
						union_set(V[j][k],V[j][0]);
						cnt--;
					}
				}
			}
		ans=min(ans,temp+MST(cnt,E,garbage));
	}
	printf("%d\n",ans);
	return 0;
}

• 相关文章
• 全局相关文章