联赛知识点不列不知道,一列觉得自己就像一个pupil一样,于是赶紧学点新东西

二分图的定义:如果能把一张无向图(连不连通都可以)分成两个点集$V,V’; V\cap V’=\emptyset$,使得两个点集内部无边,则这张图是二分图,分成的两个点集分别称为左部和右部.

二分图判定定理

一张无向图是二分图$\Leftrightarrow$这张无向图中没有奇环.

那么这个定理有什么用呢?显然是可以方便地判断一张图是不是二分图,然后利用二分图的性质了.由于二分图的两个点集内部没有边,所以从一个点到同一集合中的另一个点一定会经过偶数条边,其中一半是出集合的,一半是进集合的.而且这条路径上的点是$V,V’$中的点交替出现的.所以我们如果给这张图着色,并且要求任意一条边的两个端点颜色不能相同,那么我们最少只需要两种颜色.

这就有了二分图染色判定法.即从一个点开始,给它染上一种颜色,那么这张图上的所有点颜色都应该确定了.我们通过DFS或者BFS给点染色,如果有相连的点未染色,就染上不同的颜色.如果有相连的点颜色相同,就返回0.

例题 [NOIP2010]关押罪犯

分析

题目非常清楚地告诉了我们要把罪犯(点)分成两个部分,然后使得每个部分内部的边的最大值最小.那么我们可以获得两个信息:首先要把点分成两个不相交的集合,其次还要使得最大值最小.我们猜测这是二分图和二分答案结的题目.

但是题目貌似没有办法让每个集合内部没有边,那我们先来看能不能二分答案.答案是最大边的最小值,而这个根据不同的分法显然能构成一个单调的结果序列.所以我们二分是否存在一个分法,使得集合内部最大的边权$<mid$,然后来缩小范围.

那么既然要求集合内部的边都小于$mid$,那么不小于$mid$的边就只好放在集合之间.但是连好所有$>=mid$的边的话可能会导致图中存在奇环而出现两个点既应该在一个集合又不应该在一个集合的情况,所以我们要通过染色法来判断这张图是不是二分图.这样我们就得出了解法:二分$mid$,在染色时只看$>=mid$的边,如果符合就代表能够分成两个点集,否则不能.

代码:

#include <bits/stdc++.h>
#define N 100005
using namespace std;

inline void read(int &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int n, m, noe;
int to[N << 1], len[N << 1], nxt[N << 1], head[20005];
int col[20005];

inline void addedge(int from, int t, int l) {
    len[++noe] = l;
    nxt[noe] = head[from];
    head[from] = noe;
    to[noe] = t;
    return;
}

inline bool paint(int st, int c, int mid) {
    queue<int> q;//广搜染色
    q.push(st);
    col[st] = c;
    while (!q.empty()) {
        int temp = q.front();
        q.pop();
        for (int i = head[temp]; i; i = nxt[i]) {
            if (len[i] < mid)//只看>=mid的边
                continue;
            if (col[to[i]] == col[temp])
                return 0;
            if (!col[to[i]])
                col[to[i]] = 3 - col[temp], q.push(to[i]);
        }
    }
    return 1;
}

inline bool check(int nowans) {
    memset(col, 0, sizeof(col));
    for (int i = 1, flag = 1; i <= n; ++i) {
        if (!col[i])
            flag = paint(i, 1, nowans);
        if (!flag) return 0;
    }//二分答案的检验
    return 1;
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        read(x), read(y), read(z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    int l = 0, r = 1145141919;
    while (l < r) {
        int mid = l + r >> 1;
//        cout << mid << " " << check(mid) << endl;
        if (!check(mid))
            l = mid + 1;
        else r = mid;
    }//因为>=mid的都不能分,所以最终答案=mid-1
    printf("%d\n", (l == 0 ? 0 : l - 1));//别忘了0
    return 0;
}

二分图的最大匹配

先来说一下二分图的匹配:

互相独立没有公共顶点的一组边称为图的一个匹配.对于一组匹配,我们称它所涉及到的点为匹配点,未涉及的叫非匹配点.同样的方法定义了匹配边和非匹配边.如果在二分图中存在一条连接两个非匹配点的路径,而且这条路径还是匹配边和非匹配边交错组成,那么这条路被称为这个匹配的增广路.为什么叫”增广”呢?因为我们由定义可以发现,由于是匹配与非匹配交错,但是开头结尾都是非匹配边,所以非匹配边一定比匹配边多一条.那么我们把路径上每个点以及每条边的性质取反,就会发现它仍然是一组匹配.所以这条路实现了对它对应匹配的”增广”.二分图的最大匹配就是含有边数最多的匹配.当然因此我们就可以推出以下结论:

二分图的一组匹配是最大匹配$\Leftrightarrow$图中没有这个匹配的增广路(因为它无法再被增广了)

那么我们是不是可以通过逐步增广的方式来求出最大匹配呢?答案是肯定的.由此引出重点:匈牙利(增广路)算法

匈牙利算法

这个算法主要用来计算二分图的最大匹配.下面用文字介绍一下它的过程(由于本人水平和时间问题,不再上图,无法理解文字者请自行百度图解,抱歉)

1. 首先把所有边都当作非匹配边,即一切从零开始.

2. 寻找增广路,即寻找匹配的右部节点.方法如下:

   扫描当前点u的出边,访问对面所有满足以下条件之一的点v

   • v是非匹配点,那么这条出边就是一条增广路.
   • v虽然已经匹配了,但与它匹配的点x有能力让位并换一个点y配对,也就是取消一个匹配(x,v),并增加两个匹配(x,y)(u,v),这样也找到了增广路.

   第二个条件回溯时取反则u也得以匹配.操作上就是由边(u,v)递归到y,由已有的匹配(v,x)递归到x,扫描x的出边找到y,表明可以让位并创建(x,y)返回时把路径取反就完成了上述表明的操作并得到了新的两个匹配(x,y)和(u,v).

3. 重复第二步,直到没有增广路

以上就是匈牙利算法的过程.

例题【模板】二分图匹配

本题已经明确了图是二分图,且左部和右部都是从1开始标号.由于数据范围小我们可以建立邻接矩阵来存图.因为我们只需为左部点向右部点寻找匹配,所以只由左部点向右部点连边.然后进行匈牙利算法.
代码:

int dfs(int now) {
    for (int i = 1; i <= m; ++i)
        if (!vis[i] && edge[now][i]) {
            vis[i] = 1;
            if (!conn_y[i] || dfs(conn_y[i])) {
                conn_x[now] = i;//满足两个条件之一即可
                conn_y[i] = now;
                return 1;
            }
        }
    return 0;
}

inline void maxmatch() {
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        ans += dfs(i);
    }
    cout << ans << endl;
    return;
}