c++实例研究

从0开始

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  104 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks
晚上随便找了一道练手题。开始就看出是拓扑排序,将等级限制先不考虑后,写出个topo排序,再做更新处理。最后加上了等级限制。这题是一个考验理解能力的题目,本身算法不难。

well 编写测试用例恰当,一次AC。
less well 处理细节处有些鲁莽,其实可以想明白的再改。注意memset是按位初始化。

/*  
*    Doc Name: 昂贵的聘礼
*    Prob Id: 1062
*    Serial Id: 2
*    Author: LTE
*    Date: 10/10/27
*/


#include 
<iostream>
using namespace std;

const int MAXN = 101;

int g[MAXN][MAXN];
int M,N;
bool visit[MAXN];
int topo[MAXN];
int tpi = 0;
struct V{
    
int level; 
    
int price;
}
;
V item[MAXN];
int a,b;
int i,j;
int en;

void dfsTopo(int v)
{
    visit[v] 
= 1;
    
int i;
    
for(i=1; i<=N; i++)
    
{
        
if((g[v][i]!= -1)&&(!visit[i]))
            dfsTopo(i);
    }

    topo[tpi
++= v;
}


int minGold()
{
    
for(i=0; i<tpi-1; i++)
    
{
        
for(j=i+1; j<tpi; j++)
        
{
            
if(g[topo[j]][topo[i]]>0)
            
{
                
int pr = g[topo[j]][topo[i]]+item[topo[i]].price;
                
if(pr < item[topo[j]].price)
                    item[topo[j]].price 
= pr;
            }

        }

    }

    
return item[1].price;
}


int main()
{
    
//freopen("in.txt", "r", stdin);
    
//freopen("out.txt", "w", stdout);

    memset(g, 
-1sizeof(int)*MAXN*MAXN);
    memset(visit, 
0sizeof(bool)*MAXN);
    scanf(
"%d%d"&M, &N);
    
for(i=1;i<=N;i++)
    
{
        scanf(
"%d%d%d"&item[i].price, &item[i].level, &en);
        
for(j=0; j<en; j++)
        
{
            scanf(
"%d%d"&a, &b);
            g[i][a] 
= b;
        }

        
if( abs(item[i].level-item[1].level) > M )
        
{
            
for(j=1;j<N;j++) g[j][i]=-1;
        }

    }

    
    dfsTopo(
1);
        
    printf(
"%d\n", minGold());
    
    
//system("PAUSE");
    return 0;
}

posted on 2010-10-27 23:27 elprup 阅读(1188) 评论(4)  编辑 收藏 引用 所属分类: POJ

评论

# re: POJ 1062 拓扑排序 2011-05-18 16:03 银志圆
程序写的太好了   回复  更多评论
  

# re: POJ 1062 拓扑排序 2011-10-15 20:43 sly
感觉写的有问题,题目中有 间接访问<m的限制。  回复  更多评论
  

# re: POJ 1062 拓扑排序 2011-12-05 21:53 Ancowei
这不是杭电上的题吧。
  回复  更多评论
  

# re: POJ 1062 拓扑排序 2012-01-23 13:02 npbool
感觉真有问题,用以下数据试试看
5 3
10000 10 1
2 1000
1000 8 1
3 200
100 14 0
物品2和物品3等级差了6,不能交换,但你的算法给出最优解1300,其实应该是2000。POJ上提交AC实在不能理解。还是区间dijkstra扫描正确。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理