首页 > 代码库 > uva 1151 - Buy or Build poj 2784 Buy or Build(最小生成树)
uva 1151 - Buy or Build poj 2784 Buy or Build(最小生成树)
也是简单的最小生成树算法
不过添加了一些新的东西,需要对最小生成树算法 以及其中的 并查集的使用 有一些比较深入的理解。
处理问题的方法也有些复杂
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 1005; struct point { int x; int y; }pp[maxn]; struct edge { int s; int e; int dist; }l[maxn*maxn]; int n,q,m; int p[maxn]; vector<int> g[10]; int c[10]; int distance_(point a,point b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int cmp(edge a,edge b) { return a.dist < b.dist; } int find_(int x) { return p[x]==x?x:p[x]=find_(p[x]); } bool merge_(int a,int b) { int x=find_(a); int y=find_(b); if(x==y) return false; p[x]=y; return true; } int kruskal() { int ans=0; int num=0; for(int i=0;i<m&&num<n-1;i++) { if(merge_(l[i].s,l[i].e)) { num++; ans+=l[i].dist; } } return ans; } void solve() { for(int i=0;i<=n;i++) p[i]=i; int ans = kruskal(); for(int s=1;s<(1<<q);s++) { int cost=0; for(int tt=0;tt<=n;tt++) p[tt]=tt; for(int j=0;j<q;j++) { if(!((s>>j)&1)) continue; cost+=c[j]; for(int k=0;k<g[j].size();k++) { merge_(g[j][k],g[j][0]); } } ans=min(ans,cost+kruskal()); } printf("%d\n",ans); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&q); for(int i=0;i<10;i++) g[i].clear(); for(int i=0;i<q;i++) { int cnt; scanf("%d%d",&cnt,&c[i]); int a; for(int j=0;j<cnt;j++) { scanf("%d",&a); g[i].push_back(a); } } for(int i=1;i<=n;i++) { scanf("%d%d",&pp[i].x,&pp[i].y); } m=0; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { l[m].s=i; l[m].e=j; l[m++].dist=distance_(pp[i],pp[j]); } } sort(l,l+m,cmp); solve(); if(t) printf("\n"); } return 0; }
对于给出的几种方案需要采用 子集枚举 算法。
在上面的解决方法中,用到了二进制帮助子集枚举的办法,只适用于集合元素比较小的子集枚举算法。
上面的方法采取了用结构体来表示edge的方法,没有开那么多的数组。我觉得用结构体可以是代码的可读性更高。
uva 1151 - Buy or Build poj 2784 Buy or Build(最小生成树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。