officeyutong

标签： 二分图

  • 洛谷2774 方格取数问题

    行列染色，然后每个黑格子向白格子连边，然后二分图最大带权独立集。

    别**把反向边流量给写成加了！

    #include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 11000;
const int_t SOURCE = LARGE - 1;
const int_t SINK = LARGE;
const int_t INF = 0x7fffffff;
struct Edge {
    int_t to, capacity;
    int_t flow = 0;
    Edge* rev;
};

std::vector<Edge*> graph[LARGE + 1];
void pushEdge(int_t from, int_t to, int_t cap) {
    Edge* e0 = new Edge{to, cap};
    Edge* e1 = new Edge{from, 0};
    e1->rev = e0;
    e0->rev = e1;
    graph[from].push_back(e0);
    graph[to].push_back(e1);
#ifdef DEBUG
    cout << "edge " << from << " " << to << " " << cap << endl;
#endif
}

int_t dis[LARGE + 1], visited[LARGE + 1], curr[LARGE + 1];
bool BFS() {
    memset(curr, 0, sizeof(curr));
    memset(visited, 0, sizeof(visited));
    memset(dis, 0x3f, sizeof(dis));
    dis[SOURCE] = 0;
    std::queue<int_t> queue;
    queue.push(SOURCE);
    visited[SOURCE] = true;
    while (queue.empty() == false) {
        auto front = queue.front();
        queue.pop();
        // visited[front]=true;
        for (auto edge : graph[front]) {
            if (edge->capacity > edge->flow && visited[edge->to] == false) {
                visited[edge->to] = true;
                queue.push(edge->to);
                dis[edge->to] = dis[front] + 1;
            }
        }
    }
    return visited[SINK];
}

int_t DFS(int_t vtx, int_t minf = INF) {
    if (minf == 0 || vtx == SINK) return minf;
    int_t result = 0;
    for (int_t& i = curr[vtx]; i < graph[vtx].size(); i++) {
        Edge* edge = graph[vtx][i];
        if (dis[edge->to] != dis[vtx] + 1) continue;
        int_t val = DFS(edge->to, std::min(minf, edge->capacity - edge->flow));
        if (val > 0) {
            minf -= val;
            result += val;
            edge->flow += val;
            edge->rev->flow -= val;
            if (minf == 0) break;
        }
    }
    return result;
}
int_t execute() {
    int_t result = 0;
    while (BFS()) result += DFS(SOURCE);
    return result;
}
int_t n, m;

int_t encode(int_t r, int_t c) { return (r - 1) * m + c; }
int main() {
    // {
    //     cin >> n >> m >> SOURCE >> SINK;
    //     for (int_t i = 1; i <= m; i++) {
    //         int_t from, to, cap;
    //         cin >> from >> to >> cap;
    //         pushEdge(from, to, cap);
    //     }
    //     cout << execute() << endl;
    //     return 0;
    // }
    cin >> n >> m;
    static int_t mat[LARGE + 1][LARGE + 1];
    for (int_t i = 1; i <= n; i++)
        for (int_t j = 1; j <= m; j++) cin >> mat[i][j];
    int_t result = 0;
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = 1; j <= m; j++) {
            if ((i + j) % 2) {
                const auto connect = [&](int_t r, int_t c) {
                    if (r >= 1 && r <= n && c >= 1 && c <= m) {
#ifdef DEBUG
                        cout << i << "," << j << "->" << r << "," << c << endl;
#endif
                        pushEdge(encode(i, j), encode(r, c), INF);
                        //         #ifdef DEBUG
                        // cout<<"edge "
                        //         #endif
                    }
                };
                connect(i + 1, j);
                connect(i - 1, j);
                connect(i, j + 1);
                connect(i, j - 1);
                pushEdge(SOURCE, encode(i, j), mat[i][j]);
            } else {
                pushEdge(encode(i, j), SINK, mat[i][j]);
            }
            result += mat[i][j];
        }
    }
    cout << result - execute() << endl;
    return 0;
}

     

  • 洛谷2756 飞行员配对方案问题

    二分图匹配模板。

    #include <iostream>
