UVA 1151 Buy or Build(生成树+二进制枚举)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
题意思路:见紫书
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000+10;
const int maxm = 10000+10;
#define INF 1e9
int n,m;
struct Edge
{
int u,v,dist;
Edge(){}
Edge(int u,int v,int dist):u(u),v(v),dist(dist){}
bool operator<(const Edge&rhs)const
{
return dist < rhs.dist;
}
};
struct point
{
int x,y;
};
point p[maxn];
int fa[maxn];
Edge e[maxn*maxn];
int findset(int x)
{
return fa[x]==-1?x:fa[x]=findset(fa[x]);
}
int di(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int kruskal()
{
int sum = 0;
int ans = 0;
// sort(e,e+m);
for (int i = 0;i<m;i++)
{
if (findset(e[i].u)!=findset(e[i].v))
{
fa[findset(e[i].u)]=findset(e[i].v);
ans+=e[i].dist;
if (++sum>=n-1)
return ans;
}
}
return ans;
}
int T,cas=1;
vector<int>g[10];
int c[10];
int main()
{
scanf("%d",&T);
while (T--)
{
if (cas>1)
printf("\n");
cas++;
int q;
scanf("%d%d",&n,&q);
for (int i = 0;i<q;i++)
{
int temp,cnt;
g[i].clear();
scanf("%d",&cnt);
scanf("%d",&c[i]);
for (int j = 0;j<cnt;j++)
{
scanf("%d",&temp);
g[i].push_back(temp);
}
}
for (int i = 1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
m=0;
for (int i = 1;i<=n;i++)
for (int j = i+1;j<=n;j++)
{
e[m++]=Edge(i,j,di(p[i],p[j]));
}
sort(e,e+m);
memset(fa,-1,sizeof(fa));
int ans = kruskal();
for (int s =0;s<(1<<q);s++)
{
int cost = 0;
memset(fa,-1,sizeof(fa));
for (int j= 0;j<q;j++)
{
if ((s>>j)&1) continue;
cost+=c[j];
for (int k = 1;k<g[j].size();k++)
{
if (findset(g[j][k])!=findset(g[j][0]))
{
fa[findset(g[j][k])]=findset(g[j][0]);
}
}
}
ans = min(cost+kruskal(),ans);
}
printf("%d\n",ans);
}
}
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |