二分图

二分图匹配

二分图:把无向图 G = (V,E)分为两个集合 V1,V2,所有的边都在 V1 和 V2 之间,而 V1 或 V2 的内部没有边。V1 中的一个点与 V2 中的一个点关联,称为匹配。
染色法:一个图是否为二分图,一般用“染色法”进行判断。用两种颜色对所有顶点进行染色,要求一条边所连接的两个相邻顶点的颜色不相同。染色结束后,如果所有相邻顶点的颜色都不相同,它就是二分图。
结论:一个图是二分图,当且仅当它不含边的数量为奇数的圈。

二分图最大匹配问题

二分图最大匹配问题:无权图,求包含边数最多的匹配,即二分图的最大匹配。
图片说明

匈牙利算法

时间复杂度: 图片说明
匈牙利算法可以看成最大流的一个特殊实现。
由于二分图是一个很简单的图,并不需要做一个标准的最大流,可以进行简化。

  1. 从上面的图解中发现对 s 和 t 的操作是多余的,直接从 a、b、c 开始找增广路径就可以了。
  2. 残留网络上的增广路需要覆盖完整的路径,如果在二分图中进行{a、b、c}到{x、y、z}的局部操作,将之用一个数组match[]就有覆盖整个路径的效果。
// 络谷 板子题(https://www.luogu.com.cn/problem/P3386)
#include<bits/stdc++.h>

using namespace std;

const int maxn = 501;
const int maxm = 5e4+1;

struct edge{
    int to, next;
}e[maxm<<1]; int head[maxn], tot;
int match[maxn];
bool vis[maxn];

void addedge(int u, int v) {
    e[++tot] = {v, head[u]}, head[u] = tot;
}

int dfs(int x) {
    for(int i = head[x]; ~i; i = e[i].next) {
        int j = e[i].to;
        if (vis[j]) continue;
        vis[j] = true;
        if (!match[j] || dfs(match[j])) {
            match[j] = x;
            return 1;
        }
    }
    return 0;
}

int main() {
    int nx, ny, m; scanf("%d%d%d", &nx, &ny, &m);
    memset(head, -1, sizeof head), tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v; scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    int maxmatch = 0;
    for(int i = 1; i <= nx; ++ i) {
        memset(vis, false, sizeof vis);
        maxmatch += dfs(i);
    }
    printf("%d\n", maxmatch);
    return 0;
}

Hopcroft-Krap算法

时间复杂度:图片说明
预先找到多条路径最短的增广路,然后匈牙利算法就沿着bfs找的路径去找增广路。
bfs具体步骤:

  1. 把 V1 中所有没匹配的点加入队列
  2. 每次出来一个点 x,对于它连的 V2 中的每个点 y,如果 y 没访问过且没匹配过,找到增广路,否则把 y 的匹配点压入队列
// hdu 2063 (http://acm.hdu.edu.cn/showproblem.php?pid=2063)
#include<bits/stdc++.h>

using namespace std;

const int maxn = 501;
const int inf = 0x3f3f3f3f;

vector<int> g[maxn];
int cx[maxn], cy[maxn];
int dx[maxn], dy[maxn];
int vis[maxn];

int bfs(int n) { // bfs搜索多条不想交最短增广路径
    memset(dx, 0, sizeof(dx));
    memset(dy, 0, sizeof(dy));
    queue<int> q;
    for(int i = 1; i <= n; ++ i) {
        if (!cx[i]) q.push(i);
    }
    int dis = inf;
    while(!q.empty()) {
        int t = q.front(); q.pop();
        if (dx[t] >= dis) continue;
        for(auto i: g[t]) {
            if (dy[i]) continue;  // 多条路径不想交
            dy[i] = dx[t] + 1;
            if (!cy[i]) dis = dy[i]; // 最短路径已找到
            else {
                dx[cy[i]] = dy[i];
                q.push(cy[i]);
            }
        }
    }
    return dis != inf;
}

int dfs(int x) {   // 按照bfs搜索路径进行dfs
    for(auto i: g[x]) {
        if (vis[i] || dy[i] != dx[x] + 1) continue;
        vis[i] = 1;
        if (!cy[i] || dfs(cy[i])) {
            cx[x] = i, cy[i] = x;
            return 1;
        }
    }
    return 0;
}

int HK(int n) { // HK算法
    memset(cx, 0, sizeof(cx));
    memset(cy, 0, sizeof(cy));
    int res = 0;
    while(bfs(n)) {
        memset(vis, 0, sizeof(vis));  // 模拟dy[] 保证路径不相交
        for(int i = 1; i <= n; ++ i) {
            if (!cx[i] && dfs(i)) res ++;
        }
    }
    return res;
}

int main() {
    int n; while(scanf("%d", &n), n) {
        int x, y; scanf("%d%d", &x, &y);
        for(int i = 1; i <= x; ++ i) g[i].clear();
        for(int i = 1; i <= n; ++ i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v);
        }
        printf("%d\n", HK(x));
    }
    return 0;
}

Dinic 算法

用网络流来写二分图最大匹配。

// 络谷 板子题(https://www.luogu.com.cn/problem/P3386)
#include<bits/stdc++.h>

