CQUPT 二分图

题解

POJ1325
题意：
有两台机器A，B，A有n种模式，B有m种模式，任意一件产品，要么可以在A的x模式下，要么在B的y模式下完成。但是每次机器转换模式，都需要重启，问最少需要重启的次数。
思路：
最少需要重启多少次，既是最少用了多少种模式。因为有A，B两个，所以想到二分图，对于一个零件，就在x,y之间连边。求最少的点覆盖，就是求边的最大匹配（画图去理解）。需要注意的是含有0的就不需要连边了，因为最开始就是0模式，这个点就不需要算。匈牙利算法过。。。
代码：

#include <stdio.h>
#include <string.h>
bool line[105][105];
bool used[105];
int g[105];
int n,m,k;
bool dfs(int x)
{
    for (int i = 1;i < m;i++)
    {
        if (line[x][i] && !used[i])
        {
            used[i] = 1;
            if (g[i] == -1 || dfs(g[i]))
            {
                g[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while (scanf("%d",&n) != EOF && n)
    {
        memset(line,0,sizeof(line));
        memset(g,-1,sizeof(g));
        scanf("%d%d",&m,&k);
        for (int i = 0;i < k;i++)
        {
            int x,y;
            int t;
            scanf("%d%d%d",&t,&x,&y);
            line[x][y] = 1;
        }
        int ans = 0;
        for (int i = 1;i < n;i++)
        {
            memset(used,0,sizeof(used));
            if (dfs(i)) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj2771：guardian of decency
题意：
有许多人要出去远足，老师为了防止互相谈恋爱，就提出四个条件，如果四个条件都不满足的人就不能一起，问有多少人可以出去。
卡住：
不知道如何建边，后来看了题解，知道了可以谈恋爱的人之间建边，那么我们要求的就是二分图的最大独立集，即每个点之间都没有相连的边，就保证了没有人可以谈恋爱。
注意：
我们选择建立无向图(有向图无法实现退流操作。。。)，所以同一条边会匹配两次，这就是最后要把匹配数除以2的原因。
代码：

#include <stdio.h>
#include <string.h>
int n;
struct pupil
{
    int h;
    char se;
    char ms[105];
    char sp[105];
};
typedef struct pupil pp;
pp stu[505];
bool line[505][505];
bool used[505];
int g[505];
int mabs(int x)
{
    return x >= 0 ? x : -x;
}
bool dfs(int x)
{
    for (int i = 0;i < n;i++)
    {
        if (line[x][i] && !used[i])
        {
            used[i] = true;
            if (g[i] < 0 || dfs(g[i]))
            {
                g[i] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        memset(stu,0,sizeof(stu));
        memset(line,0,sizeof(line));
        memset(g,-1,sizeof(g));
        memset(used,0,sizeof(used));
        scanf("%d",&n);
        for (int i = 0;i < n;i++)
            scanf("%d %c %s %s",&stu[i].h,&stu[i].se,stu[i].ms,stu[i].sp);
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
        {
            bool flag = 1;
            if (mabs(stu[i].h-stu[j].h) > 40)
                flag = 0;
            if (stu[i].se == stu[j].se)
                flag = 0;
            if (strcmp(stu[i].ms,stu[j].ms) != 0)
                flag = 0;
            if (strcmp(stu[i].sp,stu[j].sp) == 0)
                flag = 0;
            if (flag) line[i][j] = 1;
        }
        int ans = 0;
        for (int i = 0;i < n;i++)
        {
            memset(used,0,sizeof(used));
            if (dfs(i)) ans++;
        }
        ans = n - ans/2;
        printf("%d\n",ans);
    }
    return 0;
}

HDU3829 cats vs doge
题意：
有m只狗，n只猫，p个学生，每个学生如果喜欢狗，那么他一定讨厌猫，反之亦然。现在要去掉某些猫狗，如果一个学生的喜欢的被保留并且不喜欢的被去掉，那么这个学生就是开心的。问有最多能有多少学生开心。
卡住：
不知道如何建图，后来搜了报告，知道我们如果是将有矛盾的学生连边，那么很合理的，就是求最大独立集，即求最多的人不矛盾。很合理。。。
思路：
匈牙利算法，双向图，还是一条边匹配了两次，所以最后要除以2.
代码：

#include <stdio.h>
#include <string.h>
bool line[505][505];
int g[505];
bool v[505];
struct ch
{
    char like[5];
    char disl[5];
};
typedef struct ch ch;
ch chi[505];
int n,m,p;
bool dfs(int x)
{
    for (int i = 1;i <= p;i++)
    {
        if (!v[i] && line[x][i])
        {
            v[i] = 1;
            if (g[i] < 0 || dfs(g[i]))
            {
                g[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while (scanf("%d%d%d",&n,&m,&p) != EOF)
    {
        memset(chi,0,sizeof(chi));
        memset(line,0,sizeof(line));
        memset(g,-1,sizeof(g));
        memset(v,0,sizeof(v));
        for (int i = 1;i <= p;i++)
            scanf("%s%s",chi[i].like,chi[i].disl);
        for (int i = 1;i <= p;i++)
            for (int j = 1;j <= p;j++)
        {
            if (strcmp(chi[i].disl,chi[j].like) == 0) line[i][j] = line[j][i] = 1;
            if (strcmp(chi[i].like,chi[j].disl) == 0) line[i][j] = line[j][i] = 1;
        }
        int ans = 0;
        for (int i = 1;i <= p;i++)
        {
            memset(v,0,sizeof(v));
            if (dfs(i)) ans++;
        }
        printf("%d\n",p - ans / 2);
    }
    return 0;
}