王伯买鱼问题

问题描述
   王伯退休后开始养鱼。他一早起来就赶去动物公园，发现这个世界的鱼真不少，五光十色、色彩斑斓，大的、小的，什么样的都有。这些鱼实在太美了，买的人越来越多，湖里的鱼越来越少。没有美丽的鱼，哪里有美丽的湖？于是动物公园不得不规定，对于每种鱼，每个人最多只能买一条。并且有些鱼是不能一起买的，因为放在一起他们相互争斗吞食。
   王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编程帮他，如果有多个方案能买尽可能多的鱼，选择所花资金最多的一种方案。
   输入：第一行：资金m（<=1000）和鱼的种类n(<=30)。以下n行，每行有两个正整数，鱼的编号s（1<=s<=n）和该鱼的价格t。接着又有若干行，每行两个整数p和q，当p和q都大于0时，表示p和q不能共处；当p和q均等于0时，表示输入结束。
   输出：第一行两个整数，x和y，x表示买的鱼的条数，y表示总的花费。以下x行，每行有一个整数，表示所买鱼的编号。编号按升序排列输出。
   样例输入：
   170 7
   1 70
   2 50
   3 30
   4 40
   5 40
   6 30
   7 50
   1 4
   1 7
   3 4
   3 5
   5 7
   6 3
   0 0
   样例输出：
   4 170
   2
   4
   6
   7
#include
#include
#include
#include
#include
using namespace std;

vector > all;
const int maxn=30;
//int price[maxn+1]={0,70,50,30,40,40,30,50}; //各种鱼的价格
int  price[maxn+1];
int killed[maxn+1];
int  enemy[maxn+1];
//初始化敌者数组
void  init(int** a,int m)
{
    
    for(int i=1;i
    {
        for(int j=1;j
            if(a[i][j]==1)
            {
                enemy[i]++;//按行计数
            }
        killed[i]=0;
    }
}
bool  check(int enemy[],int n)
{
    //全部要么被杀掉，要么已经无敌人了，才算成功
    for(int i=1;i
        if(enemy[i]!=0 && !killed[i])
            return false;
    return true;
}
void search(int** a,int m,int tag)
{
    //先检查再说
    if(check(enemy,m)==true)
    {
        vector tmp;
        int cost=0;  //总价钱
        for(int i=1;i
            if(enemy[i]==0)  //无敌者
            {
                tmp.push_back(i);
                cost+=price[i];
            }
        tmp.push_back(cost);//最后一个元素是总价钱
        all.push_back(tmp);
    }else{  //下面一定有没有被杀且不为0的元素
        //只在非0且没有被杀掉的元素中找最小值
        int min=INT_MAX;
        for(int i=1;i
        if(enemy[i] && !killed[i])
        {
            if(enemy[i]
            {
                min  = enemy[i];
            }
        }
        //深搜,剪枝
        for(int i=1;i
        if(enemy[i]==min && !killed[i])
        {
            //杀掉敌人j,并更新敌人数组，同盟者可以少一个敌人了,注意这个敌人可能早就被杀掉了
            for(int j=1;j
                if(a[i][j]==1&& !killed[j])
                {
                    killed[j]=tag;     //j这个敌人被杀掉了
                    //k为i同盟者,包括i
                    for(int k=1;k
                        if(a[j][k]==1)
                           enemy[k]--;
                }
            search(a,m,tag-1);
            //复活敌人
            for(int j=1;j
                if(a[i][j]==1&& killed[j]==tag)
                {
                    killed[j]=0;     //j这个敌人复活了
                    //k为i同盟者,包括i
                    for(int k=1;k
                        if(a[j][k]==1)
                           enemy[k]++;
                }
        }
    }       
}
/*example
//a为各鱼之间的共存性,竞争对手
int a[maxn+1][maxn+1]={
    0,0,0,0,0,0,0,0,
    0,0,0,0,1,0,0,1,
    0,0,0,0,0,0,0,0,
    0,0,0,0,1,1,1,0,
    0,1,0,1,0,0,0,0,
    0,0,0,1,0,0,0,1,
    0,0,0,1,0,0,0,0,
    0,1,0,0,0,1,0,0,
};
*/
main()
{
    int money,m;
    cin>>money>>m;
    int j,k;
    for(int i=1;i
    {
        cin>>j>>k;
        price[j]=k;   
    }
    int* opponents[m+1];
    for(int i=1;i
            opponents[i]=new int[m+1];   
    cin>>j>>k;
    while(j!=0)
    {
        opponents[j][k]=1;
        opponents[k][j]=1;
        cin>>j>>k;           
    }
    init(opponents,m);
    search(opponents,m,m);
    cout<
    j=0;
    for(int i=1;i
        if(all[i].back()> all[j].back() &&  all[i].back()<=money)   
            j=i;
    cout<<' '<
    copy(all[j].begin(),all[j].end()-1,ostream_iterator(cout,"\n") );
    for(int i=1;i
        delete[]  opponents[i];
}