• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 2069 Asteroids
		
            
		
             1/*
             2EOJ 2069 Asteroids
             3
             4
             5----問題描述：
             6
             7Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500).
             8The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.
             9
            10Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.
            11This weapon is quite expensive, so she wishes to use it sparingly.
            12Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.
            13
            14
            15----輸入：
            16
            17* Line 1: Two integers N and K, separated by a single space.
            18* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.
            19
            20
            21----輸出：
            22* Line 1: The integer representing the minimum number of times Bessie must shoot.
            23
            24
            25----樣例輸入：
            26
            273 4
            281 1
            291 3
            302 2
            313 2
            32
            33
            34----樣例輸出：
            35
            362
            37
            38
            39----分析：
            40
            41建立二分圖模型，
            42若第 i 行和第 j 列處存在一個 asteroid ，則 x[i] 與 y[j] 連一條邊，
            43求二分圖最大匹配，使用匈牙利算法。
            44
            45*/
            46
            47
            48#include <stdio.h>
            49#include <string.h>
            50
            51#define  L  503
            52
            53int adj[ L ][ L ], n, state[ L ], result[ L ];
            54
            55int find( int i ) {
            56        int j, k;
            57        for ( j = adj[ i ][ 0 ]; j > 0; --j ) {
            58                k = adj[ i ][ j ];
            59                if ( state[ k ] == 0 ) {
            60                        state[ k ] = 1;
            61                        if ( ( result[ k ] == 0 ) || find( result[ k ] ) ) {
            62                                result[ k ] = i;
            63                                return 1;
            64                        }
            65                }
            66        }
            67        return 0;
            68}
            69
            70int maxMatch() {
            71        int ans = 0, i;
            72        for ( i = 1; i <= n; ++i ) {
            73                memset( state, 0, sizeof( state ) );
            74                if ( find( i ) )
            75                        ++ans;
            76        }
            77        return ans;
            78}
            79
            80int main() {
            81        int i, j, k;
            82        memset( adj, 0, sizeof( adj ) );
            83        memset( result, 0, sizeof( result ) );
            84        scanf( "%d%d", &n, &k );
            85        while ( k-- ) {
            86                scanf( "%d%d", &i, &j );
            87                adj[ i ][ ++adj[ i ][ 0 ] ] = j;
            88        }
            89        printf( "%d\n", maxMatch() );
            90        return 0;
            91}
            92
            
		
            
			posted on 2012-03-30 22:18 coreBugZJ 閱讀(525) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



日韩一区二区三区视频久久|
亚洲а∨天堂久久精品|
久久午夜综合久久|
亚洲日本久久久午夜精品|
久久亚洲视频|
无码人妻久久一区二区三区免费丨|
久久婷婷五月综合色奶水99啪|
无码伊人66久久大杳蕉网站谷歌|
久久久久AV综合网成人|
97久久精品人人做人人爽|
欧美亚洲国产精品久久|
婷婷久久香蕉五月综合加勒比|
国产成人精品久久免费动漫|
久久伊人五月丁香狠狠色|
国产国产成人久久精品|
精品久久久无码人妻中文字幕豆芽
|
国产激情久久久久影院|
久久福利资源国产精品999|
日本精品久久久久中文字幕8|
精品久久久久久无码中文字幕一区|
国产成人精品久久亚洲高清不卡|
伊人久久大香线蕉亚洲五月天
|
久久精品国产2020|
精品无码人妻久久久久久|
久久久久久久尹人综合网亚洲
|
99久久精品国产一区二区三区
|
久久精品国产清自在天天线|
91精品国产高清久久久久久io|
亚洲国产精品综合久久网络|
久久亚洲av无码精品浪潮|
91精品国产综合久久精品|
亚洲国产精品成人久久|
中文字幕无码久久人妻|
久久99国产精品成人欧美|
久久久青草久久久青草|
丰满少妇高潮惨叫久久久|
人妻精品久久无码区|
久久无码av三级|
精品久久久久久亚洲|
久久久久亚洲爆乳少妇无|
伊人久久综在合线亚洲2019|