• <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 1419
		
            
		
            2009年8月9日

            題目鏈接：PKU 1419 Graph Coloring

            分類：DFS

            題目分析與算法原型
                     算法1：直接暴力搜索即可過，數據不強，實現默認每個點為白色，然后從第一個點開始搜索，對于當前的頂點，枚舉與他相鄰的點中是否有黑色，若沒有則將他染黑色，然后頂點編號加一，繼續搜索下一個，若與他相鄰的點中有已經染黑的點，那么只能將當前的點染成白色，然后繼續搜索，注意無論有沒有黑色的鄰點，對于當前的點都要染白一次，搜索，因為對于白色是沒有限制的....
                    算法2：其實這是一道最大獨立集問題，對于該種問題可以通過將原圖求補，就可以變成求其補圖的最大團問題，通過最大團來求解
                   （PS：算法1->47ms,算法2->0ms）

            Code1: 

             1            #include<stdio.h>
             2#include<string.h>
             3#define max 105
             4bool flag[max];
             5int map[max][max],t,n,k,color[max],count,pos[max],fp,black,cnt;//color數組：0表示白，1表示黑
             6void dfs(int num)
             7{
             8    int i;
             9    if(num==n)
            10    {
            11        int j;
            12        if(black>count)
            13        {   
            14            fp=0;
            15            count=black;
            16            for(j=1;j<=n;j++)if(color[j]==1)pos[fp++]=j;
            17        }
            18        return ;
            19    }
            20    for(i=1;i<=n;i++)
            21        if(i!=num&&map[num][i]==1&&color[i]==1)break;
            22    if(i>n)
            23    {
            24        color[num]=1;
            25        black++;
            26        dfs(num+1);
            27        color[num]=0;
            28        black--;
            29    }
            30    dfs(num+1);
            31}
            32int main()
            33{
            34    int i;
            35    scanf("%d",&t);
            36    while(t--)
            37    {
            38        memset(flag,false,sizeof(flag));
            39        memset(map,0,sizeof(map));
            40        memset(color,0,sizeof(color));
            41        scanf("%d%d",&n,&k);
            42        for(i=1;i<=k;i++)
            43        {
            44            int a,b;
            45            scanf("%d%d",&a,&b);
            46            map[a][b]=1;
            47            map[b][a]=1;
            48        }
            49        count=0;
            50        black=0;
            51        dfs(1);
            52        printf("%d\n",count);
            53        for(i=0;i<fp;i++)
            54        {
            55            printf("%d",pos[i]);
            56            if(i<fp-1)printf(" ");
            57            else printf("\n");
            58        }
            59    }
            60    return 1;
            61}
            62
            63
            

            Code2: 

             1            #include<stdio.h>
             2#define len 105
             3int map[len][len],max,cnt[len],group[len],m,n,k;
             4bool dfs(int num,int visit[len],int pos)
             5{
             6    int i,j;
             7    for(i=num+1;i<=n;i++)
             8    {
             9        if(cnt[i]+pos<=max) return false;//根據cnt[]數組的非遞增性可以直接返回false
            10        if(map[num][i])
            11        {
            12            for(j=0;j<pos;j++)if(map[i][visit[j]]==0)break ;
            13            if(j==pos)  //與當前完全圖的所有點都有邊，可以加進來
            14            {
            15               visit[pos]=i;
            16               if(dfs(i,visit,pos+1))return true;
            17            }
            18        }
            19    }
            20    if(pos>max)
            21    {
            22        int kk;
            23        for(kk=0;kk<pos;kk++)group[kk]=visit[kk];//更新最大完全圖的頂點集合
            24        max=pos;
            25        return true;//根據cnt[]數組的非遞增性可以直接返回true
            26    }
            27    return false;
            28}
            29void init()
            30{
            31    int i,j;
            32    for(i=1;i<=n;i++)
            33        for(j=1;j<=n;j++)
            34        {
            35            if(i!=j)map[i][j]=1;
            36            else map[i][j]=0;
            37        }
            38}
            39int main()
            40{
            41    int i,a,b,path[len];
            42    scanf("%d",&m);
            43    while(m--)
            44    {
            45        scanf("%d%d",&n,&k);
            46        init();
            47        for(i=1;i<=k;i++)
            48        {
            49            scanf("%d%d",&a,&b);
            50            map[a][b]=0;
            51            map[b][a]=0;
            52        }
            53
            54        max=-1;
            55        for(i=n;i>=1;i--)
            56        {
            57            path[0]=i;
            58            dfs(i,path,1);
            59            cnt[i]=max; 
            60        }
            61        printf("%d\n",cnt[1]);//打印出最大完全圖的頂點數
            62        for(i=0;i<cnt[1];i++)printf("%d ",group[i]);//打印出最大完全圖的頂點集合
            63        printf("\n");
            64    }
            65    return 1;
            66}
            

		
            
			posted on 2009-08-09 10:00 蝸牛也Coding 閱讀(326) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年8月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



三上悠亚久久精品|
色偷偷91久久综合噜噜噜噜|
亚洲αv久久久噜噜噜噜噜|
狠狠综合久久AV一区二区三区|
久久91精品国产91|
久久国产精品久久|
亚洲国产成人久久综合野外|
久久精品国产精品亚洲毛片|
国产精品美女久久久网AV|
欧美日韩精品久久久免费观看|
国产精品九九九久久九九|
日本精品久久久久影院日本|
久久综合狠狠综合久久|
久久精品成人影院|
777米奇久久最新地址|
亚洲国产精品狼友中文久久久|
av无码久久久久不卡免费网站|
久久久久亚洲精品天堂久久久久久
|
亚洲日本va中文字幕久久|
久久最新精品国产|
日韩av无码久久精品免费|
久久久久久国产精品免费免费|
99久久国语露脸精品国产|
18岁日韩内射颜射午夜久久成人|
国产AⅤ精品一区二区三区久久|
久久不见久久见免费视频7|
久久久久国产精品嫩草影院|
久久夜色精品国产亚洲av|
嫩草影院久久国产精品|
国产精品久久免费|
久久发布国产伦子伦精品|
人妻少妇久久中文字幕一区二区|
亚洲天堂久久久|
青青青国产精品国产精品久久久久
|
国产高清国内精品福利99久久|
欧洲成人午夜精品无码区久久|
奇米影视7777久久精品人人爽|
色婷婷久久综合中文久久一本|
日本欧美国产精品第一页久久|
久久久久久av无码免费看大片|
婷婷久久综合九色综合98|