00:00/00:00

1000:MagicMoleculeEasy

题意:

给你一个一般图,图中有n个点(n小于50),每个点都有权值,你要选出一个点的集合,满足集合中正好有k个元素,每一条边的两个端点至少有一个存在于集合中,问你最大权值。。。

分析:

因为点很少,然后边也不多,那么我们直接暴力枚举每一条边两边定点的状态就好了,复杂的玄学。。。

代码:

 

int n,cnt,ans,ret;
int num[55],cost[55];
int vis[55];
struct Edge{int u,v;}edge[2550];
bool cmp(const int &a,const int &b){return cost[a]>cost[b];}
int check(int now)
{
    for(int i=now;iK)return;
    if(K==k&&check(now)) {ans=max(ans,ret);return;}
    if(kcnt)
    {
        int flag=ret;
        for(int i=1;i<=n;i++)
        {
            if(!vis[num[i]])
                ret+=cost[num[i]],k++;
            if(k==K)
                break;
        }   
        if(k==K)ans=max(ans,ret);
        ret=flag;return;
    }
    while((vis[edge[now].u]||vis[edge[now].v])&&nowcnt){dfs(now,k,K);return;}
    vis[edge[now].u]=1,ret+=cost[edge[now].u];
    dfs(now+1,k+1,K);
    vis[edge[now].v]=1,ret+=cost[edge[now].v];
    dfs(now+1,k+2,K);
    vis[edge[now].u]=0,ret-=cost[edge[now].u];
    dfs(now+1,k+1,K);
    vis[edge[now].v]=0,ret-=cost[edge[now].v];
}
int MagicMoleculeEasy::maxMagicPower(vector  magicPower, vector  magicBond, int k) {
    cnt=0;
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));
    n=magicPower.size();
    for(int i=0;i<n;i++)
        cost[i+1]=magicPower[i],num[i+1]=i+1;
    sort(num+1,num+n+1,cmp);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(magicBond[i][j]=='Y')
                edge[++cnt].u=i+1,edge[cnt].v=j+1;
    ans=-1;dfs(1,0,k);
    return ans;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注