• <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>

            POJ 3692 Kindergarten 二分圖最大獨立集

            Description

            In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.

            Input

            The input consists of multiple test cases. Each test case starts with a line containing three integers
            G, B (1 ≤ G, B ≤ 200) and M (0 ≤ MG × B), which is the number of girls, the number of boys and
            the number of pairs of girl and boy who know each other, respectively.
            Each of the following M lines contains two integers X and Y (1 ≤ X≤ G,1 ≤ Y ≤ B), which indicates that girl X and boy Y know each other.
            The girls are numbered from 1 to G and the boys are numbered from 1 to B.

            The last test case is followed by a line containing three zeros.

            Output

            For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the maximum number of kids the teacher can pick.

            Sample Input

            2 3 3
            1 1
            1 2
            2 3
            2 3 5
            1 1
            1 2
            2 1
            2 2
            2 3
            0 0 0

            Sample Output

            Case 1: 3
            Case 2: 4

            Source


                 

            本題是要求圖中的最大完全子圖(最大團)中頂點的個數。由于原圖的補圖是一個二分圖,其最大完全數等價于其補圖的最大獨立集中元素的個數,于是可以根據二分圖的性質求出這個最大獨立集。而普通圖的最大團則是一個NP問題。

            定理:二分圖最大獨立集=頂點數-二分圖最大匹配

            最大完全數:圖中最大完全子圖的頂點個數。

            獨立集:圖中任意兩個頂點都不相連的頂點集合。

            #include <iostream>
            using namespace std;

            const int MAXN = 201;
            bool visit[MAXN];
            int n,m,k,mark[MAXN];
            bool map[MAXN][MAXN];

            bool dfs(int u){
                
            int i;
                
            for(i=1;i<=m;i++)
                    
            if(map[u][i] && !visit[i]){
                        visit[i]
            =true;
                        
            if(mark[i]==-1 || dfs(mark[i])){
                            mark[i]
            =u;
                            
            return true;
                        }

                    }

                
            return false;
            }

            int hungary(){
                
            int i,ans=0;
                
            for(i=1;i<=n;i++){
                    memset(visit,
            false,sizeof(visit));
                    
            if(dfs(i)) ans++;
                }

                
            return ans;
            }

            int main(){
                
            int i,j,x,y,id=1;
                
            while(scanf("%d %d %d",&n,&m,&k),n||m||k){
                    
            for(i=1;i<=n;i++for(j=1;j<=m;j++) map[i][j]=true;
                    
            while(k--){
                        scanf(
            "%d %d",&x,&y);
                        map[x][y]
            =false;
                    }

                    memset(mark,
            -1,sizeof(mark));
                    printf(
            "Case %d: %d\n",id++,n+m-hungary());
                }

                
            return 0;
            }

            posted on 2009-06-02 15:14 極限定律 閱讀(2077) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久影视综合亚洲| 亚洲国产精品无码久久SM| 久久精品国产AV一区二区三区| 伊人久久大香线焦综合四虎| 久久久中文字幕日本| 国产69精品久久久久APP下载| 99久久国产综合精品女同图片| 久久久久99精品成人片欧美| 久久国产精品免费一区| 久久久久久久精品成人热色戒| 2021久久精品国产99国产精品| 久久久久国产视频电影| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 丁香五月网久久综合| 精品无码久久久久久久动漫| 99蜜桃臀久久久欧美精品网站| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 久久噜噜电影你懂的| 久久婷婷五月综合国产尤物app| 久久精品www| 久久精品aⅴ无码中文字字幕不卡| 亚洲一本综合久久| 国产V综合V亚洲欧美久久| 久久精品视频一| 狠狠色综合网站久久久久久久| 国产成人精品免费久久久久| 漂亮人妻被黑人久久精品| 亚洲国产精品综合久久一线| 久久精品国产欧美日韩| 久久久青草青青亚洲国产免观| 久久久久久伊人高潮影院| 久久国产香蕉一区精品| 国内精品久久久久久久涩爱 | 亚洲午夜久久久影院| 欧美一区二区久久精品| 性做久久久久久久久浪潮| 午夜精品久久久久久影视777| 一级女性全黄久久生活片免费| 女同久久| 伊人精品久久久久7777| 亚洲第一永久AV网站久久精品男人的天堂AV |