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

            為生存而奔跑

               :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
              271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

            留言簿(5)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            積分與排名

            • 積分 - 328415
            • 排名 - 74

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            獨(dú)立集:任意兩點(diǎn)都不相連的頂點(diǎn)的集合
            獨(dú)立數(shù):獨(dú)立集中頂點(diǎn)的個(gè)數(shù)

            完全子圖:任意兩點(diǎn)都相連的頂點(diǎn)的集合
            最大完全數(shù):最大完全子圖中頂點(diǎn)的個(gè)數(shù)

            最大完全數(shù)=原圖的補(bǔ)圖的最大獨(dú)立數(shù)
            最大獨(dú)立數(shù)=頂點(diǎn)數(shù)-最大匹配數(shù)

            這樣,就可以求出最大完全數(shù)

            PKU 3692
             1#include<iostream>
             2#include<algorithm>
             3using namespace std;
             4#define maxn 210
             5#define max(x,y) ((x)>(y)?(x):(y))
             6bool map[maxn][maxn],mark[maxn] ;
             7int nx,ny,cx[maxn],cy[maxn];
             8int path(int u)
             9{
            10    for (int v = 1;v <= ny; v++
            11        if (map[u][v] && !mark[v])
            12        {
            13            mark[v] = 1 ;
            14            if (cy[v] == -1 || path(cy[v])) 
            15            {
            16                cx[u] = v ; 
            17                cy[v] = u ; 
            18                return 1 ;
            19            }

            20        }

            21    return 0 ;
            22}

            23int MaxMatch()
            24{
            25    int res=0 ;
            26    memset(cx , 0xff , sizeof(cx)) ;
            27    memset(cy , 0xff , sizeof(cy)) ;
            28    for (int i = 1 ; i <= nx ; i++
            29        if (cx[i] == -1
            30        {
            31            memset(mark , 0 , sizeof(mark)) ;
            32            res += path(i) ; 
            33        }

            34    return res ;
            35}

            36int main()
            37{
            38    int g,b,m,x,y,k;
            39    k=1;
            40    while(scanf("%d%d%d",&g,&b,&m)!=EOF)
            41    {
            42        if(g==0&&b==0&&m==0)
            43            break;
            44        nx=g,ny=b;
            45        for(int i=1;i<=g;i++)
            46            for(int j=1;j<=b;j++)
            47                map[i][j]=1;
            48        while(m--)
            49        {
            50            scanf("%d%d",&x,&y);
            51            map[x][y]=0;
            52        }

            53        printf("Case %d: %d\n",k++,g+b-MaxMatch());
            54    }

            55}
            posted on 2009-07-27 15:13 baby-fly 閱讀(1475) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Algorithm
            久久久www免费人成精品| 亚洲国产成人久久一区久久| 精品久久久久久久中文字幕| 久久99精品久久只有精品 | 国产亚洲精久久久久久无码| 国产A三级久久精品| 香蕉99久久国产综合精品宅男自 | 久久超乳爆乳中文字幕| 日韩精品久久无码人妻中文字幕| 久久人与动人物a级毛片| 久久强奷乱码老熟女网站| 国产精品久久久久久久久软件| 久久久久无码精品| 亚洲人AV永久一区二区三区久久| 久久久久香蕉视频| 波多野结衣久久精品| 日韩精品久久无码中文字幕| 韩国免费A级毛片久久| 狠狠色丁香久久综合婷婷| 91精品无码久久久久久五月天| www亚洲欲色成人久久精品| 亚洲国产一成久久精品国产成人综合 | 欧美亚洲另类久久综合婷婷| 久久天天躁夜夜躁狠狠| 77777亚洲午夜久久多喷| 精品多毛少妇人妻AV免费久久| 久久无码AV中文出轨人妻| 亚洲va中文字幕无码久久不卡| 999久久久无码国产精品| 久久久久亚洲AV无码专区网站| 国产成人精品久久| 久久国产精品免费| 久久亚洲中文字幕精品有坂深雪 | 色综合久久中文字幕综合网 | 亚洲欧美成人综合久久久| 亚洲精品国产成人99久久| 亚洲精品午夜国产va久久| 久久ZYZ资源站无码中文动漫| 久久国产香蕉视频| 国产美女久久精品香蕉69| 日日狠狠久久偷偷色综合0|