@darkproject 2017-03-30T10:03:44.000000Z 字数 3522 阅读 785

二分图专题

集训队

A - COURSES （POJ - 1469）

题意大致是P门课n个学生，学生可以选一门课程或者不选，但要求每门课程都要被选上并且是不同的学生代表。
我们可以将学生与课程二分建图，判断其最大匹配数是否满足条件，满足即为yes

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
const int maxn = 405;
using namespace std;
int un, vn, g[maxn][maxn];
int linker[maxn], check[maxn];
bool dfs(int u) {
    int v;
    for (v = 1; v<=vn; v++)
    {
        if (g[u][v] && !check[v])
        {
            check[v] = 1;
            if (linker[v] == -1 || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungarian()
{
    int ans = 0;
    memset(linker, -1, sizeof(linker));
    for (int u = 1; u<=un; u++)
    {
        memset(check, 0, sizeof(check));
        if (dfs(u)) ans++;
    }
    return ans;
}
int main()
{
    int p, n, a, b, t;
    scanf("%d", &t);
    while (t--)
    {
        memset(g,0,sizeof(g)); 
        scanf("%d%d", &p, &n);
        un = p, vn = n;
        for (int i = 1; i<=p; ++i)
        {
            scanf("%d", &a);
            for (int j = 0; j<a; j++)
            {
                scanf("%d", &b);
                g[i][b] = 1;
            }
        }
        if (hungarian()==p) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B - The Accomodation of Students HDU - 2444

N个学生他们可能认识也可能不认识，现考虑能否将他们分为2组，使2组的学生都是熟人，每组内的学生都是陌生人，如果可以分成2组算出需要多少房间，不可以则输出No
ps:判断是否为二分图：选取某个点作为起点并染为某种颜色、同时把它相邻的元素染为对立的颜色，进行搜索，如果到那步发现当前点和相邻点的颜色一样，那么就出现了矛盾，就不是二分图。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
const int maxn=205;
using namespace std;
typedef vector<int>::iterator mxr;
int n,m,color[maxn],check[maxn],linker[maxn];
//vector<int>un;
vector<int>G[maxn];
bool judge(int v,int c)
{
    color[v]=c;
    for(int i=0;i<G[v].size();i++)
    {
        if(color[G[v][i]]==c) return false;
        if(color[G[v][i]]==0&&!judge(G[v][i],-c)) return false;
    }
    return true;
}
bool solve()
{
    memset(color,0,sizeof(color));
    for(int i=0;i<n;++i)
        if(color[i]==0)
            if(!judge(i,1))
                return false;
    return true;
}
bool dfs(int u)
{
    int v;
    for(mxr i=G[u].begin();i!=G[u].end();i++)
    {
        v=*i;
        if(!check[v])
        {
            check[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            { 
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}
int hungarian()
{
   int ans=0;
   memset(linker,-1,sizeof(linker));
   //mxr it;
   //for(it=un.begin();it!=un.end();++it)
   for(int i=1;i<=n;i++)
   {
     memset(check,0,sizeof(check));
     if(dfs(i)) ans++;
   }
    return ans;
}
void init()
{
    //un.clear();   
    for(int i=0;i<maxn;i++)
        G[i].clear();
}
int main()
{
    int x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=0;i<m;++i)
        {
            scanf("%d%d",&x,&y);
        //  un.push_back(x);
            G[x].push_back(y);
        }
        if(!solve())
            printf("No\n");
        else
        {
            printf("%d\n",hungarian());
        }
    }
    return 0;
}

C - Guardian of Decency POJ - 2771

老师带学生出去旅游，但是担心学生会发生恋爱关系，所以带出去的学生至少要满足以下要求之中的一个：
1.身高相差40cm以上
2.同性
3.喜欢的音乐风格不同
4.喜欢的运动相同
问最多可以带出去多少学生？
最大独立集：最大的一个集合，其中的每两点之间都不存在边
最大独立集=顶点数-最大匹配数
ps:因为dfs扫点扫了2遍，所以最大匹配数/2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <cstring>
const int maxn = 505;
using namespace std;
int check[maxn], linker[maxn];
int map[maxn][maxn];
int t, n;
struct mxr
{
    int hei;
    char sex;
    char music[105];
    char sport[105];
}stu[maxn];
bool judge(mxr a, mxr b)
{
    if (a.sex != b.sex&&strcmp(a.music, b.music) == 0 && abs(a.hei - b.hei) <= 40 && strcmp(a.sport, b.sport) != 0)
        return true;
    return false;
}
bool dfs(int u)
{
    for (int v = 0; v<n; v++)
    {
        if (map[u][v] && !check[v])
        {
            check[v] = 1;
            if (linker[v] == -1 || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungarian()
{
    int ans = 0;
    memset(linker, -1, sizeof(linker));
    for (int i = 0; i<n; i++)
    {
        memset(check, 0, sizeof(check));
        if (dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        memset(map, 0, sizeof(map));
        scanf("%d", &n);
        for (int i = 0; i<n; ++i)
            scanf("%d %c %s %s", &stu[i].hei, &stu[i].sex, stu[i].music,stu[i].sport);
        for (int i = 0; i<n; ++i)
            for (int j = 0; j<n; j++)
            {
                if (judge(stu[i], stu[j]))
                    map[i][j] = 1;
            }
        printf("%d\n", n - hungarian()/2);
    }
    return 0;
}

自补：
codeforce #round 400 (div1+div2) D. The Door Problem

m个开关控制n个门，每个门由2个开关控制。门的状态由0，1表示，问任意按下开关是否可以使所有的门为0状态。此题可以用并查集或者二分图做，将开关视为点，门的状态作为点边连接。开关分为2个状态按与不按，可以将其分为i+m与i来表示这个状态，最后判断是否在一个并查集里同时存在i+m与m即可，若同时存在即为NO。二分图将开关按下与不按下分为2个集合然后dfs判断图中是否存在环，若存在即为NO。

二分图专题

内容目录