POJ匹配

POJ1274

题目链接：http://poj.org/problem?id=1274

这道题可以用两种大的解法，一种是把他当作匈牙利算法的一道题，从匈牙利的角度找增广路，另一种是把他当作一道无源网络流问题，加一个超级源点，加一个超级聚点，求最大流。

下面是一份大佬的代码（匈牙利算法），我打的注释：

大佬的原文链接：https://blog.csdn.net/u013487051/article/details/37656979

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int M = 1000 + 5;
int n, m;
// 用来存m个barns里面产奶的牛是谁 
int link[M];
// 用来存那个路 
bool MAP[M][M];
// 在一次增广的过程中，防止同一个barn被访问多次，导致死循环，原作者用的名字是cover，然我我喜欢用vis来标记是否访问过，这里就定义为vis了 
bool vis[M];
// 记录答案 
int ans;

void init()
{
    int num;
    int y;
    memset(MAP, false, sizeof(MAP));
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &num);
        while( num-- )
        {
            scanf("%d", &y);
            MAP[i][y]=true;
        }
    }

}

bool dfs(int x)
{
    // x表示从x这头牛开始增广，尝试将x这头牛分配到每一个可能的barn 
    for(int y=1; y<=m; y++)
    {
        // 如果x可以到y，并且y这个barn在这次增广中还没有访问过 
        if(MAP[x][y] && !vis[y])
        {
            // 将这个barn标记为访问过了 
            vis[y]=true;
            // 如果这个barn之前没有牛，那么直接分配给这个牛即可，这次增广就成功了
            // 如果这个barn之前有牛，尝试把之前那个牛重新分配到非当前barn(y)，如果能成功，那么就增广成功 
            if(link[y]==-1 || dfs(link[y]))
            {
                link[y]=x;
                return true;
            }
            // 这个vis[y] =false,是我认为加的，加上应该不错，意思是说，在这次增广中dfs这个y，在当前这一层（dfs按照距离起点的距离分层的话），是不行的,
            // 但可能先去访问别的barn，然后一会儿再用到这个y，这样的效果是搜索了每一种情况 
            // 而按照本题这种两个集合的匹配问题的前提来思考，一旦y这次不行，那么就y一直不行了，
            // 因为从y出发只会找到同一条路(一个barn之前只被一头牛占领了嘛，每次去找肯定是之前那头牛，不会是别的)，
            // 我们这次在这一层走不通，下次在别的层再碰上还是走不通 , 此处不加这vis[y] =false,我认为是一种剪枝加速，并不是说错误 ，你去交会超时 
            // vis[y]=false;
        }
    }
    return false;
}

int main()
{
    freopen("in.txt", "r", stdin);
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        ans=0;
        init();

        // 用-1表示没有牛占用这个barn 
        memset(link, -1, sizeof(link));
        // 由于我们是顺序访问每一头牛的,所以每次访问的时候必定能保证这头牛还没有分配barn 
        for(int i=1; i<=n; i++)
        {
            // 每次增广前吧vis置0 
            memset(vis, false, sizeof(vis));
            // 每次成功增广一次，说明多出一个匹配，那么ans++ 
            if(dfs(i))ans++;
        }
        printf("%d\n", ans);
    }

    return 0;
}

网络流：

注意要将牛的标号和barn的编号区分，我这里是认为1-200是牛，201-400是barn，0是超级源点，401是超级汇点。

一开始先把题目的路输进来，然后超级源点，到每个牛加一个路，每个barn到超级汇点加一个路。

然后dfs搜索路径即可，注意用vis标记一次增广过程中访问过的点，避免死循环。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 200;
const int total_number=maxn*2+2;

int rode[total_number][total_number];

int pre[total_number];

bool vis[total_number];

int n,m;

int super_source=0, super_sink=total_number-1;

bool dfs(int ss)
{
    if(ss==super_sink)return true;

    for(int i=0;i<total_number;i++)
    {
        if(!vis[i]&&rode[ss][i]>0)
        {
            pre[i]=ss;
            vis[i]=1;
            if(dfs(i))return true;
//          vis[i]=0; //不写这个可以剪枝 
            pre[i]=i;
        }
    }
    return false;
}

void fresh_rode()
{
    // 正向减边，反向加边 
    int ss=super_sink;
    while(pre[ss]!=ss)
    {
        rode[pre[ss]][ss]-=1;
        rode[ss][pre[ss]]+=1;
        ss=pre[ss];
    }
}

void fresh_pre_vis()
{
    for(int i=0;i<total_number;i++)
    {
        pre[i]=i;
    }
    memset(vis, 0, sizeof(vis));
    vis[0]=1;
}

int main()
{
    freopen("D:\\c++\\dev\\in.txt", "r", stdin);
    while(~scanf("%d %d", &n, &m))
    {
        memset(rode, 0, sizeof(rode));
        int cnt, e;
        for(int i=1;i<=n;i++)
        {
            scanf("%d", &cnt);
            for(int j=0;j!=cnt;j++)
            {
                scanf("%d", &e);
                rode[i][maxn+e]=1;
            }
        }

        for(int i=1;i<=n;i++)
        {
            rode[super_source][i]=1;
        }
        for(int i=1;i<=m;i++)
        {
            rode[maxn+i][super_sink]=1;
        }

        int ans=0;
        fresh_pre_vis();
        while(dfs(super_source))
        {
            ans++;  
            fresh_rode();
            fresh_pre_vis();
        }

        printf("%d\n", ans);
    }
}