Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

ACM-二分图

2019/12/08 ACM
Word count: 2,465 | Reading time: 11min

二分图的判定：

染色法1：假设DFS初始点A涂黑色，与它相邻的点就涂白色。如果搜到某一个点u的相邻点v已经涂色并且与u同色，就不可能是二分图啦~

染色法2：就是给每个点进行标号，标为-1，1如果存在一条边连接的两个点标号相同，那么就是存在一个奇数环…

热身题：

判断无向图是否有环

用DFS遍历图g，如果访问到已经访问过的顶点，那么有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define SIZE 100+5

/**
 * 起点编号从0开始
 */
struct graph{
    int en;                 // 边数
    int vn;                 // 顶点数
    int map[SIZE][SIZE];    // 邻接矩阵
    int vis[SIZE];          // 记录矩阵
    bool huan = false;      // 是否有环
};


/**
u: 当前节点节点
prev: 记录上一个节点
g: 图指针
 */
void dfs(int u, int prev, graph *g){
    // 遍历图
    for (int v = 0; v < g->vn; ++v){    // v为下一个可达的节点
        // 自己到自己为0, 是没有边的
        if (v == prev) continue;
        if ( g->vis[v] != 2 && g->map[u][v] ){
            g->vis[v] = 1;
            dfs(v, u, g);
        }else if(g->vis[v] == 2 && g->map[u][v] ){
            printf("now: %d %d\n",u ,v );
             g->huan = true;
             return ;
        }
    }
}

void showGraph(const graph *g){
    printf("\t");
    for (int i = 0; i < g->vn; ++i){
        printf("%d ", i);
    }
    printf("\n");
    for (int i = 0; i < g->vn; ++i){
        printf("v:%d\t", i);
        for (int j = 0; j < g->vn; ++j){
            printf("%d ", g->map[i][j]);
        }
        printf("\n");
    }
}

int main(int argc, char const *argv[]){
    int n;
    graph *g = new graph();
    scanf("%d%d", &g->vn, &g->en);
    memset(g->map, 0, sizeof(int)*g->en*g->vn);
    for (int i = 0; i < g->en; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        g->map[u][v] = g->map[v][u] = 1;
    }
    showGraph(g);

    for (int i = 0; i < g->vn; ++i){
        // 如果节点i没被访问过
        if (g->vis[i] == 0 && g->huan == false){
            g->vis[i] = 2;
            dfs(i, -1, g);
            g->vis[i] = 1;
        }else if(g->huan == true) break;
    }
    if (g->huan) printf("有环\n");
    else printf("无环\n");
    return 0;
}

判断一个环是否为奇数环

1356: Catch

题意：给出一个起始点，一些边，有人从这个起始点开始随意走，问在某一个时候，它是否可以处于任意位置。

思路：思考下，就可以明白，只要是一个联通图，并且存在奇数点形成的环，那么在某一个时候就可以处于任意位置。

1
2


最大匹配数——匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;

const int maxn = 150;

int line[maxn][maxn]; // 邻接矩阵,表示男生是否有好感(可达)
int used[maxn];       // 在位男生i匹配的那轮中,女生i是否被尝试过匹配
int nxt[maxn];        // 如果匹配到了的话,那么男生是谁,女生i的对象为nxt[i]

int m, n, t;


/**
 * 为男生x匹配到一个女生i,如果匹配到的女生有主,那么让已配对女生的对象(男)修改匹配对象
 * @author mrli 2019-12-08
 * @param  x 男生
 * @return   男生x是否能匹配到女生
 */
bool Find(int x){
    // 遍历所有妹子Y节点
    for (int i = 1; i <= m; ++i){
        // 如果男生对女生互有好感(即边可达) 且 妹子没有匹配过
        if (line[x][i] && !used[i]){
            // 在男生该轮,将该女生i标记为已经被尝试匹配过
            used[i] = 1;
            //  如果妹子没有对象  或者  已匹配到的男生是可以转移对象的
            if ( nxt[i]==0 || Find( nxt[i]) ){
                // 将女生的已配对对象改为x
                nxt[i] = x;
                return true;
            }
            
        }
    }
    return false;
}

/**
 * 为所有男生进行匹配
 * @author mrli 2019-12-08
 * @return 最大匹配数
 */
int match(){
    // 最大匹配数
    int sum = 0;
    // 遍历所有男生X节点
    for (int i = 1; i <= n; ++i){
        // 在男生i该轮,所有女生都没有被修改过匹配
        memset(used, 0, sizeof(used));
        // 如果当前男生能找到匹配女生,那么最大匹配数++
        if (Find(i)) sum++;

    }
    return sum;
}

int main(int argc, char const *argv[]){
    int u, v;
    cin >> t;
    // XY节点数
    n = m = 4;
    memset(line, 0, sizeof(line));
    memset(nxt, 0, sizeof(nxt));
    while(t--){
        cin >> u >> v;
        line[u][v] = 1;
    }
    cout << match();
    return 0;
}

/**
input:
7
1 1
1 2
2 2
2 3
3 1
3 2
4 3
output:
3
 */

拓展题:无题II HDU2236

二分图：为什么会想到用二分图呢？不同行不同列，仔细想一下，如果某点（x,y），被选中，那么横坐标上x的值不能再选，纵坐标上的y值也不能再选，这相当于二维上有很多值，但是每个值都只能用一次，这就可以想到用二分图匹配求完美匹配了。

