• <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 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



亚洲综合久久久|
久久国产综合精品五月天|
香蕉99久久国产综合精品宅男自|
午夜精品久久久久9999高清|
一本色道久久99一综合|
国内精品久久久久国产盗摄|
国产精品99精品久久免费|
伊人久久大香线蕉无码麻豆|
久久精品国产亚洲Aⅴ蜜臀色欲|
国产成人无码精品久久久免费
|
99久久精品国产毛片|
中文字幕乱码久久午夜|
国产精品久久亚洲不卡动漫|
久久精品人人做人人妻人人玩|
久久精品中文无码资源站|
日产精品久久久久久久|
亚洲国产精品成人久久蜜臀
|
久久夜色精品国产欧美乱|
亚洲精品无码久久久|
久久夜色精品国产噜噜亚洲AV|
久久综合亚洲色HEZYO国产|
久久久噜噜噜久久中文字幕色伊伊|
久久久久久久女国产乱让韩|
青青青国产成人久久111网站|
99久久精品费精品国产|
精品无码久久久久久午夜|
久久久久亚洲AV无码专区首JN|
成人精品一区二区久久久|
日产精品久久久一区二区|
色综合久久久久综合99|
91久久精品电影|
久久婷婷久久一区二区三区|
久久综合香蕉国产蜜臀AV|
久久久久久精品无码人妻|
久久成人小视频|
久久99热这里只频精品6|
中文字幕精品无码久久久久久3D日动漫
|
狠狠人妻久久久久久综合蜜桃|
国产一久久香蕉国产线看观看|
精品国产一区二区三区久久|
潮喷大喷水系列无码久久精品|