• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku 1456
		
            
		
            2009年7月13日 星期一

            題目鏈接：PKU 1456 Supermarket

            分類：帶限制的作業(yè)排序問題（貪心+并查集）

            Code：

             1            #include<stdio.h>
             2#include<stdlib.h>
             3#define max 10005
             4
             5int n,i,j,sum,parent[max],f[max];
             6
             7struct zuoye
             8{
             9    int p,d;
            10}            task[max];
            11
            12void init(int n)
            13{
            14    for(i=0;i<=n;i++)
            15    {
            16        parent[i]=-1;
            17        f[i]=i;
            18    }
            19}
            20int find(int x)
            21{
            22    if(parent[x]<0) return x;
            23    else return parent[x]=find(parent[x]);
            24}
            25int Union(int x,int y)
            26{
            27    int root1=find(x),root2=find(y);
            28    if(root1==root2) return root1;
            29    if(parent[root1]<parent[root2])
            30    {
            31        parent[root1]+=parent[root2];
            32        parent[root2]=root1;
            33        return root1;
            34    }
            35    else
            36    {
            37        parent[root2]+=parent[root1];
            38        parent[root1]=root2;
            39        return root2;
            40    }
            41}
            42void FJS()
            43{
            44    int i,j,l;
            45    for(i=1;i<=n;i++)
            46    {
            47        if(task[i].d>n)j=find(n);
            48        else j=find(task[i].d);
            49        if(f[j]!=0)
            50        {
            51            sum+=task[i].p;
            52            l=find(f[j]-1);
            53            Union(l,j);
            54            f[j]=f[l];
            55        }
            56    }
            57    printf("%d\n",sum);
            58}
            59int cmp(const void *a,const void *b)
            60{
            61    return (*(zuoye *)b).p>(*(zuoye *)a).p? 1: -1;
            62}
            63int main()
            64{
            65    while(scanf("%d",&n)!=EOF)
            66    {
            67        init(n);
            68        sum=0;
            69        for(i=0;i<n;i++)scanf("%d %d",&task[i].p,&task[i].d);
            70        qsort(task,n,sizeof(task[0]),cmp);
            71        for(i=n;i>=1;i--)task[i]=task[i-1];
            72        FJS();
            73    }
            74    return 0;
            75}
            76
            

		
            
			posted on 2009-07-13 23:33 蝸牛也Coding 閱讀(971) 評論(1)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				# re: pku 1456
					
						2010-01-20 19:41
					
				雪舞冰封
			
            
			
            
				很受啟發(fā)，這里謝過了。  回復(fù)  更多評論
				  
			
            
		

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年7月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計(jì)
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



2021最新久久久视精品爱|
亚洲AV无码久久|
日韩AV毛片精品久久久|
久久伊人色|
久久99精品久久久大学生|
精品国际久久久久999波多野|
av无码久久久久不卡免费网站|
99久久亚洲综合精品网站|
性做久久久久久久久老女人|
久久人人爽爽爽人久久久|
91久久精品无码一区二区毛片|
欧美久久一级内射wwwwww.|
久久AV高清无码|
久久久久九国产精品|
亚洲精品乱码久久久久久久久久久久
|
国产精品免费久久久久久久久
|
久久精品国产一区二区三区不卡|
久久久久青草线蕉综合超碰|
久久精品国产只有精品66|
国产麻豆精品久久一二三|
色老头网站久久网|
国产 亚洲 欧美 另类 久久|
久久精品天天中文字幕人妻
|
久久久久无码国产精品不卡|
国产V综合V亚洲欧美久久|
亚洲AV无一区二区三区久久|
欧美精品一区二区久久|
很黄很污的网站久久mimi色
|
久久久国产视频|
久久五月精品中文字幕|
国产精品嫩草影院久久|
国产99久久久国产精品～～牛|
avtt天堂网久久精品|
久久精品国产亚洲AV电影|
日韩精品久久无码人妻中文字幕|
香港aa三级久久三级老师2021国产三级精品三级在
|
久久亚洲精品国产精品婷婷
|
国内精品久久久久影院薰衣草|
伊人久久大香线蕉无码麻豆|
久久人人爽人人爽人人片AV麻豆
|
久久99精品久久久久久秒播
|