搜索与图论

树与图的存储

树是一种特殊的图，所以我们只需要掌握图的存取就可以，对于无向边，我们存储两条有向边，那么我们只考虑有向图的存储就可以了

存储方式

领接矩阵：用来存储稠密图
领接矩阵：g[a][b]存储 a->b 的权重
领接表：

1
2
3
4
5
6
7
8
9
10
11
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
    //存下b的值，b下一个指向a的下个一节点，a的下一个节点指向b
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

dfs 深度优先遍历

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

示例 1：全数字排列

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
#include <iostream>

using namespace std;

int res[10],b[10],n;

void dfs(int k){
    if(k==n){//k==n则输出n个数字
        for(int i=0;i<n;i++)printf("%d ",res[i]);
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        if(!b[i]){//判断是否被用过
            res[k]=i;//当前k位存入位置
            b[i]=1;//表示被占用
            dfs(k+1);
            b[i]=0;//恢复现场
        }
    }
}

int main(){
    cin>>n;
    dfs(0);//从0开始枚举
    return 0;
}

示例 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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;//无向图n条边时，最多2n个idx，因为每条边在邻接表中会出现两次

int n;//n个结点,n-1条边
int h[N], e[M], ne[M], idx;//n个链表头，e每一个结点的值，ne每一个结点的next指针
int ans = N;//最小的最大值
bool st[N];//状态数组，防止子节点搜索父节点

void add(int a, int b)//a->b
{//e记录当前点的值(地址->值),ne下一点的地址(地址->地址)，h记录指向的第一个点的地址(值->地址)
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;

}//头插法

int dfs(int u)//通过h数组找到子结点的向
{
    st[u] = true;//st标记当前点被搜过

    int size = 0, sum = 0;
    //size删掉元素后各个子连通块的最大值
    //sum当前子树大小，遍历叶节点时，返回1

    for (int i = h[u]; i != -1; i = ne[i])//遍历单链表，链表末端初始化为-1
    {
        int j=e[i];
        if(st[j])continue;//此处防逆向dfs
        int s = dfs(j);//s各个子连通块的大小
        size = max(size, s);//size删掉元素后各个连通块的最大值
        sum += s;//各个连通块大小之和
    }

    size = max(size, n - sum - 1);//判断最大子连通块与父连通块的最大值
    ans = min(ans, size);//全局变量ans存最小的最大值
//注意：本题若求最大的最大值，则只需去除任意叶节点即可，即n-1
    return sum + 1;//各个子连通块，当前结点之和
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);//n个头节点全部指向-1

    for (int i = 0; i < n - 1; i ++ )//n个结点，n-1条边
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);//不知道子节点还是父节点，所以需要建两条边可以双向查找
    }

    dfs(1);//结点编号为1~n且可能只有一个结点，则参数只能为1
    printf("%d\n", ans);
    return 0;
}

示例 3：n 皇后问题

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
using namespace std;

const int N = 11;

char q[N][N];//存储棋盘
bool dg[N * 2], udg[N * 2], cor[N];//点对应的两个斜线以及列上是否有皇后

int n;

void dfs(int r)
{
    if(r == n)//放满了棋盘，输出棋盘
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                cout << q[i][j];
            cout << endl;
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < n; i++)//第 r 行，第 i 列 是否放皇后
    {
        if(!cor[i] && !dg[i + r] && !udg[n - i + r])//不冲突，放皇后
        {
            q[r][i] = 'Q';
            cor[i] = dg[i + r] = udg[n - i + r] = 1;//对应的 列， 斜线 状态改变
            dfs(r + 1);//处理下一行
            cor[i] = dg[i + r] = udg[n - i + r] = 0;//恢复现场
            q[r][i] = '.';
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            q[i][j] = '.';
    dfs(0);
    return 0;
}

bfs 宽度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

示例 1:走迷宫

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
typedef pair<int,int> PII;//声明pair时候必须要在代码前面写上using namespace std;

const int N=110;
int g[N][N],f[N][N],n,m;

int bfs(int x,int y){
    queue<PII> que;
    que.push({x,y});
    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    while(!que.empty()){
        PII t=que.front();
        que.pop();
        g[t.first][t.second]=1;
        for(int i=0;i<4;i++){
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a>=0&&b>=0&&a<n&&b<m&&!g[a][b]){
                g[a][b]=1;
                f[a][b]=f[t.first][t.second]+1;
                que.push({a,b});
            }
        }
    }
    return f[n-1][m-1];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&g[i][j]);
    cout<<bfs(0,0)<<endl;
    return 0;
}