二分答案：求n个数的最大最小的差值最小，首先这个差值一定是**0-(maxv-minv)**区间的，然后我们二分差值为外循环，枚举下界为内循环，得到一个区间。做法：修改二分图匹配模板：如果这个二分图的匹配点是在这个区间里的前去匹配，hungry()函数中返回是否为完美匹配，对于每一个二分的差值，只要它能找到一个满足区间条件的完美匹配，就记录一下答案。

Q：首先明白在求什么

A： 首先需要明白：图中每个数值X + 最大差值 <= 最大值

我对上面的理解：

1.最大的差值是个具体的数值δ，最初可以确定的范围在[0, maxv - minv] 之间，因此可以通过二分搜索的方式来找到这个值==>二分搜索

2.那怎么进行二分来缩小这个区间范围呢?Ans：如果符合最大差值的条件(表中所有数都满足 ：数值x+差值 <= 最大值)，即所有点都能完成匹配，那么证明最大差值在这个区间中---->完美匹配==>匈牙利算法

▲所以算法变成了，不断缩小最大差值可以取值的区间，核心： 判断所有数是否在[p, p+差值]区间内

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

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

int line[maxn][maxn]; // 邻接矩阵,表示男生是否有好感(可达)
int used[maxn];       // 在位男生i匹配的那轮中,女生i是否被尝试过匹配
int nxt[maxn];        // 如果匹配到了的话,那么男生是谁,女生i的对象为nxt[i]

int m, n, t, maxv, minv;
int l, r, mid;
int p;


/***
input:
1
4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
*/
bool Find(int x){
    for (int i = 1; i <= m; ++i){
        // 修改模板：增加界定二分[p, p+mid]的区间
        // 判断边x是否还在[minv, minv+差值]之间
        /*if条件解释:执行过程分析
        如题,l=0, r=4,
        第一次mid=2,p=1, 此时并不是所有点都在[1, 1+2]之间,所以匹配失败
        因为1+2<=4(maxv),所以p++后再进入,此时mid=2,p=2,此时仍然不是所有点在这个范围[2,2+2]内,所以失败,第一次二分失败,区间不在[l,mid]即[0,2]之间
  		第二次更新l=mid+1=2+1=3,mid=(3+4)/2=3
  		p=1时,判断是否所有点都在[1,1+3]范围,==>结果是的,hungarian返回true,二分确定在[mid, r]即[3,4]之间,更新r=mid-1=3,mid=(l+r)/2=3,此时有l=r=3所以找到了最大差值mid
        */
        if(p <= line[x][i] && line[x][i]<= p+mid && !used[i]){
            used[i] = 1;
            if ( nxt[i]==0 || Find( nxt[i]) ){
                nxt[i] = x;
                return true;
            }
        }
    }
    return false;
}

int hungarian(){
    int sum = 0;
    // 这边改了，每次都是新情况
    memset(nxt, 0, sizeof(nxt));
    for (int i = 1; i <= n; ++i){
        memset(used, 0, sizeof(used));
        if (Find(i)) sum++;
    }
    // 修改模板
    return sum==n?1:0;
}

int main(int argc, char const *argv[]){
    int size;
    cin >> t;
    while(t--){
        cin >> size;
    	m = n = size;
        maxv = -inf;
        minv = inf;
        for (int i = 1; i <= size; ++i){
            for (int j = 1; j <= size; ++j){
                cin >> line[i][j];
                maxv = max(maxv, line[i][j]);
                minv = min(minv, line[i][j]);
            }
        }

        l = 0;
        r = maxv - minv;
        int ans = 0;
        // 二分搜索，不断缩小区间
        while( l <= r){
            bool flag = false;
            mid = (l+r) >> 1;	// mid为差值
            // 遍历下界的搜索,枚举最小值，检查当前差值是否可以匹配成功,条件是“最小值+差值<=最大值”
            // 核心： 判断所有数是否在[p, p+差值]区间内
            for (p = minv; p+mid <= maxv; ++p){
                if (hungarian()){	
                // 这句类似二分搜索里的if一旦找到哪个区间，就直接在这个区间里继续二分，
                    flag = true;
                    break;
                }
            }
            // 因为是从[min,min+mid]~[max-mid, max]的搜索,区间大小为mid,如果true,意思是最大差值mid就在[l, mid]之间
            if (flag) ans = mid,r = mid-1;
            // 如果全不符合,那么区间小了,mid得大点,所以mid范围变为[mid, r]
            else l = mid+1;
        }
		// 二分搜索中如果l==r，那么搜索数x的索引就是最后的mid
        cout << ans << endl;
    }
    return 0;
}

最佳匹配——KM算法

解决有权的完美匹配问题，成为最佳匹配，又称为有权完美匹配。最佳匹配同时也是完备匹配

KM算法详解+模板——含图讲解

Author: Mrli

Link: https://nymrli.top/2019/12/05/ACM-二分图/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
KM(Kuhn-Munkres)算法NextPost >
Hungarian algorithm匈牙利算法
CATALOG
  1. 1. 二分图的判定：
    1. 1.1. 判断无向图是否有环
    2. 1.2. 判断一个环是否为奇数环
  2. 2. 最大匹配数——匈牙利算法
  3. 3. 最佳匹配——KM算法