zoj 1586 QS Network

浏览数：20 / 时间：2015年06月09日

题意：若两个QS之间要想连网，除了它们间网线的费用外，两者都要买适配器，

求使所有的QS都能连网的最小费用

分析：这个除了边的权值外，顶点也有权值，因此要想求最小价值，必须算边及顶点的权值和

#include<cstdio>
#include<algorithm>
using namespace std;
int f[1010],n,m;
struct stu
{
    int a,b,c;
}t[500100];
int cmp(struct stu x,struct stu y)
{
    return x.c<y.c;
}
int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
int krus()
{
    int i,k=0,s=0,x,y;
    for(i=1;i<m;i++){
        x=find(t[i].a);
        y=find(t[i].b);
        if(x!=y){
            s+=t[i].c;
            k++;
            if(k==n-1)
                break;
            f[x]=y;
        }
    }
    return s;
}
int main()
{
    int T,i,j,a[1010],c,s=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            f[i]=i;
            scanf("%d",&a[i]);
        }
        m=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++){
                scanf("%d",&c);
                if(j<i){
                    t[m].a=i;
                    t[m].b=j;
                    t[m++].c=c+a[i]+a[j];        //计算边和顶点的权值和
                }
            }
        sort(t+1,t+m,cmp);
        s=krus();
        printf("%d\n",s);
    }
    return 0;
}

zoj 1586 QS Network,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

zoj 1586 QS Network