image.png

最小生成树

prim算法O(n^2)

  • 循环n次
  • 每次循环判断哪个节点离最小生成树集合更近，并加入最小生成树集合 ```cpp

    include

    include

    using namespace std;

const int N = 510, M = 100010; int n, m; int g[N][N], dist[N]; bool st[N];

int prim() { // dist represent distance from node to tree memset(dist, 0x3f, sizeof(dist)); int res = 0; // loop n time for (int i = 0; i < n; i ++) { // get min distance node int t = -1, r = 0x3f3f3f3f + 1; for (int j = 1; j <= n; j ++) { if (st[j] == true) { continue; } if (dist[j] < r) { r = dist[j]; t = j; } } if (i && r == 0x3f3f3f3f) { return r; }

  1.     st[t] = true;
  2.     if (i != 0) {
  3.         res += r;
  4.     }
  6.     for (int j = 1; j <= n; j ++) {
  7.         dist[j] = min(dist[j], g[t][j]);
  8.     }
  9. }
  10. return res;

}

int main() { memset(g, 0x3f, sizeof(g)); scanf(“%d%d”, &n, &m); for (int i = 0; i < m; i ++) { int a, b, c; scanf(“%d%d%d”, &a, &b, &c); g[a][b] = g[b][a] = min(g[a][b], c); }

auto ans = prim();
if (ans == 0x3f3f3f3f) {
    cout << "impossible" << endl;
} else {
    cout << ans << endl;
}
return 0;

}

<a name="t5imU"></a>
### kruskal算法O(m logm)

- 对所有边排序
- 依次判断所有边，两端点是否在同一集合，如果不在，加入最小生成树
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

#define N 100010
#define M (2 * N)
int r[N], cnt[N];
int n, m;

struct Edge {
    int a, b, c;
} edge[M];

static bool cmp(const Edge &A, const Edge &B) {
    return A.c < B.c;
}

int find(int x) {
    if (r[x] != x) {
        r[x] = find(r[x]);
    }
    return r[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) {
        r[i] = i;
    }
    for (int i = 0; i < m; i ++) {
        scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].c);
    }

    sort(edge, edge + m, cmp);
    int ans = 0, cnt = 0;

    for (int i = 0; i < m; i ++) {
        int ra = find(edge[i].a);
        int rb = find(edge[i].b);
        if (ra == rb) {
            continue;
        }
        cnt ++;
        r[ra] = rb;
        ans += edge[i].c;
    }

    if (cnt == n - 1) {
        cout << ans << endl;
    } else {
        cout << "impossible" << endl;
    }

    return 0;
}

二分图

染色法判断一个图是否为二分图

  • 思想其实就是图的遍历，遍历过程中判断相邻的点是否为不同颜色

    DFS版本

    ```cpp

    include

    include

    using namespace std;

define N 100010

define M (2*N)

int h[N], color[N]; int e[M], ne[M]; int idx, n, m, cnt;

void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx; idx ++; }

bool dfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == c) { return false; } if (color[j] != -1) { continue; } if (dfs(j, (c + 1) % 2) == false) { return false; } } return true; }

int main() { memset(h, -1, sizeof h); memset(color, -1, sizeof color); scanf(“%d%d”, &n, &m); for (int i = 0; i < m; i ++) { int a, b; scanf(“%d%d”, &a, &b); add(a, b); add(b, a); }

for (int i = 1; i <= n; i ++) {
    if (color[i] == -1) {
        if (dfs(i, 0) == false) {
            cout << "No" << endl;
            return 0;
        }
    }
}
cout << "Yes" << endl;
return 0;

}

<a name="cD9tx"></a>
#### BFS版本
```cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define N 100010
#define M 200010

int h[N], e[M], ne[M], idx;
int n, m;
int a, b;
int color[N];
queue<int> q;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int bfs() {
    for(int i = 1; i <= n; i ++) {
        if (color[i] != 0) {
            continue;
        }
        color[i] = 1;
        q.push(i);

        while (q.size()) {
            int x = q.front();
            q.pop();
            for (int j = h[x]; j != -1; j = ne[j]) {
                if(color[e[j]] == 0) {
                    color[e[j]] = -1 * color[x];
                    q.push(e[j]);
                } else if (color[e[j]] == color[x]) {
                    return -1;
                }
            }
        }
    }
    return 0;
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF){
        memset(h, -1, sizeof h);
        idx = 0;
        memset(color, 0, sizeof color);

        for(int i = 0; i < m; i ++) {
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }

        int res = bfs();
        if(res == -1) {
            printf("No\n");
        } else {
            printf("Yes\n");
        }
    }
    return 0;
}

匈牙利算法

  • 算法的思路是依次看二分图的左半边，依次为每一个左边“男生”挑选右边的“女生”
  • 假设该女生没有对应的伴侣，则匹配成功；如果该女生有对应的伴侣，而该女生的伴侣还有其他的选择，则挖墙脚成功，该女生和该男生成为伴侣，之前的伴侣另找新欢。
  • 如果所有女生都匹配失败，该男生无法匹配。 ```cpp

    include

    include

    using namespace std;

define N 510

define M 100010

int h[N], match[N]; bool st[N]; int e[M], ne[M]; int idx; int n1, n2, m;

void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; }

bool find(int u) { for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (st[j]) continue; st[j] = true; if (match[j] == 0 || find(match[j])) { match[j] = u; return true; } } return false; }

int main() { memset(h, -1, sizeof h); scanf(“%d%d%d”, &n1, &n2, &m); while(m —) { int a, b; scanf(“%d%d”, &a, &b); add(a, b); }

int ans = 0;
for (int i = 1; i <= n1; i ++) {
    // 需要挖墙脚，所以换人了之后，还是要考虑匹配完成的一方
    memset(st, 0, sizeof st);
    if (find(i)) {
        ans ++;
    }
}

cout << ans << endl;
return 0;

} ```