这道题我做了2天了，在本地测试我始终测不出错误来，不知是不是我把题目意思理解错了。
我采用的是分支界限法。sample input和我自己设计的input都能过，就是不能AC。我不知道那个“不准间接交易”到底是什么意思，我的理解是凡是跟酋长地位相隔M的就不予考虑了，不知道这样理解是否正确。
哪位大虾要能给个错误的input给我也行，我现在就是不知道错在哪。

附程序如下：
#include <iostream>
#include <list>
#define INFINITE 0xFFFFFFFF
using namespace std;

// 物品的优惠交换条件
struct Condition
{
	int TiObjectID;		// 替代品ID
	unsigned int ViPrice;	// 优惠价格
};

// 物品
struct Object
{
	unsigned int Price;	// 物品的价格
	int Status;		// 物品主人的地位
	int CdtCount;		// 优惠条件个数
	Condition* pConditions;	// 物品的优惠交换条件
};

// 分支界限中的状态节点
struct StateNode
{
	int TiObjectID;		// 替代品ID，如果为0就是直接购买
	unsigned int CurEstPrice;	// 当前的最低估价
//	StateNode* Next;
};

int main()
{
	int M, N, i, j;
	Object* pObjects = NULL;
	unsigned int result = INFINITE;

	cin >> M >> N;
	pObjects = new Object[N];
	for (i=0; i<N; i++)
	{
		cin >> pObjects[i].Price >> pObjects[i].Status >> pObjects[i].CdtCount;
		if (pObjects[i].CdtCount > 0)
		{
			pObjects[i].pConditions = new Condition[pObjects[i].CdtCount];
			for (j=0; j<pObjects[i].CdtCount; j++)
			{
				cin >> pObjects[i].pConditions[j].TiObjectID >> pObjects[i].pConditions[j].ViPrice;
			}
		}
	}

	// 用分支界限法求解
    M = pObjects[0].Status - M;			// 将M转化为要求的最低地位等级
	Object* pCurObject = NULL;			// 当前处理的物品
	list<StateNode*> lstActiveNodePtr;		// 活结点列表
	StateNode* pCurNode = new StateNode;		// 当前处理的状态节点
	pCurNode->TiObjectID = 1;			// 从酋长女儿开始
	pCurNode->CurEstPrice = 0;

	while (true)
	{
		// 加入新状态节点
		pCurObject = &pObjects[pCurNode->TiObjectID-1];
		for (i=0; i<pCurObject->CdtCount; i++)
		{
			StateNode* pNewNode = new StateNode;// 要加入的新的状态节点
			if (pObjects[pCurObject->pConditions[i].TiObjectID-1].Status >= M)
			{
				pNewNode->TiObjectID = pCurObject->pConditions[i].TiObjectID;
				pNewNode->CurEstPrice = pCurNode->CurEstPrice + pCurObject->pConditions[i].ViPrice;
				lstActiveNodePtr.push_back(pNewNode);
			}
		}
		unsigned int tresult = pCurNode->CurEstPrice + pCurObject->Price;
		result = result > tresult ? tresult : result;
		// 删除老状态节点
		lstActiveNodePtr.remove(pCurNode);
		delete pCurNode;
		// 选出最优节点
		if (lstActiveNodePtr.size() == 0)
			break;
		pCurNode = NULL;//*lstActiveNodePtr.begin();
		unsigned int minCost = INFINITE;
		list<StateNode*>::iterator iter = lstActiveNodePtr.begin();
		while (iter != lstActiveNodePtr.end())
		{
			// 如果此节点最低估计值已经比当前最优解差，则剪枝。
			if ((*iter)->CurEstPrice >= result) {
				StateNode* node = *iter;
				iter++;
				lstActiveNodePtr.remove(node);
				delete node;
				if (lstActiveNodePtr.size() == 0)
					goto END;
				continue;
			}
			else if ((*iter)->CurEstPrice < minCost) {
				pCurNode = *iter;
				minCost = pCurNode->CurEstPrice;
			}
			iter++;
		}
	}

END:cout << result;
	return 0;
}

• 题意理解错了, 在交易的所有人中地位最高的和地位最低的等级差在M 内, 没有说酋长地位最高. (3022) xfxyjwf 2005-07-21 14:19:17
  • 哦，是的。多谢了。:) (0) Cocoa17 2005-07-21 14:30:32