程序员人生 网站导航

uva 1151 - Buy or Build poj 2784 Buy or Build(最小生成树)

栏目:互联网时间:2014-09-24 07:14:29

也是简单的最小生成树算法

不过添加了一些新的东西,需要对最小生成树算法 以及其中的 并查集的使用 有一些比较深入的理解。

处理问题的方法也有些复杂

#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 ",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(" "); } return 0; }

对于给出的几种方案需要采用 子集枚举 算法。

在上面的解决方法中,用到了二进制帮助子集枚举的办法,只适用于集合元素比较小的子集枚举算法。

上面的方法采取了用结构体来表示edge的方法,没有开那么多的数组。我觉得用结构体可以是代码的可读性更高。


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