uva 1151 - Buy or Build poj 2784 Buy or Build（最小生成樹）
來源：程序員人生 發(fā)布時(shí)間：2014-09-24 07:14:29 閱讀次數(shù)：2613次
也是簡(jiǎn)單的最小生成樹算法
不過添加了一些新的東西，需要對(duì)最小生成樹算法 以及其中的 并查集的使用 有一些比較深入的理解。
處理問題的方法也有些復(fù)雜
#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;
}
對(duì)于給出的幾種方案需要采用 子集枚舉 算法。
在上面的解決方法中，用到了二進(jìn)制幫助子集枚舉的辦法，只適用于集合元素比較小的子集枚舉算法。
上面的方法采取了用結(jié)構(gòu)體來表示edge的方法，沒有開那么多的數(shù)組。我覺得用結(jié)構(gòu)體可以是代碼的可讀性更高。
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
