• <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精品国产99久久6|
久久精品国产99国产精品亚洲|
久久久久亚洲Av无码专|
久久久久人妻一区精品色
|
久久99热狠狠色精品一区|
久久香蕉一级毛片|
久久精品一区二区三区中文字幕
|
久久久WWW成人免费精品|
久久精品中文字幕一区|
国产精品午夜久久|
久久综合噜噜激激的五月天|
香蕉久久永久视频|
久久亚洲国产欧洲精品一|
亚洲午夜久久久久久久久电影网|
久久99精品国产99久久|
久久久久久精品无码人妻|
狠狠精品干练久久久无码中文字幕|
精品国产青草久久久久福利|
91精品国产91久久久久久蜜臀|
中文精品久久久久人妻不卡|
九九久久精品国产|
国产精品99久久99久久久|
无码超乳爆乳中文字幕久久|
久久精品国产男包|
久久www免费人成精品香蕉|
久久噜噜电影你懂的|
国产一级做a爰片久久毛片|
91久久成人免费|
国产精品免费久久|
久久夜色精品国产www|
激情久久久久久久久久|
久久精品一区二区影院|
久久久青草青青国产亚洲免观|
国产毛片久久久久久国产毛片
|
东京热TOKYO综合久久精品|
亚洲综合精品香蕉久久网|
免费精品国产日韩热久久|
区久久AAA片69亚洲|
777午夜精品久久av蜜臀|
亚洲日本va中文字幕久久|
久久天堂AV综合合色蜜桃网|