CSU 1116 Kingdoms 最小生成树（prim)

由于点数只有16，而点1又必选，暴力枚举选点情况，每次做一个最小生成树

这里用的prim算法，要注意的是存在选取这些点但找不到生成树的情况，需要将之排出

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=18;
int mp[maxn][maxn];
int wi[maxn];
bool vis[maxn];
int prim(int n)
{
    int low[maxn];
    int ans=0,i,j;
    for(i=1;i<=n;i++)
        if(!vis[i])
            low[i]=mp[1][i];
        else
            low[i]=0;
    for(i=2;i<=n;i++)
    {
        int mi=INF,idx;
        for(j=2;j<=n;j++)
            if(!vis[j]&&low[j]<mi)
            {
                mi=low[j];
                idx=j;
            }
        if(mi==INF)    break;
        ans+=mi;
        vis[idx]=true;
        for(j=2;j<=n;j++)
            if(!vis[j]&&low[j]>mp[idx][j])
                low[j]=mp[idx][j];
    }
    for(i=2;i<=n;i++)
        if(!vis[i])    return INF;
    return ans;
}
int main()
{
    int i,j,n,m,k,t,u,v,w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(mp,INF,sizeof(mp));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&wi[i]);
            mp[i][i]=0;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            if(mp[u][v]>w)
            mp[u][v]=mp[v][u]=w;
        }
        int len=(1<<(n-1))-1;
        int ans=0;
        for(i=0;i<=len;i++)
        {
            int x=i;
            int sum=0;
            for(j=n;j>=2;j--)
            {
                if(x&1)    
                    vis[j]=true;
                else
                {
                    sum+=wi[j];
                    vis[j]=false;
                }
                x>>=1;
            }
            vis[1]=false;sum+=wi[1];
            int sk=prim(n);
            if(sk<=k&&sum>ans)    ans=sum;
        }
        printf("%d
",ans);
    }
    return 0;
}