【题意】
平面上有n个点(1<=N<=1000)，你的任务是让所有n个点连通，为此，你可以新建一些边，费用等于两个端点的欧几里得距离的平方。
另外还有q(0<=q<=8)个套餐，可以购买，如果你购买了第i个套餐，该套餐中的所有结点将变得相互连通，第i个套餐的花费为ci。
求最小花费。
Input
(1 ≤ n ≤ 1000) (0 ≤ q ≤ 8).The second integer is the the cost of the subnetwork
(not greater than 2 × 10^6). integer values (ranging from 0 to 3000)
Output...
Sample Input
1
7 3
2 4 1 2
3 3 3 6 7
3 9 2 4 5
0 2
4 0
2 0
4 2
1 3
0 5
4 4
Sample Output
17
【分析】
枚举套餐哦。其实生成树问题多一些东东的话都是枚举的吧？吗？
你一开始先排序好，枚举完就不用排序了。
LRJ说什么只考虑最小生成树上的边优化版本：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define INF 0xfffffff int a[][Maxn],c[];
int nx[Maxn],ny[Maxn];
int n,q; struct node
{
int x,y,c;
}t[Maxn*Maxn];
int len,nl; void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
} bool cmp(node x,node y) {return x.c<y.c;} int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} int fa[Maxn];
int ffa(int x)
{
if(fa[x]!=x) fa[x]=ffa(fa[x]);
return fa[x];
} void ffind()
{
int ans=INF;
for(int i=;i<(<<q);i++)
{
int now=;
for(int j=;j<=n;j++) fa[j]=j;
int ft=-;
for(int j=;j<=q;j++) if((<<j-)&i)
{
for(int k=;k<=a[j][];k++)
fa[ffa(a[j][k])]=ffa(a[j][]);
now+=c[j];
}
int cnt=;
for(int j=;j<=n;j++) if(ffa(j)==j) cnt++;
for(int j=;j<=nl;j++)
{
if(ffa(t[j].x)!=ffa(t[j].y))
{
fa[ffa(t[j].x)]=ffa(t[j].y);
now+=t[j].c;
cnt--;
}
if(cnt==) break;
}
ans=mymin(ans,now);
}
printf("%d\n",ans);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(int i=;i<=q;i++)
{
scanf("%d%d",&a[i][],&c[i]);
for(int j=;j<=a[i][];j++) scanf("%d",&a[i][j]);
}
for(int i=;i<=n;i++)
{
scanf("%d%d",&nx[i],&ny[i]);
}
len=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
// double xx=(double)(nx[i]-nx[j]),yy=(double)(ny[i]-ny[j]);
int xx=nx[i]-nx[j],yy=ny[i]-ny[j];
ins(i,j,xx*xx+yy*yy);
}
sort(t+,t++len,cmp);
int cnt=;nl=;
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=len;i++)
{
if(ffa(t[i].x)!=ffa(t[i].y))
{
fa[ffa(t[i].x)]=ffa(t[i].y);
cnt++;
t[++nl]=t[i];
}
if(cnt==n-) break;
}
ffind();
if(T) printf("\n");
}
return ;
}
- -
其实我觉得不用也没什么？？反正都排序选前面的，区别？？
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define INF 0xfffffff int a[][Maxn],c[];
int nx[Maxn],ny[Maxn];
int n,q; struct node
{
int x,y,c;
}t[Maxn*Maxn];
int len,nl; void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
} bool cmp(node x,node y) {return x.c<y.c;} int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} int fa[Maxn];
int ffa(int x)
{
if(fa[x]!=x) fa[x]=ffa(fa[x]);
return fa[x];
} void ffind()
{
int ans=INF;
for(int i=;i<(<<q);i++)
{
int now=;
for(int j=;j<=n;j++) fa[j]=j;
int ft=-;
for(int j=;j<=q;j++) if((<<j-)&i)
{
for(int k=;k<=a[j][];k++)
fa[ffa(a[j][k])]=ffa(a[j][]);
now+=c[j];
}
int cnt=;
for(int j=;j<=n;j++) if(ffa(j)==j) cnt++;
for(int j=;j<=len;j++)
{
if(ffa(t[j].x)!=ffa(t[j].y))
{
fa[ffa(t[j].x)]=ffa(t[j].y);
now+=t[j].c;
cnt--;
}
if(cnt==) break;
}
ans=mymin(ans,now);
}
printf("%d\n",ans);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(int i=;i<=q;i++)
{
scanf("%d%d",&a[i][],&c[i]);
for(int j=;j<=a[i][];j++) scanf("%d",&a[i][j]);
}
for(int i=;i<=n;i++)
{
scanf("%d%d",&nx[i],&ny[i]);
}
len=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
// double xx=(double)(nx[i]-nx[j]),yy=(double)(ny[i]-ny[j]);
int xx=nx[i]-nx[j],yy=ny[i]-ny[j];
ins(i,j,xx*xx+yy*yy);
}
sort(t+,t++len,cmp);
/*int cnt=0;nl=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=len;i++)
{
if(ffa(t[i].x)!=ffa(t[i].y))
{
fa[ffa(t[i].x)]=ffa(t[i].y);
cnt++;
t[++nl]=t[i];
}
if(cnt==n-1) break;
}*/
ffind();
if(T) printf("\n");
}
return ;
}
像是没有区别= =
2016-11-01 22:24:10