HDU 1281 Chessboard game(Bipartite graph match)

Description

N行M列的棋盘，空白地区放棋子“車”，使彼此不能攻击到，非空白地区不影响彼此的攻击(不是“墙”)，求在放最多“車”的前提下，有几个点是“重要点”（棋子不放在这里就会减少可放棋子数）？

Analyze

同HDU 1045 Fire Net类似，解法思想(二分图匹配)也相同

方案一 较为暴力

求完最大匹配后，将每条匹配的边撤掉再求一遍最大匹配，看是否减少，若减少则该边对应点是最要点。

Code

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

int n, m, k;
bool vis[N];
int mp[N][N], link[N], t_link[N];

///DFS(int x): link[to] = x not link[x] = to

bool DFS(int x)
{
    for(int i = 1; i <= n; ++i)
        if(mp[x][i] && !vis[i])
        {
            vis[i] = 1;
            if(link[i] == -1 || DFS(link[i]))
            {
                link[i] = x;
                return 1;
            }
        }
    return 0;
}

int solve()
{
    int res = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i <= n; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if(DFS(i))
            res++;
    }
    return res;
}

int main()
{
    int CASE = 1;
    while(~scanf("%d %d %d", &n, &m, &k))
    {
        memset(mp, 0, sizeof(mp));
        int u, v;
        for(int i = 0; i < k; ++i)
        {
            scanf("%d %d", &u, &v);
            mp[u][v] = 1;
        }

        int num = solve();

        int ans = 0;
        memcpy(t_link, link, sizeof(link));
        for(int i = 1; i <= n; ++i)
            if(t_link[i] != -1)
            {
                mp[ t_link[i] ][i] = 0;
                int t_num = solve();
                if(t_num != num)
                    ans++;
                mp[ t_link[i] ][i] = 1;
            }
        printf("Board %d have %d important blanks for %d chessmen.\n", CASE++, ans, num);
    }
    return 0;
}

方案二 小题大做

同HDU 4685，添加虚点，求最大匹配，缩点。

这样做麻烦些，不仅可以得到“重要点”的个数，还可以得出”重要点“是哪些

Code

#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105 * 4;
const int M = 2 * N * N;
const int base = 100;

int n, m, k;
bool love[N][N];

int head[N], cnt;
struct edge
{
    int v, pre;
} e[M];

void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].pre = head[u];
    head[u] = cnt++;
}

bool vis[N];
int girl[N], boy[N];
bool DFS(int x)
{
    for(int i = head[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(!vis[to])
        {
            vis[to] = 1;
            if(!girl[to] || DFS(girl[to]))
            {
                girl[to] = x;
                boy[x] = to;
                return 1;
            }
        }
    }
    return 0;
}

int Match()
{
    int res = 0;
    for(int i = 1; i <= n; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if(DFS(i))
            res++;
    }
    return res;
}

bool inst[N];
stack<int> st;
vector<int> scc[N];
int low[N], times[N], t, num, ltt[N];
void Tarjan(int x)
{
    st.push(x);
    inst[x] = 1;
    low[x] = times[x] = ++t;
    for(int i = head[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(!times[to])
        {
            Tarjan(to);
            low[x] = min(low[x], low[to]);
        }
        else if(inst[to])
            low[x] = min(low[x], times[to]);
    }

    if(low[x] == times[x])
    {
        ++num;
        while(!st.empty())
        {
            int tem = st.top();
            st.pop();
            ltt[tem] = num;
            inst[tem] = 0;

            if(tem > base && tem <= 2 * base)///This is a girl.
                scc[num].push_back(tem - base);

            if(tem == x)
                break;
        }
    }
}

void init()
{
    for(int i = 0; i <= num; ++i)
        scc[i].clear();
    cnt = t = num = 0;
    while(!st.empty())
        st.pop();
    memset(ltt, 0, sizeof(ltt));
    memset(boy, 0, sizeof(boy));
    memset(girl, 0, sizeof(girl));
    memset(love, 0, sizeof(love));
    memset(inst, 0, sizeof(inst));
    memset(head, -1, sizeof(head));
    memset(times, 0, sizeof(times));
}

int main()
{
    int CASE = 1;
    while(~scanf("%d %d %d", &n, &m, &k))
    {
        init();
        int u, v;
        for(int i = 0; i < k; ++i)
        {
            scanf("%d %d", &u, &v);
            love[u][v] = 1;
            add(u, base + v);
        }

        int matches = Match();

        int node = 0;
        for(int i = 1; i <= n; ++i)
            if(!boy[i])
            {
                ++node;
                v = 2 * base + node;
                boy[i] = v, girl[v] = i;

                for(int j = 1; j <= n; ++j)
                    add(j, v);
            }
        for(int i = base + 1; i <= base + m; ++i)
            if(!girl[i])
            {
                ++node;
                v = 2 * base + node;
                girl[i] = v, boy[v] = i;

                for(int j = base + 1; j <= base + m; ++j)
                    add(v, j);
            }

        for(int i = base + 1; i <= base * 2 + node; ++i)
            add(i, girl[i]);///Opposite edges

        for(int i = 1; i <= n; ++i)
            if(!times[i])
                Tarjan(i);

        int tot, ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            tot = 0;
            int sz = scc[ ltt[i] ].size();
            for(int j = 0; j < sz; ++j)
            {
                v = scc[ ltt[i] ][j];
                if(love[i][v])
                    tot++;
            }
            if(tot == 1)
                ans++;
        }
        printf("Board %d have %d important blanks for %d chessmen.\n", CASE++, ans, matches);
    }
    return 0;
}