示例 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
using namespace std;

int bfs(string state) {
    queue<string> q;
    unordered_map<string, int> d;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    string ed = "12345678x";
    q.push(state);
    d[state] = 0;

    while (q.size()) {
        auto t = q.front();
        q.pop();
        if (t == ed)//等于结果就输出步数
            return d[t];
        int distance = d[t];
        int k = t.find('x');//寻找x
        int x = k / 3, y = k % 3;//计算下标
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                swap(t[a * 3 + b], t[k]);//交换
                if (!d.count(t)) {//不存在就入队
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);//还原
            }
        }
    }
    return -1;
}

int main() {
    char s[2];
    string state;
    for (int i = 0; i < 9; i ++ ) {
        cin >> s;
        state += *s;
    }
    cout<<bfs(state)<<endl;
    return 0;
}

拓扑排序

拓扑序：一个有向图，没有环的一个有向图。
算法思路：

  1. 所有入度为 0 的点入队
  2. 宽搜
1
2
3
4
5
6
7
8
while(queue不空){
    t指向对头；
    枚举t的所有出边，入度-1；
    if(入度为0)
    {
        加入队列
    }
}

最后查看队列长度是否等于节点的个数，若相等，则存在拓扑序
示例

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
using namespace std;
const int N = 100010;
int e[N], ne[N], idx; //邻接表存储图
int h[N];//邻接表的每个头链表
int q[N], hh = 0, tt = -1; //队列保存入度为0的点，也就是能够输出的点
int n, m; //保存图的点数和边数
int d[N];//保存各个点的入度

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

void topsort() {
    for (int i = 1; i <= n; i++) {//遍历一遍顶点的入度。
        if (!d[i])//如果入度为0，则可以入队列
            q[++tt] = i;
    }
    while (tt >= hh) { //循环处理队列中点的
        int a = q[hh++];
        for (int i = h[a]; i != -1; i = ne[i]) {
            int b = e[i]; //a 有一条边指向b
            d[b]--;//删除边后，b的入度减1
            if (!d[b])//如果b的入度减为 0,则 b 可以输出，入队列
                q[++tt] = b;
        }
    }
    if (tt == n - 1) {//如果队列中的点的个数与图中点的个数相同，则可以进行拓扑排序
        for (int i = 0; i < n; i++)//队列中保存了所有入度为0的点，依次输出
            printf("%d ", q[i]);
    } else//如果队列中的点的个数与图中点的个数不相同，则可以进行拓扑排序
        cout << -1;
}

int main() {
    cin >> n >> m; //保存点的个数和边的个数
    memset(h, -1, sizeof h); //初始化领接矩阵
    while (m--) { //依次读入边
        int a, b;
        cin >> a >> b;
        d[b]++;//顶点b的入度+1
        add(a, b); //添加到邻接矩阵
    }
    topsort();//进行拓扑排序
    return 0;
}

最短路问题

  1. 单源最短路：一个点到其它点的最短路

    • 所有边权均为正数：
      • 朴素版的 Dijakstra（领接表，稠密图）
      • 堆优化的 Dijakstra (使用小根堆优化，稀疏图)
      • SPFA 算法
    • 存在负权边：
      • Bellman-Ford（经过 k 条边的最短路）
      • SPFA（求有无负环）

  2. 多源最短路：多个起点多个终点

    • Floyd 算法

朴素版 dijakstar 算法

时间复杂度：O(n^2+m),n 表示点数，m 表示边数
算法思路：

1
2
3
4
5
6
7
8
1.初始化距离：dist[1]=0,dist[i]为无穷大
2.for(int i=0;i<n;i++)
{

    t为不在S(当前已经确定最短距离的点的集合)中距离最近点；
    用t来更新其它所有点的距离；
    dist[x]=dist[t]+w;
}

算法模版：

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
onst int N = 510, M = 100010;

int h[N], e[M], ne[M], w[M], idx;//邻接表存储图
int state[N];//state 记录是否找到了源点到该节点的最短距离
int dist[N];//dist 数组保存源点到其余各个节点的距离
int n, m;//图的节点个数和边数

