• <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 閱讀(524) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



国产精品九九久久精品女同亚洲欧美日韩综合区
|
久久人人爽人人爽人人AV东京热|
精品久久久久久中文字幕大豆网
|
亚洲精品乱码久久久久久蜜桃
|
香蕉久久影院|
久久亚洲春色中文字幕久久久|
久久成人精品视频|
久久久久久青草大香综合精品|
少妇无套内谢久久久久|
99久久国产宗和精品1上映|
日本免费一区二区久久人人澡|
久久久久一本毛久久久|
国产国产成人精品久久|
久久久久久无码国产精品中文字幕|
欧美牲交A欧牲交aⅴ久久|
国产精品成人99久久久久91gav|
久久久久久久波多野结衣高潮
|
91精品国产91久久综合|
欧美成a人片免费看久久|
国产成人精品久久免费动漫|
久久受www免费人成_看片中文|
93精91精品国产综合久久香蕉|
久久精品国产亚洲AV不卡|
99久久国产综合精品五月天喷水|
精品无码久久久久久尤物|
亚洲精品高清一二区久久|
国产亚洲色婷婷久久99精品91|
久久久久久九九99精品|
中文无码久久精品|
日日狠狠久久偷偷色综合0|
色综合久久综合网观看|
久久久久久免费一区二区三区|
亚洲精品无码久久千人斩|
中文字幕久久精品|
久久久国产99久久国产一|
亚洲&#228;v永久无码精品天堂久久
|
久久久久人妻精品一区|
久久精品久久久久观看99水蜜桃
|
久久久无码精品亚洲日韩软件|
亚洲综合婷婷久久|
免费国产99久久久香蕉|