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





            
	    
    




            






            

				

            


    
    







            
	   
	



色偷偷91久久综合噜噜噜噜|
久久精品无码一区二区无码|
久久久久久久久久免免费精品|
久久久久成人精品无码|
奇米影视7777久久精品人人爽|
一本久久知道综合久久|
一本大道加勒比久久综合|
久久精品国产久精国产果冻传媒|
国产成人久久精品激情|
久久一区二区三区99|
久久免费的精品国产V∧
|
无码人妻久久一区二区三区蜜桃|
中文无码久久精品|
久久九九久精品国产免费直播|
亚洲av成人无码久久精品|
久久久噜噜噜久久|
天天久久狠狠色综合|
看久久久久久a级毛片|
一级女性全黄久久生活片免费
|
无码人妻精品一区二区三区久久|
国产精品成人99久久久久|
久久精品人人做人人爽电影蜜月|
欧洲国产伦久久久久久久|
久久综合久久综合九色|
国产精品久久国产精品99盘
|
国产精品成人久久久久久久|
久久久久亚洲精品天堂|
一本久久知道综合久久|
久久人人爽人人爽人人片AV东京热|
久久久久亚洲?V成人无码|
久久99免费视频|
精品久久久久久久无码|
99久久99久久|
久久久久久久综合日本亚洲
|
色狠狠久久AV五月综合|
亚洲AV乱码久久精品蜜桃|
狠狠色狠狠色综合久久|
无码人妻精品一区二区三区久久
|
久久亚洲国产午夜精品理论片|
久久国产精品无码一区二区三区|
久久综合香蕉国产蜜臀AV|