void add(int a, int b, int c)//插入边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));//dist 数组的各个元素为无穷大
    dist[1] = 0;//源点到源点的距离为置为 0
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)//遍历 dist 数组，找到没有确定最短路径的节点中距离源点最近的点t
        {
            if (!state[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

        state[t] = 1;//state[i] 置为 1。

        for (int j = h[t]; j != -1; j = ne[j])//遍历 t 所有可以到达的节点 i
        {
            int i = e[j];
            dist[i] = min(dist[i], dist[t] + w[j]);//更新 dist[j]
        }


    }
}

int main()
{
    memset(h, -1, sizeof(h));//邻接表初始化

    cin >> n >> m;
    while (m--)//读入 m 条边
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
    }

    Dijkstra();
    if (dist[n] != 0x3f3f3f3f)//如果dist[n]被更新了，则存在路径
        cout << dist[n];
    else
        cout << "-1";
}

堆优化版的 dijakstar

使用优先队列来优化 Dijakstra 算法，用领接表来存储
算法模版：

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
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
    memset(dist,0x3f,sizeof dist);//距离初始化为无穷大
    dist[1]=0;//1->1的节点距离为0
    priority_queue<PII,vector<PII>,greater<PII>> heap;//小根堆
    heap.push({0,1});//插入距离和节点编号

    while(heap.size()){
        auto t=heap.top();//取距离源点最近的点
        heap.pop();

        int ver=t.second,distance=t.first;//ver：节点编号，distance源点距离ver
        if(st[ver])continue;//如果距离已经确定，则跳过该点
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])//更新ver所指向的节点距离
        {
            int j=e[i];
            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});//距离变小，则入堆
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}

Bellman-Ford 算法

时间复杂度 O(nm),n 表示点数，m 表示边数，用结构体来存储
算法思路：

1
2
3
4
5
6
7
for(int i=0;i<n;i++)
{
    备份一下更新的距离
    for(枚举所有边)
        dist[b]=min(dist[b],dist[a]+w)
}
若迭代k次，表示从一号点经过不超过k条走到每个点的最短距离

算法模版：

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
int n,m,k;
const int N=512,M=10012;
struct Edge{
    int a,b,w;
}e[M];
int dist[N];
int back[N];
void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){
        memcpy(back,dist,sizeof dist);
        for(int j=0;j<m;j++){
            int a=e[j].a,b=e[j].b,c=e[j].w;
            dist[b]=min(dist[b],back[a]+c);
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        e[i]={a,b,w};
    }
    bellman_ford();
    if(dist[n]>0x3f3f3f3f/2)cout<<"impossible"<<endl;
    else cout<<dist[n]<<endl;
    return 0;
}

SPFA 算法(队列优化的 Bellman-Ford 算法)

时间复杂度平均情况下 O(m)，最坏情况下 O(nm)，n 表示点数，m 表示边数
算法思路：

1
2
3
4
5
6
7
1. 1号点入队(因为试求1号点到每个点的最短距离，所以把1号点入队，有时需要将所有点入队，请根据具体问题具体分析)
2. while(队列不空)
{
    1.取出队头复制给t，删除队头元素
    2.更新t的所有出边
    3.将更新后的元素插入到队尾
}

算法模版：

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
const int N = 1e6 + 10;

int n, m;//节点数量和边数
int h[N], w[N], e[N], ne[N], idx;//邻接矩阵存储图
int dist[N];//存储距离
bool st[N];//存储状态

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);//距离初始化为无穷大
    dist[1] = 0;//初始化1到1的距离为0
    queue<int> que;//队列
    que.push(1);//1入队

    while (que.size())//判断是否存在
    {
        int t=que.front();
        que.pop();//获取第一个并出队
        st[t]=false;//第一个取消占用
        for(int i=h[t];i!=-1;i=ne[i]){//遍历第一个可以到达的结点
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){//1号点可到达的节点距离是否大于上次的距离距离加上当前的距离
                dist[j]=dist[t]+w[i];//赋值给可到达的节点
                if(!st[j]){//如果可到达的节点未被占用
                    que.push(j);//则入队
                    st[j]=true;//占用
                }
            }
        }
    }

    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t=spfa();
    if(t==0x3f3f3f3f)cout<<"impossible"<<endl;
    else printf("%d\n",t);

    return 0;
}