using namespace std;

const int maxn = 5010 << 1;
const int maxm = 5e4 + maxn;

struct edge{
    int to, next, cap, flow;
}e[maxm<<2]; int head[maxn], tot;
int nx, ny, m, s, t, d[maxn], cur[maxn];

void addedge(int u, int v, int w) {
    e[++tot] = {v, head[u], 1, 0}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0}, head[v] = tot;
}

void init() { // 连接源点 和 汇点
    memset(head, -1, sizeof head);
    tot = -1;
    s = nx + ny + 1;
    for(int i = 1; i <= nx; ++ i) {
        addedge(s, i, 1);
    }
    t = nx + ny + 2;
    for(int i = 1; i <= ny; ++ i) {
        addedge(i + nx, t, 1);
    }
}

bool bfs() {
    memset(d, 0x7f, sizeof d);
    queue<int> q; q.push(t);
    d[t] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (d[j] > d[x] + 1 && e[i^1].cap > e[i^1].flow) {
                d[j] = d[x] + 1;
                if (j == s) return true;
                q.push(j);
            }
        }
    }
    return false;
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
//    for(int i = cur[x]; ~i && flow != used; i = e[ cur[x] = i ].next) { // 当前弧优化
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to, f;
        if (d[x] - 1 == d[j] && e[i].cap > e[i].flow) {
            f = dfs(j, min(flow - used, e[i].cap - e[i].flow));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    if (!used) d[x] = 0; // 剪枝优化
    return used;
}

int main() {
    scanf("%d%d%d", &nx, &ny, &m);
    init();
    for(int i = 1; i <= m; ++ i) {
        int u, v; scanf("%d%d", &u, &v);
        addedge(u, v + nx, 1);
    }
    int maxflow = 0;
    while(bfs()) {
//        memcpy(cur, head, sizeof head);
        maxflow += dfs(s, INT_MAX);
    }
    printf("%d\n", maxflow);
    return 0;
}

二分图求最大权匹配

KM 算法

时间复杂度:图片说明
KM算法:用于求二分图匹配的最佳匹配(最大权完美匹配)。
算法过程:

  1. 用邻接矩阵存图,给每个点加一个期望(cx[] 或 cy[]),当一对匹配的期望和等于其权值时该匹配才有可能匹配,我们需要最大权值和,所以先假设期望可以最大 cx[i] = max{与它有关的匹配权值},cy[i] = 0。
  2. 尝试对第 i 个点进行匹配,若匹配成功,则进行下一个;若匹配失败,则降低左边已匹配点和该点的期望,提高右边已匹配点的期望,通过降低期望的方式尝试与独立点进行匹配,重复操作2。


注:初始化各点期望后,实线为可能匹配,虚线暂时不能匹配。(绿色为匹配成功,黄色为增广路,红色为匹配失败)
图片说明
注: 若经过图四修改后 x2 仍然匹配失败,则重复图四修改即可。
图片说明
注:代码中 km算法 是完备匹配下的最大期望,若初始化为0,则是最大权值和。

// hdu 2255 (http://acm.hdu.edu.cn/showproblem.php?pid=2255)
#include<bits/stdc++.h>

using namespace std;

const int maxn = 301;

int graph[maxn][maxn];
int match[maxn], hx[maxn], hy[maxn], d[maxn], pre[maxn];
bool vis[maxn];

int km(int n) {
    memset(match, 0, sizeof match);
    for(int i = 1; i <= n; ++ i) { // 初始化期望权值
        hx[i] = INT_MIN, hy[i] = 0;
        for(int j = 1; j <= n; ++ j) {
            hx[i] = max(graph[i][j], hx[i]);
        }
    }
    for(int i = 1; i <= n; ++ i) {  // 尝试匹配
        memset(d, 0x7f, sizeof d);
        memset(vis, false, sizeof vis);
        int pos = 0, y;
        match[pos] = i;
        do {   // 通过不段提高期望来满足匹配
            int dis = INT_MAX, x = match[pos];
            vis[pos] = true;
            for(int j = 1; j <= n; ++ j) {
                if (vis[j]) continue;
                if (d[j] > hx[x] + hy[j] - graph[x][j]) {
                    d[j] = hx[x] + hy[j] - graph[x][j];
                    pre[j] = pos;
                }
                if (dis > d[j]) {
                    dis = d[j];
                    y = j;
                }
            }
            for(int j = 0; j <= n; ++ j) {
                if (vis[j]) hx[ match[j] ] -= dis, hy[j] += dis;
                else d[j] -= dis;
            }
            pos = y;
        } while(match[pos]);
        for(int j = pos; j; j = pre[j]) {
            match[j] = match[ pre[j] ];
        }
    }
    int res = 0;
    for(int i = 1; i <= n; ++ i) {
        res += graph[ match[i] ][i];
    }
    return res;
}

int main() {
    int n; while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                scanf("%d", &graph[i][j]);
            }
        }
        printf("%d\n", km(n));
    }
    return 0;
}

测试题:

https://nanti.jisuanke.com/t/42404

图论 文章被收录于专栏

关于acm竞赛图论的个人笔记

全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务