前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 3829 Cat VS Dog(二分图最大独立集)

HDU 3829 Cat VS Dog(二分图最大独立集)

作者头像
Ch_Zaqdt
发布2019-01-10 16:24:00
5110
发布2019-01-10 16:24:00
举报
文章被收录于专栏:Zaqdt_ACM

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3829

       题意是动物园里有n只猫,m只狗,然后有p个小朋友,每个小朋友都有一种喜欢的动物和一种不喜欢的动物,如果他喜欢猫,他就一定不喜欢狗,然后管理员现在要清除一些动物,如果一个小朋友喜欢的动物没有被清除,而不喜欢的动物被清除了他就会很开心,问最多能让多少个小朋友开心。

       思路就是如果一个小朋友喜欢的动物是另一个小朋友不喜欢的,或者他不喜欢的动物是另一个小朋友喜欢的,就说明他们矛盾,所以我们给他俩加一条边,然后去跑一个最大独立集(也就是最多保留多少个小朋友)就好了。


AC代码:

代码语言:javascript
复制
#include <bits/stdc++.h>
#define maxn 505 * 505
using namespace std;
struct Node{
    int to,next;
}Edge[maxn];
struct node{
    string str_l, str_d;
}edge[maxn];
int head[maxn],num;
int pre[maxn];
bool vis[maxn];
int n,m,p,cnt;

void init(){
    memset(head,-1,sizeof(head));
    num = 0;
}

void add(int u, int v){
    Edge[num].to = v;
    Edge[num].next = head[u];
    head[u] = num ++;
}

bool dfs(int u){
    for(int i=head[u];i!=-1;i=Edge[i].next){
        int v = Edge[i].to;
        if(!vis[v]){
            vis[v] = true;
            if(pre[v] == -1 || dfs(pre[v])){
                pre[v] = u;
                return true;
            }
        }
    }
    return false;
}

int solve(){
    int sum = 0;
    memset(pre,-1,sizeof(pre));
    for(int i=1;i<=p;i++){
        memset(vis,false,sizeof(vis));
        if(dfs(i)) sum ++;
    }
    return sum;
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&p)){
        init();
        for(int i=1;i<=p;i++){
            cin>>edge[i].str_l>>edge[i].str_d;
        }
        for(int i=1;i<=p;i++){
            for(int j=1;j<=p;j++){
                if(edge[i].str_l == edge[j].str_d || edge[i].str_d == edge[j].str_l){
                    add(i, j);
                }
            }
        }
        int ans = solve();
        printf("%d\n",p - ans / 2);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年11月28日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档