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

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, 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 閱讀(535) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美一级淫片播放口| 日韩午夜高潮| 久久裸体视频| 久久免费国产| 亚洲美女在线观看| 99在线热播精品免费| 国产精品乱子久久久久| 欧美一区二区精品| 久久久久久69| 亚洲精品久久久蜜桃| 在线视频你懂得一区| 国产农村妇女精品一区二区| 久久九九国产精品| 久久人人97超碰精品888| 91久久夜色精品国产九色| 亚洲乱码国产乱码精品精天堂 | 欧美第一黄色网| 亚洲视频在线观看一区| 性欧美xxxx视频在线观看| 亚洲国产日韩一级| 亚洲视频一区二区免费在线观看| 国产乱码精品| 亚洲国产裸拍裸体视频在线观看乱了| 欧美激情国产日韩| 久久精品国产69国产精品亚洲| 久久亚洲国产精品一区二区| 亚洲免费高清视频| 欧美影院在线| 亚洲视频一二| 欧美插天视频在线播放| 亚洲欧美中日韩| 欧美激情va永久在线播放| 午夜精品视频网站| 欧美xx69| 久久综合给合久久狠狠狠97色69| 欧美另类变人与禽xxxxx| 久久婷婷人人澡人人喊人人爽| 欧美日韩国产成人| 欧美aaaaaaaa牛牛影院| 国产精品一区二区三区久久久| 亚洲国产一区二区三区高清| 国产日韩在线亚洲字幕中文| 99re66热这里只有精品4| 在线播放中文字幕一区| 中文日韩在线| 一区二区三区高清在线观看| 久久久久久亚洲精品中文字幕| 亚洲欧美日韩中文播放| 欧美久久婷婷综合色| 欧美成人激情在线| 激情综合电影网| 欧美亚洲综合在线| 欧美一区二粉嫩精品国产一线天| 欧美日韩国产一区二区三区| 欧美大片第1页| 亚洲高清一区二区三区| 久久久久久久综合| 久久综合九色综合欧美就去吻 | 国产精品乱码妇女bbbb| 亚洲美女诱惑| 一区二区三区欧美| 欧美日韩另类一区| 夜夜爽99久久国产综合精品女不卡| 91久久久久久久久| 欧美精品一区视频| 亚洲毛片在线免费观看| 亚洲午夜电影网| 欧美色中文字幕| 亚洲午夜精品17c| 欧美在线观看视频在线| 欧美日韩一区二区免费在线观看| 亚洲老板91色精品久久| 亚洲视频观看| 国产精品自拍一区| 久久国产精品久久久久久电车| 久久九九免费| 亚洲第一天堂av| 欧美极品aⅴ影院| 亚洲精品久久久蜜桃 | 国产一区二区三区在线观看免费视频| 午夜精品久久久久| 久久综合色8888| 亚洲人成网站在线观看播放| 欧美国产视频在线| 亚洲桃色在线一区| 久久天天综合| 日韩视频在线观看一区二区| 欧美午夜无遮挡| 久久激情婷婷| 亚洲精品资源| 久久国产一区| 99国产成+人+综合+亚洲欧美| 欧美日韩一卡二卡| 久久国产一区二区三区| 亚洲人成77777在线观看网| 亚洲在线一区| 在线精品视频一区二区三四| 欧美日韩dvd在线观看| 亚洲女优在线| 亚洲欧洲精品一区二区三区| 午夜精品久久久久久久久久久| 黄色av一区| 欧美婷婷在线| 美女在线一区二区| 午夜久久福利| 日韩一区二区精品| 欧美成人蜜桃| 久久黄色网页| 亚洲一区二区三| 亚洲精品乱码视频| 国产午夜精品一区二区三区欧美| 欧美国产精品| 久久人人看视频| 亚洲免费网站| 制服丝袜亚洲播放| 亚洲欧洲一区二区在线播放| 久久国产天堂福利天堂| 中日韩午夜理伦电影免费| 亚洲第一页自拍| 国产欧美日韩三区| 欧美日韩亚洲视频一区| 免费成人高清视频| 久久成人久久爱| 午夜精品久久久久久久99热浪潮| 亚洲激情社区| 亚洲国产精品第一区二区| 久久天天躁夜夜躁狠狠躁2022 | 亚洲免费观看高清完整版在线观看熊| 国产日韩欧美一区在线| 国产精品乱码人人做人人爱| 欧美日韩www| 欧美乱人伦中文字幕在线| 蜜臀久久99精品久久久久久9| 欧美一区免费| 欧美在线一区二区| 欧美一级理论性理论a| 亚洲伊人久久综合| 亚洲一区二区三区久久| 在线亚洲精品| 亚洲字幕一区二区| 亚洲小视频在线观看| 亚洲午夜极品| 香蕉av福利精品导航| 午夜日本精品| 久久精彩免费视频| 久久午夜国产精品| 暖暖成人免费视频| 欧美精品aa| 国产精品chinese| 国产欧美一区二区三区沐欲| 国产欧美日韩不卡免费| 国产人妖伪娘一区91| 国产视频久久| 亚洲韩国青草视频| 一本久道久久久| 午夜精品久久久久久久蜜桃app| 亚洲欧美日韩成人| 久久精品国产精品| 欧美v亚洲v综合ⅴ国产v| 欧美激情中文字幕一区二区| 亚洲国产综合91精品麻豆| 亚洲精品资源美女情侣酒店| 99re66热这里只有精品3直播| 亚洲一区二区毛片| 久久久久久夜| 欧美日韩一区二区在线观看视频| 国产精品入口福利| 在线免费观看日韩欧美| 一区二区精品| 久久久精品免费视频| 亚洲国内欧美| 午夜精品免费| 欧美国产亚洲视频| 国产欧美日韩一级| 亚洲精品一线二线三线无人区| 亚洲天堂av高清| 麻豆av一区二区三区| 99国产精品久久久久久久| 久久国产精品久久久| 欧美日韩视频专区在线播放| 国产一区999| 亚洲一区二区三区视频| 美女日韩欧美| 亚洲一区二区三区乱码aⅴ| 浪潮色综合久久天堂| 国产精品久久久久久久久动漫| 亚洲高清在线精品| 欧美一区网站| 一本一本久久| 欧美高清你懂得| 黄色av成人| 久久av一区二区三区| 亚洲伦理网站| 欧美wwwwww| 亚洲第一精品电影| 久久久精品国产免大香伊| 亚洲图片欧美日产| 欧美日本国产一区| 亚洲精品国久久99热| 久久综合精品一区|