题目链接:

csu 1116

题意:

有一幅双向图连接N个城市（标号1~n,1表示首都）  每一个城市有一个价值W.

地震摧毁了全部道路,现给出可修复的m条道路并给出修复每条道路所需的费用

问在总费用不超过k的情况下,使得  与  首都连通的全部城市  的价值和 最大

解题思路:

点的数量不超过16 ,2^16次方枚举全部城市是否在连通的集合类

再通过kruskal推断这个集合是否合法就可以

代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct node{

    int a,b,w;

}edge[128];

int v[18];

int fa[18];

int sum;

void init()

{

    for(int i=0;i<18;i++)

        fa[i]=i;

    sum=0;

}

int Find(int x)

{

    return x==fa[x]?x:fa[x]=Find(fa[x]);

}

int cmp(node a,node b)

{

    return a.w<b.w;

}

int main()

{

    int T,n,m,k;

    int ans;

    int f1,f2;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&n,&m,&k);

        ans=0;

        for(int i=1;i<=n;i++)

            scanf("%d",&v[i]);

        for(int i=0;i<m;i++)

            scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].w);

        sort(edge,edge+m,cmp);                                  //给边排序 保证费用尽量小

        int num=(1<<n)-1;

        for(int i=0;i<=num;i++)

        {

            if(i&1)

            {

                init();

                for(int j=0;j<m;j++)

                    if(i&(1<<edge[j].a-1))

                        if(i&(1<<edge[j].b-1))              //当前边属于当前的点集

                        {

                            f1=Find(edge[j].a);

                            f2=Find(edge[j].b);

                            if(f1!=f2)

                            {

                                fa[f1]=f2;

                                sum+=edge[j].w;

                            }

                        }

                for(int j=1;j<=n;j++)

                    if((i&(1<<j-1))&&Find(j)!=Find(1))        //当前点集有多余的点

                    {

                        sum=k+1;

                        break;

                    }

                if(sum<=k)

                {

                    sum=0;

                    for(int j=1;j<=n;j++)

                        if(i&(1<<j-1))

                            sum+=v[j];

                    if(sum>ans)

                        ans=sum;

                }

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}