CQUPT 集训队专题训练（二分图）

二分图

题目链接

A - COURSES

题意

　有ｐ个门课，n个学生
请问能不能让由一个p个学生组成的集合，使得p个学生与p门门一一对应，即每门课都有不同的学生，每个学生都选了不同的课

思路

二分图最大匹配数 == p的时候满足条件

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
const int N = 307;

vector<int> map[N];
int p[N];
bool use[N];

bool dfs(int u){
    for(int i = 0 ; i < map[u].size() ; i++){
        if( !use[map[u][i]] ){
            use[map[u][i]] = true;
            if( p[map[u][i]] == -1 || dfs(p[map[u][i]]) ){
                p[map[u][i]] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian(int n){
    int ans = 0;

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

int main(){
    int t,n,m,x,y;
    scanf("%d",&t);
    while( t-- ){
        scanf("%d%d",&n,&m);
        memset(p,-1,sizeof(p));
        for(int i = 0 ; i <= n ; i++)   map[i].clear();     
        for(int i = 1 ; i <= n ; i++){
            scanf("%d",&x);
            for(int k = 1 ; k <= x ; k++)   scanf("%d",&y) , map[i].push_back(y);
        }
        if( n == hungarian(n) )
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
} 

B - The Accomodation of Students

题意

有n个学生，有m对人是认识的，每一对认识的人能分到同一组，不认识的人分到统一部分，能不能将n个人分成两部分，使得不同部分的两个相互认识人组队，最大组队数是多少？

思路

用染色法判断这是不是一个二分图
先标记一个为1，那么所有他认识的都标记为2，所有认识2的都标记为1，如果标记相同的相互认识就不是二分图，否则就是二分图
然后最大匹配数的1/2就是组数

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <set> 
using namespace std;
const int N = 207;

vector<int> s[N];
int p[N];
int color[N];

void cc(){
    for(int i = 0 ; i <= N ; i++)   s[i].clear();
}

bool pd_tf(int u){
    for(int i = 0 ; i < s[u].size(); i++){
        if( color[s[u][i]] == color[u] )    return false;
        if( !color[s[u][i]] ){
            color[s[u][i]] = 3 - color[u];
            if( !pd_tf(s[u][i]) ){
                return false;
            }
        }
    }
    return true;
}

bool dfs(int u){
    for(int i = 0 ; i < s[u].size(); i++){
        if( 0 == color[s[u][i]] ){
            color[s[u][i]] = 1;
            if( p[s[u][i]] == -1 || dfs(p[s[u][i]]) ){
                p[s[u][i]] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian(int n){
    int ans = 0;

    for(int i = 1 ; i <= n ; i++){
        memset(color,0,sizeof(color));
        if( dfs(i) )
            ans++;
    }
    return ans/2;
}

int main(){
    int n,m,a,b;
    while( scanf("%d%d",&n,&m) != EOF ){
        cc();
        for(int i = 0 ; i < m ; i++)    scanf("%d%d",&a,&b),s[a].push_back(b), s[b].push_back(a);
        memset(color,0,sizeof(color));
        color[1] = 1;
        if( !pd_tf(1) ){
            printf("No\n");
            continue;
        }
        memset(p,-1,sizeof(p));
        printf("%d\n",hungarian(n));
    }
    return 0;
} 

D - Machine Schedule

题意

给出一系列任务，每个任务可以在机器A的某个模式，或者在机器B的某个模式下完成。机器A和B每切换一次模式需要重启一次。问完成这些任务，最少需要重启机器多少次？
两个机器的初始方式默认为0

思路

把任务需要A的工作模式与B的工作模式封装为一条边，则两台机器工作模式为点，这就转化为最小点覆盖的问题，其中最小点覆盖就是最大匹配

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <set> 
using namespace std;
const int N = 110;

vector<int> v[N];
int p[N];
bool use[N];

bool dfs(int u){
    for(int i = 0 ; i < v[u].size() ; i++){
        if( !use[v[u][i]] ){
            use[v[u][i]] = true;
            if( p[v[u][i]] == -1 || dfs(p[v[u][i]]) ){
                p[v[u][i]] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian(int n){
    int ans = 0;
    memset(p,-1,sizeof(p));
    for(int i = 0 ; i < n ; i++){
        memset(use,false,sizeof(use));
        if( dfs(i) )    ans++;
    }
    return ans;
}

int main(){
    int n,m,k,a,b,c;
    while( scanf("%d",&n) != EOF && n ){
        scanf("%d%d",&m,&k);
        for(int i = 0 ; i < N ; i++)    v[i].clear();
        for(int i = 0 ; i < k ; i++){
            scanf("%d%d%d",&a,&b,&c);
            if( b == 0 || c == 0 )  continue; 
            v[b].push_back(c);
        }

        printf("%d\n",hungarian(n));
    }
    return 0;
} 

E - Cat VS Dog

题意

猫狗大战
一群喜欢猫的孩子和喜欢狗的孩子在动物园玩
现在动物园动物太多了，要移出一部分猫或狗
而每一个孩子都喜欢某一只动物而讨厌另一只动物
如果孩子喜欢的动物没被移走而不喜欢的动物没移走他就很开心
请问移动后开心的孩子最多能到达多少个

思路

最大独立集
以孩子建图，把每个孩子分成两半
然后把喜欢对方讨厌的，讨厌对方喜欢的建立一条无向边
然后求最大匹配
答案就是总数-最大匹配数的一半

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <set> 
using namespace std;
const int N = 507;

struct chi{
    char like[110] , dislike[110];
};

vector<int> v[N];
chi c[N];
int p[N];
bool use[N];

void creat_pic(int n){
    for(int i = 0 ; i <= n ; i++)   v[i].clear();
    for(int i = 1 ; i <= n ; i++)
        for(int k = 1 ; k <= n ; k++)
            if( strcmp(c[i].like,c[k].dislike) == 0 || strcmp(c[i].dislike,c[k].like) == 0 )
                v[i].push_back(k) , v[k].push_back(i);
}

int dfs(int u){
    for(int i = 0 ; i < v[u].size() ; i++){
        if( !use[v[u][i]] ){
            use[v[u][i]] = true;
            if( p[v[u][i]] == -1 || dfs(p[v[u][i]]) ){
                p[v[u][i]] = u;
                return 1;
            }
        }
    }
    return 0;
}

int hungarian(int n){
    int ans = 0;
    memset(p,-1,sizeof(p));
    for(int i = 1 ; i <= n ; i++)   memset(use,false,sizeof(use)), ans += dfs(i);
    return ans;
}

int main(){
    int cat,dog,child;
    while( scanf("%d%d%d",&cat,&dog,&child) != EOF ){
        for(int i = 1 ; i <= child ; i++)   scanf("%s %s",c[i].like,c[i].dislike);
        creat_pic(child);
        printf("%d\n",child - hungarian(child) / 2);
    }
    return 0;
} 

F - Antenna Placement

题意

有N座城市，在地图上*表示
每座城市可以建立一个基站，每个基站可以覆盖本城市和与本城市直线相邻的一座城市，不能是对角线，问最少用多少个基站可以覆盖完所有城市

思路

先给所有城市编号，把所有城市分成两个点，然后相邻城市建立无向边
于是可以只需要找到这些点的最大匹配书求出最大独立集即可

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <set> 
using namespace std;
const int N = 1009;

char map[50][20];
int map_count[50][20];
vector<int> v[N];
int p[N];
bool use[N];

int creat_count_of_city(int h , int w){
    int count = 1;
    for(int i = 1 ; i <= h ; i++){
        for(int k = 1 ; k <= w ; k++){
            if( map[i][k] == '*' )
                map_count[i][k] = count++;
            else
                map_count[i][k] = 0;
        }
    }
    return count - 1;
}

void creat_pic(int h , int w){
    for(int i = 0 ; i < N; i++) v[i].clear();
    for(int i = 1 ; i <= h; i++){
        for(int k = 1 ; k <= w ; k++){
            if( k < w && map_count[i][k+1] != 0 )   v[map_count[i][k]].push_back(map_count[i][k+1]) , v[map_count[i][k+1]].push_back(map_count[i][k]);
            if( k > 1 && map_count[i][k-1] != 0 )   v[map_count[i][k]].push_back(map_count[i][k-1]) , v[map_count[i][k-1]].push_back(map_count[i][k]);
            if( i < h && map_count[i+1][k] != 0 )   v[map_count[i][k]].push_back(map_count[i+1][k]) , v[map_count[i+1][k]].push_back(map_count[i][k]);
            if( i > 1 && map_count[i-1][k] != 0 )   v[map_count[i][k]].push_back(map_count[i-1][k]) , v[map_count[i-1][k]].push_back(map_count[i][k]);
        }
    }
}

int dfs(int u){
    for(int i = 0 ; i < v[u].size() ; i++){
        if( !use[v[u][i]] ){
            use[v[u][i]] = true;
            if( p[v[u][i]] == -1 || dfs(p[v[u][i]]) ){
                p[v[u][i]] = u;
                return 1;
            }
        }
    }
    return 0;
}

int hungarian(int n){
    int ans = 0;
    memset(p,-1,sizeof(p));
    for(int i = 1 ; i <= n ; i++)
        memset(use,false,sizeof(use)) , ans += dfs(i);
    return ans; 
}

int main(){
    int h,w,t,n;
    scanf("%d",&t);
    while( t-- ){
        scanf("%d%d",&h,&w);
        for(int i = 1 ; i <= h ; i++)   scanf("%s",map[i]+1);
        n = creat_count_of_city(h,w);
        creat_pic(h,w);
        printf("%d\n",n - hungarian(n) / 2);
    }
}