HDU2489【状压枚举】

题意：

给你n个点的图，然后让你在图里挑m个点，达到sumedge/sumnode最小

思路：

由于数据范围小，状压枚举符合m个点的状态，我是用vactor存了结点位置，也记录了结点的sum值，然后跑一发最小生成树就可以知道sumedge，这里判断可以利用乘法，然后更新一个状态就好了；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int ma[20][20];

int val[20];

int sumnode,sumedge;

int n,m;

int cnt;

int a,b;

int dis[20];

vector<int>pb;

bool vis[20];

int prim()

{

    memset(vis,0,sizeof(vis));

    dis[pb[0]]=0;

    vis[pb[0]]=1;

    for(int i=1;i<pb.size();i++)

    {

        dis[pb[i]]=ma[pb[0]][pb[i]]?ma[pb[0]][pb[i]]:1000000;

    }

    int ans=0;

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

    {

        int k=-1;

        int mimi=1000000;

        for(int j=0;j<pb.size();j++)

        {

            if(vis[pb[j]]) continue;

            if(dis[pb[j]]<mimi)

            {

                mimi=dis[pb[j]];

                k=j;

            }

        }

        if(k==-1)

            break;

        vis[pb[k]]=1;

        for(int j=0;j<pb.size();j++)

        {

            if(ma[pb[k]][pb[j]]&&!vis[pb[j]]&&dis[pb[j]]>ma[pb[k]][pb[j]])

                dis[pb[j]]=ma[pb[k]][pb[j]];

        }

    }

    for(int i=0;i<pb.size();i++)

    {

        ans+=dis[pb[i]];

    }

    return ans;

}

int main()

{

    while(scanf("%d%d",&n,&m))

    {

        if(!n&&!m) break;

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

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

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

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

            {

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

                if(ma[i][j]==0)

                    ma[i][j]=1000000;

            }

        a=1000000;

        b=1;

        int build=1<<n;

        int ans;

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

        {

            int cnt=0;

            sumnode=0;

            pb.clear();

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

            {

                if(i&(1<<j))

                {

                    cnt++;

                    pb.push_back(j);

                    sumnode+=val[j];

                }

            }

            if(cnt==m)

            {

                int sumedge=prim();

                if(a*sumnode>sumedge*b)

                {

                    a=sumedge;

                    b=sumnode;

                    ans=i;

                }

            }

        }

        int flag=0;

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

        {

            if(ans&(1<<i))

            {

                if(flag) printf(" ");

                printf("%d",i+1);

                flag=1;

            }

        }

        puts("");

    }

    return 0;

}