#include <vector>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 100;
std::vector<int_t> graph[LARGE + 1];
int_t match[LARGE * 2 + 1];
bool checked[LARGE + 1];
bool DFS(int_t vtx)
{
    for (int_t to : graph[vtx])
    {
        if (checked[to] == false)
        {
            checked[to] = true;
            if (match[to] == -1 || DFS(match[to]))
            {
                match[to] = vtx;
                match[vtx] = to;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int_t n, m;
    cin >> n >> m;
    while (true)
    {
        int_t from, to;
        cin >> from >> to;
        if (from == -1)
            break;
        graph[from].push_back(to);
    }
    std::fill(match + 1, match + 1 + LARGE * 2, -1);
    int_t result = 0;
    for (int_t i = 1; i <= n; i++)
    {
        std::fill(checked + 1, checked + 1 + n + m, false);
        if (match[i] == -1)
        {
            result += DFS(i);
        }
    }
    cout << result << endl;
    for (int_t i = 1; i <= n; i++)
    {
        if (match[i] != -1)
        {
            cout << i << " " << match[i] << endl;
        }
    }
    return 0;
}

     

  • CF19E Fairy

    题意：

    删掉若干条边使原图成为二分图的方案数。

    题解：

    考虑DFS树。

    答案为所有奇环的交减掉偶环的并。

    这里的环指的是由一条非树边和若干条树边组成的环。

    如果一个奇环和偶环在树边上有交集，那么删掉交集部分后会形成新的奇环，而删掉奇环的非树边则会破坏奇环。

     

    首先考虑只有一个奇环的情况。

    首先奇环的非树边显然是可以删掉的，删掉后破坏了奇环。

    其次，奇环的树边，只要不被另一个偶环覆盖，那么也可以删（如果被覆盖了，删掉后会拼成一个新的奇环）

    考虑由多个奇环的情况。

    答案是所有奇环的公共部分。

    直接在树上打标记即可。

    #include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 10000;

struct State
{
    int_t depth;
    int_t vertex;
    bool operator<(const State &x) const
    {
        return depth < x.depth;
    }
    State(int_t vertex = -1, int_t depth = 0)
    {
        this->depth = depth;
        this->vertex = vertex;
    }
} seq[20][LARGE * 3 + 1];
struct Edge
{
    int_t to;
    int_t id;
    int_t from = -1;
};
int_t count = 0;
int_t first[LARGE + 1];
int_t depth[LARGE + 1];
std::vector<Edge> graph[LARGE + 1];
std::vector<Edge> nonetree[LARGE + 1];
std::vector<int_t> stage[LARGE + 1];
Edge inEdge[LARGE + 1];
bool visited[LARGE + 1];
int_t mark[LARGE + 1];
int_t parent[LARGE + 1];
int_t n, m;
void DFS0(int_t vertex, int_t from = -1, int_t depth = 1)
{
    if (visited[vertex])
        return;
    // cout << "visiting " << vertex << endl;
    ::parent[vertex] = from;
    stage[depth].push_back(vertex);
    ::depth[vertex] = depth;
    visited[vertex] = true;
    seq[0][++count] = State(vertex, depth);
    if (first[vertex] == 0)
        first[vertex] = count;
    for (auto &edge : graph[vertex])
    {
        if (visited[edge.to] && edge.to != from && ::depth[edge.to] > ::depth[vertex])
        {
            nonetree[vertex].push_back(edge);
        }
        else if (visited[edge.to] == false)
        {
            inEdge[edge.to] = edge;
            DFS0(edge.to, vertex, depth + 1);
            seq[0][++count] = State(vertex, depth);
            if (first[vertex] == 0)
                first[vertex] = count;
        }
    }
}
void init()
{
    for (int_t i = 1; (1 << i) <= count; i++)
    {
        for (int_t j = 1; j + (1 << i) - 1 <= count; j++)
        {
            seq[i][j] = std::min(seq[i - 1][j], seq[i - 1][j + (1 << (i - 1))]);
        }
    }
}
int_t getLCA(int_t v1, int_t v2)
{
    v1 = first[v1];
    v2 = first[v2];
    if (v1 > v2)
        std::swap(v1, v2);
    int_t i = std::log2(v2 - v1 + 1);
    return std::min(seq[i][v1], seq[i][v2 - (1 << i) + 1]).vertex;
}
int main()
{
    cin >> n >> m;
    for (int_t i = 1; i <= m; i++)
    {
        int_t from, to;
        cin >> from >> to;
        graph[from].push_back(Edge{to, i});
        graph[to].push_back(Edge{from, i});
    }
    for (int_t i = 1; i <= n; i++)
    {
        if (visited[i] == false)
        {
            DFS0(i);
        }
    }
    init();
    int_t count = 0;
    std::vector<Edge> evens;
    for (int_t i = 1; i <= n; i++)
    {
        for (auto &edge : nonetree[i])
        {
            int_t dis = depth[i] + depth[edge.to] - 2 * depth[getLCA(edge.to, i)] + 1;
            int_t mark;
            //偶环
            if (dis % 2 == 0)
            {
                mark = -1;
            }
            else
            { //奇环
                mark = 1;
                count++;
                evens.push_back(Edge{i, edge.id, edge.to});
            }
            ::mark[i] += mark;
            ::mark[edge.to] += mark;
            ::mark[getLCA(edge.to, i)] -= 2 * mark;
        }
    }
    for (int_t i = n; i >= 2; i--)
    {
        for (int_t vtx : stage[i])
        {
            mark[parent[vtx]] += mark[vtx];
        }
    }
    std::vector<int_t> result;
    if (count == 0)
    {
        for (int_t i = 1; i <= m; i++)
        {
            result.push_back(i);
        }
    }
    else if (count == 1)
    {
        int_t v1 = evens[0].from;
        int_t v2 = evens[0].to;
        int_t lca = getLCA(v1, v2);
        result.push_back(evens[0].id);
        while (v1 != lca)
        {
            if (mark[v1] == 1)
            {
                result.push_back(inEdge[v1].id);
            }
            v1 = parent[v1];
        }
        while (v2 != lca)
        {
            if (mark[v2] == 1)
            {
                result.push_back(inEdge[v2].id);
            }
            v2 = parent[v2];
        }
    }
    else if (count > 1)
    {
        for (int_t i = 1; i <= n; i++)
        {
            if (parent[i] != -1 && mark[i] == evens.size())
            {
                result.push_back(inEdge[i].id);
            }
        }
    }
    std::sort(result.begin(), result.end());
    cout << result.size() << endl;
    for (int_t x : result)
        cout << x << " ";
    cout << endl;
    return 0;
}

     

  • SCOI2010 连续攻击游戏

    二分图匹配板子。

    要用匈牙利。

    把攻击放在左边，装备放在右边，一个装备如果有某个攻击那么他们连边。

    然后从左边第一个点开始跑匈牙利，跑到不能增广为止。

    #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
typedef int int_t;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2000000;
const int_t OFFSET = 10000;
int_t matched[LARGE + 1];
bool check[10001];

std::vector<int_t> graph[LARGE + 1];

void pushEdge(int_t from, int_t to)
{
    graph[from].push_back(to);
}

bool DFS(int_t vertex)
{
    if (check[vertex])
        return false;
    check[vertex] = true;
    for (int_t i = 0; i < graph[vertex].size(); i++)

    {
        int_t to = graph[vertex][i];
        if (matched[to] == -1 || DFS(matched[to]))
        {
            matched[to] = vertex;
            matched[vertex] = to;
            return true;
        }
    }
    return false;
}

int main()
{
    static std::vector<int_t> damages[10001];
    int_t n;
    scanf("%d", &n);
    for (int_t i = 1; i <= n; i++)
    {
        int_t a, b;
        scanf("%d%d", &a, &b);
        damages[a].push_back(i);
        damages[b].push_back(i);
    }
    for (int_t i = 1; i <= 10000; i++)
    {
        for (int_t j = 0; j < damages[i].size(); j++)
        {
            int_t x = damages[i][j];
            pushEdge(i, x + OFFSET);
        }
    }
    int_t result = 0;
    std::fill(matched + 1, matched + 1 + LARGE, -1);
    for (int_t i = 1; i <= 10000; i++)
    {

        if (matched[i] == -1)
        {
            memset(check, 0, sizeof(check));
            if (DFS(i) == false)
                break;
            else
                result++;
        }
    }
    printf("%d", result);
    return 0;
}

     

  • HNOI2006 超级英雄 luogu2319

    匈牙利板子。

    注意匈牙利算法在匹配$n+1$个点是，可能会改变前$n$个点的匹配对象，但是不会让前$n$个点从匹配点变成未匹配点。

    #include <algorithm>
#include <vector>
#include <iostream>
#include <cstdio>
typedef long long int int_t;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 5000;
const int_t OFFSET = 2000;
//某个点与哪个点匹配
int_t matched[LARGE + 1];
bool check[LARGE + 1];
std::vector<int_t> graph[LARGE + 1];
bool DFS(int_t vertex, int_t from = -1)
{
    for (int_t i = 0; i < graph[vertex].size(); i++)
    {
        int_t to = graph[vertex][i];
        if (to != from)
        {
            //如果目标点不在增广里
            if (check[to] == false)
            {
                //放到增广路里
                check[to] = true;
                //如果目标点未匹配，而且在增广路里，那么这就是一条交错路，直接增广
                //或者如果能通过某些手段空出来一个点，也可以增广
                if (matched[to] == -1 || DFS(matched[to]))
                {
                    matched[vertex] = to;
                    matched[to] = vertex;
                    return true;
                }
            }
        }
    }
    return false;
}

void pushEdge(int_t from, int_t to)
{
    graph[from].push_back(to);
}

int main()
{
    std::fill(matched + 1, matched + 1 + LARGE, -1);
    int_t n, m;
    cin >> n >> m;
    //问题在左边
    for (int_t i = 1; i <= m; i++)
    {
        int_t v1, v2;
        cin >> v1 >> v2;
        pushEdge(i, v1 + OFFSET);
        if (v1 != v2)
            pushEdge(i, v2 + OFFSET);
    }
    int_t count = 0;
    for (int_t i = 1; i <= m; i++)
    {
        std::fill(check + 1, check + 1 + LARGE, false);
        if (DFS(i))
        {
            count += 1;
        }
        else
        {
            break;
        }
    }
    cout << count << endl;
    for (int_t i = 1; i <= count; i++)
    {
        printf("%lld\n", matched[i] - OFFSET);
    }
    return 0;
}

     

  • 匈牙利算法

    我居然现在才学会这个东西…

    复杂度$O(N(N+M))$

    #include <algorithm>
#include <vector>
#include <iostream>

using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 5000;
const int_t OFFSET = 2000;
//某个点与哪个点匹配
int_t matched[LARGE + 1];
bool check[LARGE + 1];
std::vector<int_t> graph[LARGE + 1];

bool DFS(int_t vertex, int_t from = -1)
{
    for (int_t to : graph[vertex])
    {
        if (to != from)
        {
            //如果目标点不在增广里
            if (check[to] == false)
            {
                //放到增广路里
                check[to] = true;
                //如果目标点未匹配，而且在增广路里，那么这就是一条交错路，直接增广
                //或者如果能通过某些手段空出来一个点，也可以增广
                if (matched[to] == -1 || DFS(matched[to]))
                {
                    matched[to] = vertex;
                    matched[vertex] = to;
                    return true;
                }
            }
        }
    }
    return false;
}

void pushEdge(int_t from, int_t to)
{
    graph[from].push_back(to);
    graph[to].push_back(from);
}

int main()
{
    std::fill(matched + 1, matched + 1 + LARGE, -1);
    int_t n, m, e;
    cin >> n >> m >> e;
    for (int_t i = 1; i <= e; i++)
    {
        int_t left, right;
        cin >> left >> right;
        if (right > m)
            continue;
        pushEdge(left, right + OFFSET);
    }
    int_t result = 0;
    for (int_t i = 1; i <= n; i++)
    {
        if (matched[i] == -1)
        {
            std::fill(check + 1, check + 1 + LARGE, false);
            if (DFS(i))
            {
                result += 1;
            }
        }
    }
    cout << result << endl;
    return 0;
}