注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2458  

2012-07-28 01:55:05|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=2458

本题是要求图中的最大完全子图中顶点的个数

由于原图的补图是一个二分图,其最大完全数等价于其补图的最大独立集中元素的个数,于是可以根据二分图的性质求出这个最大独立集。而普通图的最大团则是一个NP问题。
定理:二分图最大独立集中元素个数=顶点数-二分图最大匹配数
最大完全数:图中最大完全子图的顶点个数。
独立集:图中任意两个顶点都不相连的顶点集合。

/*
 * fudq.cpp
 *
 *  Created on: 2012-07-27
 *      Author: fudq
 *  最大独立集=V-最大匹配数
 */
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
#define N 500
bool f[N][N];
int n, m,Link[N];
bool vis[N];

bool Find(int a)
{
    int i;
    for(i=1;i<=m;i++)
    {
        if(!f[a][i] && !vis[i])//由于是求补图,所以这里的f[a][i]要等于0
        {
            vis[i]=1;
            if(Link[i]==0 || Find(Link[i]))
            {
                Link[i]=a;
                return true;
            }
        }
    }
    return false;
}

int maxmatch() {
    int i, res = 0;
    memset(Link, 0, sizeof(Link));
    for (i = 1; i <=n; i++) {
        memset(vis, false, sizeof(vis));
        if (Find(i))
            res++;
    }
    return res;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("testin.txt", "r", stdin);
#endif
    int i, b,a,T,cas=1;
    while (scanf("%d%d%d", &n,&m,&T)!=EOF) {
     if(n==0 && m==0 && T==0)
      break;
        memset(f,false,sizeof(f));
        for (i = 1; i <=T; i++)
        {
            scanf("%d%d",&a,&b);
            f[a][b]=true;
        }
        printf("Case %d: %d\n",cas++,n+m-maxmatch());
    }
    return 0;
}

  评论这张
 
阅读(164)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018