> 这道题我做了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;
> }

• 哦，是的。多谢了。:) (0) Cocoa17 2005-07-21 14:30:32