青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

EOJ 2069 Asteroids

 1/*
 2EOJ 2069 Asteroids
 3
 4
 5----問(wèn)題描述:
 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 列處存在一個(gè) 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, 0sizeof( state ) );
74                if ( find( i ) )
75                        ++ans;
76        }

77        return ans;
78}

79
80int main() {
81        int i, j, k;
82        memset( adj, 0sizeof( adj ) );
83        memset( result, 0sizeof( 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 閱讀(544) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM 、Algorithm課內(nèi)作業(yè)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美3dxxxxhd| 午夜一区二区三区在线观看| 国产精品久久国产愉拍| 久久亚洲私人国产精品va媚药 | 亚洲三级免费电影| 久久免费视频在线观看| 亚洲自拍偷拍麻豆| 亚洲理论电影网| 亚洲电影免费观看高清| 国产日韩欧美夫妻视频在线观看| 欧美激情中文字幕乱码免费| 久久婷婷麻豆| 久久不射电影网| 亚洲欧美日本国产专区一区| 亚洲最新在线视频| 亚洲国产欧美一区二区三区丁香婷| 久久久久国产精品一区二区| 性伦欧美刺激片在线观看| 亚洲视频中文字幕| 中文在线资源观看网站视频免费不卡| 亚洲国产黄色片| 伊人久久综合97精品| 国产亚洲欧美日韩一区二区| 国产精品爽爽爽| 国产精品永久| 国产精品日韩在线| 国产精品蜜臀在线观看| 国产精品videosex极品| 欧美色视频在线| 欧美无砖砖区免费| 国产精品v欧美精品v日韩 | 欧美伊人久久久久久久久影院 | 亚洲精品免费网站| 亚洲黄色大片| 亚洲激情精品| 亚洲美女精品一区| 一区二区三区久久精品| av成人老司机| 亚洲一区二区视频| 香蕉亚洲视频| 久久久久成人精品| 快射av在线播放一区| 美女图片一区二区| 欧美精品国产一区二区| 欧美精品九九99久久| 欧美日韩在线视频一区| 国产精品色婷婷久久58| 国产一区二区精品久久91| 1024精品一区二区三区| 亚洲欧洲日产国码二区| 99一区二区| 午夜精品av| 久久久久免费视频| 欧美国产日韩亚洲一区| 亚洲毛片在线| 亚洲欧美美女| 久久躁狠狠躁夜夜爽| 欧美精品在线免费观看| 国产精品色婷婷久久58| 韩国一区二区在线观看| 91久久夜色精品国产九色| 中文日韩在线| 久久久欧美一区二区| 亚洲国产成人久久| 亚洲综合成人婷婷小说| 久久久久久久精| 欧美日韩国产一区精品一区| 国产免费观看久久黄| 亚洲国产日韩综合一区| 亚洲综合三区| 免费久久久一本精品久久区| 亚洲精品一区二区三区在线观看 | 国产精品一区二区视频| 在线观看一区| 亚洲综合电影一区二区三区| 久久久噜噜噜久久中文字幕色伊伊 | 国产欧美一区二区精品秋霞影院 | 亚洲精品国产日韩| 性久久久久久久久久久久| 美女视频黄a大片欧美| 欧美性一二三区| 亚洲成色www久久网站| 亚洲免费在线| 亚洲国产精品999| 午夜久久一区| 欧美日韩一区二区三区四区五区| 国产一区二区三区丝袜| 一本久久知道综合久久| 久久精品日韩| 日韩亚洲欧美一区二区三区| 欧美在线视频一区二区| 欧美午夜电影网| 亚洲国产精品一区二区第一页| 亚洲自拍16p| 亚洲国产精品精华液网站| 欧美一区二视频| 欧美性色aⅴ视频一区日韩精品| 在线视频国产日韩| 久久久精品动漫| 亚洲天堂网在线观看| 欧美精品在线一区二区| 亚洲成在人线av| 久久精品国产清自在天天线| 99一区二区| 欧美精品在线免费| 91久久久久久国产精品| 快射av在线播放一区| 欧美一区=区| 国产精品久久久久久久久久久久久 | 亚洲午夜免费福利视频| 欧美日韩国产二区| 一区在线播放| 欧美影院久久久| 亚洲一区二区三区四区五区黄| 欧美精品乱码久久久久久按摩| 在线观看视频一区| 久久久久久夜| 欧美一区二区在线免费播放| 国产美女精品| 亚洲欧美日韩视频一区| 一区二区成人精品| 欧美日韩美女一区二区| 亚洲最新合集| 亚洲精品少妇30p| 欧美日本国产视频| 99精品国产一区二区青青牛奶| 欧美成人精品一区二区三区| 久久精品一区二区| 韩日欧美一区| 女人天堂亚洲aⅴ在线观看| 久久精品99无色码中文字幕| 国产一区二区三区免费不卡| 久久精品亚洲乱码伦伦中文 | 欧美一区永久视频免费观看| 亚洲手机成人高清视频| 国产精品乱子久久久久| 亚洲欧美色婷婷| 亚洲午夜在线观看| 国产欧美日韩视频| 久久久久女教师免费一区| 久久精品五月| 亚洲黄色av一区| 亚洲日本视频| 国产精品麻豆成人av电影艾秋| 午夜视频一区在线观看| 欧美一区二区三区精品| 伊人久久婷婷| 亚洲国产天堂久久国产91| 欧美区二区三区| 午夜久久资源| 久久久久亚洲综合| 亚洲精品久久久久久久久久久久| 亚洲精品久久7777| 国产精品手机视频| 蜜桃av综合| 欧美欧美午夜aⅴ在线观看| 亚洲免费影视第一页| 欧美在线免费| 亚洲免费大片| 午夜精品久久久久久久久| 在线免费观看视频一区| 亚洲精品视频一区| 国产视频久久| 亚洲黄一区二区三区| 国产精品区一区二区三区| 免费不卡在线视频| 欧美色欧美亚洲另类二区| 久久久久久久久久久久久久一区 | 国产视频久久久久| 欧美搞黄网站| 国产精品三区www17con| 欧美成人精品激情在线观看| 欧美亚洲成人精品| 蜜臀va亚洲va欧美va天堂| 欧美激情一区二区三区在线视频| 香蕉久久夜色精品国产| 欧美成人激情视频| 欧美在线地址| 欧美日韩福利| 美乳少妇欧美精品| 国产精品久久一区主播| 欧美黄免费看| 国产亚洲精品aa| 亚洲精品一区二区网址| 韩日午夜在线资源一区二区| a91a精品视频在线观看| 亚洲国产美女| 亚洲免费视频成人| a91a精品视频在线观看| 久久久久久9| 欧美一区二视频| 欧美日本不卡高清| 女人香蕉久久**毛片精品| 国产乱子伦一区二区三区国色天香| 亚洲高清色综合| 伊人久久久大香线蕉综合直播| 亚洲天堂偷拍| 在线亚洲欧美专区二区| 嫩草伊人久久精品少妇av杨幂| 久久成人这里只有精品|