HDU 1083 2063 ZOJ 4120(二分图匹配)

确定是二分图求最大匹配时，对任意一方查找匹配均可

数组link

记录：link[i] = v; 选项i(下标) 分配给任务v(储存值)

数组vis

记录：在为任务v配对时 选项i(下标)是否被访问过

作用：为了替任务v争得选项to，在此处将选项to锁定，dfs寻找选项(to) 原来服务的任务(link[to]) 其他可行的选项，体现了增广路的特点——反悔

注意

每次为任务选择选项时，每个选项要从头考虑（memset(vis, 0, sizeo(vis))），直到找到合适的选项为止

HDU 1083

题意：P课程各找一个课代表，N个人，每人至多担任一门课代表

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int p, n;
int link[1005];///link[i] = v; 选项i 分配给任务v
bool vis[1005];///在为任务v配对时 选项i是否被访问过
vector<int> vec[1005];

/*
vis数组的作用：
///为了替任务v争得选项to，在此处将选项to锁定，
dfs寻找选项(to) 原来服务的任务(link[to]) 其他可行的选项
体现了反悔这一增广路的特点
*/

bool dfs(int v)
{
    for(int i = 0; i < vec[v].size(); ++i)
    {
        int to = vec[v][i];
        if(!vis[to])
        {
            vis[to] = 1;
            if(link[to] == -1 || dfs(link[to]))
            {
                link[to] = v;
                return 1;
            }
        }
    }
    return 0;
}

void slove()
{
    int ans = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i <= p; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
            ans++;
    }
    if(ans == p)
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int cnt, tem;
        scanf("%d%d", &p, &n);
        for(int i = 0; i < 1005; ++i)
            vec[i].clear();
        for(int i = 1; i <= p; ++i)
        {
            scanf("%d", &cnt);
            while(cnt--)
            {
                scanf("%d", &tem);
                vec[i].push_back(tem);
            }
        }
        slove();
    }
    return 0;
}

HDU 2063

题意：男女配对

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int k, m, n;
int link[1005];
bool vis[1005];
vector<int> vec[1005];

bool dfs(int v)
{
    for(int i = 0; i < vec[v].size(); ++i)
    {
        int to = vec[v][i];
        if(!vis[to])
        {
            vis[to] = 1;
            if(link[to] == -1 || dfs(link[to]))
            {
                link[to] = v;
                return 1;
            }
        }
    }
    return 0;
}

void slove()
{
    int ans = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i <= m; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
            ans++;
    }
    cout << ans << '\n';
}

int main()
{
    int girl, boy;
    while(~scanf("%d", &k) && k)
    {
        for(int i = 0; i < 1005; ++i)
            vec[i].clear();
        scanf("%d%d", &m, &n);
        for(int i = 0; i < k; ++i)
        {
            scanf("%d%d", &girl, &boy);
            vec[girl].push_back(boy);
        }
        slove();
    }
    return 0;
}

ZOJ 1083 Tokens on the Segments

题意：一个直角坐标轴，y轴上从1到n共n个点，分别对应x轴上一段区间，从对应区间中为每个点匹配一个点，x轴上每个被选择的点不可重复

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

int n;
map<int, int> link;
map<int, int> vis;
int l[N], r[N];

bool dfs(int v)
{
    for(int i = l[v]; i <= r[v]; ++i)
        if(!vis[i])
        {
            vis[i] = 1;
            if(link[i] == 0 || dfs(link[i]))
            {
                link[i] = v;
                return 1;
            }
        }
    return 0;
}

void slove()
{
    int ans = 0;
    link.clear();
    for(int i = 1; i <= n; ++i)
    {
        vis.clear();
        if(dfs(i))
            ans++;
    }
    cout << ans << '\n';
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i)
            scanf("%d%d", &l[i], &r[i]);
        slove();
    }
    return 0;
}

昨日种种皆成今我：利用一切可利用的时间学习，也不至于不会做，不至于打铁了

今日种种皆成新我：现在不珍惜时间多学多练，将来还是要被碾压、还是要打铁