海星请帮帮我

皇宫看守问题的c++语言实现，怎么做？？？？
我快急晕了

7 个解决方案

#1

我记的海星的homepage上有，http://algorithm.126.com
去看看吧！呵呵，给斑竹做广告！:L

#2

是用c 编的，我想要c++的。3ks！！

#3

C++不就是比C多了个面向对象吗，并不是所有的问题都适合用面向对象的模式来解决的，对于那道皇宫看守问题，根本没有必要用到面向对象的设计模式。

#4

我想用c++来实现，怎么设计？
你的程序的节点指针怎么作的？

#5

#include <stdio.h>
#include <assert.h>
#include <iostream.h>
#include <fstream.h>
#include <alloc.h>
#include <string.h>
#include <values.h>
#define MAX_N 1500+1
#define INPUT_FILE "节点信息.TXT"//输入数据文件
#define OUTPUT_FILE "结果.TXT"//输出文件
#define false 0
#define true  1

class treeNode
{
friend class tree;
private:
int cost;//节点花费
int label;//节点标号
treeNode * first,* next;
treeNode(int val1=0,int val2=0,treeNode * fc=NULL,treeNode * ns=NULL):cost(val1),label(val2),first(fc),next(ns){}
};
class tree
{
public:
tree(){root=current=NULL;}
~tree(){}
buildRoot(int rootval);
int isempty();
int find(int target);
void insertChild(int num,int value);
int CalF(int t,int j);
int solve();
int readcase();
void closefile();
private:
treeNode * root,* current;
int find(treeNode * p,int target);
int f[MAX_N][3];
int Min(int a, int b);
FILE *fin, *fout;    /* 输入输出文件                               */
int minres;
};

int main(void)
{
tree palace;
palace.readcase();
palace.solve();
palace.closefile();
    return 0;
  }

int tree::buildRoot(int rootval)
{
root=current= new treeNode(rootval,1);
return 0;
}

int tree::isempty()
{
if (root==NULL)
return 1;
else return 0;
}
int tree::find(int target)
{
if (isempty()) return 0;
return find(root,target);
}
int tree::find(treeNode * p,int target)
{
int result=0;
if (p->label==target){result=1;current=p;}
else{
treeNode * q=p->first;
while(q!=NULL&&!(result=find(q,target)))q=q->next;
}
return result;
}
void tree::insertChild(int value,int num)
{
treeNode * newNode = new treeNode(value,num);
if(current->first==NULL) current->first= newNode;
else{
treeNode * p=current->first;
while(p->next!=NULL) p=p->next;
p->next= newNode;
}

}
int tree::CalF(int t,int j)
{ treeNode *k, *i;
int s, res;
treeNode * nowNode=new treeNode;
if(f[t][j]>=0) return f[t][j];
find(t);
nowNode=current;
if(nowNode->first==NULL)
{
f[t][0]=nowNode->cost;
f[t][1]=0;
f[t][2]=nowNode->cost;
return f[t][j];
}
res=MAXINT;
switch( j ) {
    case 0:   k = current->first;
              while( k ) {

                /* 累加除了儿子结点k以外各项的最优代价 */
                i = current->first;
                s = 0;
                while( i ) {
                  if( i!= k)
s += Min( CalF(i->label,0), CalF(i->label,2) );
                    i = i->next;
                }
res = Min( res, s + CalF(k->label,2) );  /* 记录res的最优值, 公式（1） */
                k = k->next;
              }
              break;
    case 1:   i = current->first;
              s = 0;
              while( i ) {                               /* 公式（2） */
s += Min( CalF(i->label,0), CalF(i->label,2) );
                i = i->next;
              }
              res = s;
              break;
    case 2:   i = current->first;
              s = 0;
              while( i ) {                               /* 公式（3） */
s += Min( CalF(i->label,1), CalF(i->label,2) );
                i = i->next;
              }
              res = s + nowNode->cost;
              break;
   }

   f[t][j] = res;

   return res;

}
int tree::Min(int a, int b)
{
  if( a < b )
    return a;
  else
    return b;
}
int tree::solve()
{int nn,mm;
  for (mm=0;mm<=1500 ;mm++ )
for(nn=0;nn<=2;nn++){f[mm][nn]=-1;};
minres=Min( CalF(1,0), CalF(1,2) );
//fprintf( fout, "%d", Min( CalF(root,0), CalF(root,2) ));
return minres;

}
int tree::readcase()
{
int count, value, num,rootcost,n,m;
    //treeNode * p=new treeNode;
fin = fopen( INPUT_FILE , "r" );
    fout = fopen( OUTPUT_FILE, "w" ) ;
if( feof(fin) )
{cout<<"空文件，请在节点信息.TXT中按要求写入节点信息"<<endl;
return 0;}
fscanf(fin, "%d", &n);//读入节点个数
fscanf(fin, "%d", &rootcost);//读入根节点标号
fscanf(fin, "%d", &rootcost);//读入看守根节点所花费用
        buildRoot(rootcost);
for( count = 1; count <= n; count++ )
{
fscanf( fin, "%d", &m );
for ( ; m>0; m-- )
{
fscanf(fin, "%d", &num);
fscanf(fin, "%d", &value);
insertChild(value,num);
}
if (count<n)
      find(count+1);
}
current=root;
}
void tree::closefile()
{
fprintf( fout, "%d", minres);
fclose( fin  );
    fclose( fout );
   }
有逻辑错误

#6

海星，谢谢了。

#7

sunnyice(jiajia)，那个代码是我写的吗，不太像呀，好像是你自己改编的吧，有什么问题吗

#1