应用：判断是否存在负环

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

floyd 算法 O(n^3)

算法思路：

1
2
3
4
5
基于动态规划，使用邻接矩阵来存储所有边d[i,j](存储i->j的最短距离)
for(k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

算法模版：

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
using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

void floyd()
{
    for (int k = 1; k <= n; k ++ )//k为中转节点
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}

最小生成树问题(无向图)

最小生成树的核心是 “用最少的代价连接所有节点”

  1. 普里姆算法(prim)
    • 朴素版 Prim:稠密图
    • 用堆优化的 Prim：稀疏图
  2. 克鲁斯卡尔算法(kruskal)：稀疏图

Prim 算法

时间复杂度:O(n^2+m),n 表示点数，m 表示边长

算法思路：

1
2
3
4
5
6
1. 初始化：所有节点的距离定义为无穷大
2.  for(int i=0;<n;i++)
    {
        找到不在集合中的距离最近的点设为t，用t来更新
        到其他点到集合S的距离
    }

算法模版：

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
onst int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

Kruskal 算法

时间复杂度 O(mlogm)，n 表示点数，m 表示边数
算法思路：

1
2
3
1.用结构体来存储每条边
2.将所有边按从小到大的方式排序
3.枚举每条边 if(a和b不连通)，将这条边加入集合

算法模版：

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

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

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

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

    int t = kruskal();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

二分图

二分图（Bipartite Graph）是指顶点可划分为两个不相交的非空集合 U 和 V，使得图中所有边的两个端点分别属于 U 和 V（即同一集合内的顶点之间没有边）。

  • 若一个图为二分图，当且仅当图中不含奇数环
  • 一个二分图可以分为两部分，集合内无边，集合外有边

染色法判定二分图

Dfs 实现

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
using namespace std;

const int N = 100010, M = 200010;// 由于是无向图, 顶点数最大是N，那么边数M最大是顶点数的2倍

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

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = 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])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);// 无向图，a->b, b->a
    }

    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }

    if (flag) puts("Yes");
    else puts("No");

    return 0;
}

BFS 实现

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
// BFS版本染色法判定二分图
bool bfs(int start, int c) {
    queue<int> q;
    q.push(start);
    color[start] = c;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!color[j]) {
                color[j] = 3 - color[u]; // 染相反颜色
                q.push(j);
            } else if (color[j] == color[u]) {
                return false; // 相邻同色，不是二分图
            }
        }
    }
    return true;
}

// 在main函数中调用时，将dfs替换为bfs即可
for (int i = 1; i <= n; i++) {
    if (!color[i]) {
        if (!bfs(i, 1)) {
            flag = false;
            break;
        }
    }
}

匈牙利算法求二分图最大匹配

匈牙利算法的核心是通过寻找增广路来扩大匹配规模：
增广路是一条 “未匹配边 → 匹配边 → 未匹配边 →…→ 未匹配边” 的路径，起点和终点都是未匹配顶点。
反转增广路上的边（匹配边变未匹配边，未匹配边变匹配边）后，匹配数会增加 1（因为起点和终点变为匹配顶点，中间顶点匹配关系不变）。
假设初始匹配为 (1−4)，尝试匹配 2 时发现 4 已被匹配，但 4 的匹配对象 1 可以改匹配 5，于是增广路为 2−4−1−5，反转后匹配变为 (2−4,1−5)，匹配数从 1 增加到 2。

  • 匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。
  • 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
  • 完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
  • 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
  • 增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替 路称为增广路（agumenting path）。
    算法模版：
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
using namespace std;

const int N = 510, M = 100010;

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

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

bool find(int x)
{
     // 和各个点尝试能否匹配
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])//打标记
        {
            st[j] = true;
            // 当前尝试点没有被匹配或者和当前尝试点匹配的那个点可以换另一个匹配
            if (match[j] == 0 || find(match[j]))
            {
                // 和当前尝试点匹配在一起
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d%d", &n1, &n2, &m);

    memset(h, -1, sizeof h);
    // 保存图，因为只从一遍找另一边，所以该无向图只需要存储一个方向
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    int res = 0;
    //为各个点找匹配
    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st);
        //找到匹配
        if (find(i)) res ++ ;
    }

    printf("%d\n", res);

    return 0;
}