一道二分图匹配模板题

点我传送

题目背景

公元二零一四年四月十七日，小明参加了省赛，在一路上，他遇到了许多问题，请你帮他解决。

题目描述

已知车上有N排座位，有N*2个人参加省赛，每排座位只能坐两人，且每个人都有自己想坐的排数，问最多使多少人坐到自己想坐的位置。

输入格式

第一行，一个正整数Ｎ。

第二行至第Ｎ*2+1行，每行两个正整数Si1，Si2，为每个人想坐的排数。

输出格式

一个非负整数，为最多使得多少人满意。

输入输出样例

输入

4
1 2
1 3
1 2
1 3
1 3
2 4
1 3
2 3

输出

7

说明/提示

对于10%的数据 N≤10

对于30%的数据 N≤50

对于60%的数据 N≤200

对于100%的数据 N≤2000

算法提示：二分图的最大匹配

题解

这题一看题面就知道是二分图，于是我想都没想就开始打板子（因为太像板子题了）。调了半天才发现这里点和点之间的对应关系不想二分图板子那样是单一的：

每排座位只能坐两人

emmmmm，这要怎末办呢。

我们发现，我们把一排座位拆成两个点对答案丝毫不产生影响，所以我们可以邻接表开两倍，再存一倍的边。

对了，这题据说卡邻接矩阵

CODE

#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 4005
using namespace std;

struct node
{
    int to, next;
} e[maxn << 4];     //要多开两倍哦~~

int head[maxn], num;
int book[maxn], match[maxn], n, ans;

void add_edge(int from, int to)     //临界表
{
    e[++num].next = head[from];
    e[num].to = to;
    head[from] = num;
}

inline bool dfs(int u)      //匈牙利算法板子
{
    for (register int i = head[u]; i; i = e[i].next)
    {
        int to = e[i].to;
        if (!book[to])
        {
            book[to] = 1;
            if (match[to] == 0 || dfs(match[to]))
            {
                match[to] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);  //关同步
    cin.tie(0);     //取消cin，cout绑定
    cout.tie(0);

    cin >> n;
    for (register int i = 1; i <= (n << 1); i++)
    {
        int x, y;
        cin >> x >> y;
        add_edge(i, y);       //把座位拆开
        add_edge(i, x);
        add_edge(i, y + n);
        add_edge(i, x + n);
    }

    for (register int i = 1; i <= (n << 1); i++)//统计答案
    {
        memset(book, 0, sizeof(book));
        ans += dfs(i);
    }
    cout << ans;
    return 0;
}

END