排列数字

利用深搜，设置一个数组用来存储走过的“路径”， 还有一个标记数组用来看这个数有没有用过

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
#include <iostream>
using namespace std;
int n;	
const int N = 10;
int path[N], st[N];
void dfs(int x)
{
    if(x > n)     
    {
        for(int i = 1; i<= n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            path[x] = i;
            st[i] = true;
            dfs(x + 1);
            st[i] = false;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

n皇后

设置三个参数，一个用来表示横行、一个竖行、一个表示当前已经有的皇后个数，一有冲突就让y++，当y走到头就让y重新回到0，然后让x向下移，设置四个bool数组，表示横行、纵行、正斜线、反斜线是否已经放了皇后

法一：

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
char place[N][N];
bool row[N], col[N], dg[N], udg[N];
int n;  
void dfs(int x, int y, int s)
{
    if(y == n) y = 0, x++;
    if(x == n)
    {
        if(s == n)
        {
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    cout << place[i][j];
                }
                cout << endl;
            }
            cout << endl;
        }
        return;
    }
    if(!row[x] && !col[y] && !dg[x - y + n] && ! udg[x + y])
    {
        row[x] = col[y] = dg[x - y + n] = udg[x + y] = true;
        place[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
         row[x] = col[y] = dg[x - y + n] = udg[x + y] = false;
        place[x][y] = '.';
    }
    dfs(x , y + 1, s);
}
int main()
{
    cin >> n;
    //memset(place, '.', sizeof place);
    for(int i = 0;i < n; i++)
        for(int j = 0; j < n; j++)
        place[i][j] = '.';
    dfs(0, 0, 0);
    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
#include <iostream>
using namespace std;
const int N = 20;
char place[N][N];
bool row[N], col[N], dg[N], udg[N];
int n;
void dfs(int x)//遍历x行
{
    if(x == n)//结束条件
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                cout << place[i][j];
            }
            cout << '\n';
        }
        cout << '\n';
        return;
    }
    for(int y = 0; y < n; y++)//遍历每一个列
    {
        if(!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n])
        {
            row[x] = col[y] = dg[x + y] = udg[y - x + n] = true;
            place[x][y] = 'Q';
            dfs(x + 1);
            row[x] = col[y] = dg[x + y] = udg[y - x + n] = false;
            place[x][y] = '.';
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) 
            place[i][j] = '.';
    dfs(0);
    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
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 110;
int g[N][N];
int d[N][N];
typedef pair<int, int> PII;
queue<PII> q;
int n, m;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int bfs()
{
    q.push({0, 0});
    d[0][0] = 0;
    while(q.size())
    {
        auto [a, b] = q.front();
        q.pop();
        for(int i = 0; i <4; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && !g[x][y] && d[x][y] == -1)
            {
               d[x][y] = d[a][b] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}
int main()
{
    memset(d, -1, sizeof(d));
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> g[i][j];
    
    cout << bfs();
    return 0;
}

八数码

将初始的状态和最后的状态转换成字符串，找到字符串中字符的位置和9宫格中字符位置的关系，对字符串进行操作

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
#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
string ed = "12345678x";
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
unordered_map<string, int> d;
queue<string> q;
string  start;
int bfs()
{
    d[start] = 0;
    q.push(start);
    while(q.size())
    {
        string t = q.front();
        q.pop();
        int dis = d[t];
        if(t == ed) return dis;
        int k = t.find('x');//找到x在字符串中的位置
        for(int i = 0; i < 4; i++)
        {
            int a = k / 3, b = k % 3;
            int x = a + dx[i], y =  b + dy[i];
            if(x >= 0 && x < 3 && y >= 0 && y < 3)
            {
                swap(t[k], t[x * 3 + y]);
                if(!d.count(t))//如果这个样子的字符串没有出现过
                {
                    d[t] = dis + 1;
                    q.push(t);
                }
                swap(t[k], t[x * 3 + y]);
            }
        }
    }
    return -1;
}
int main()
{
    for(int i = 0; i < 9; i++) //因为输入的时候有空格，所以不能直接cin >> start
    {
        char x;
        cin >> x;
        start += x;
    }
    cout << bfs();
    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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], to[M], ne[M], idx;//链式前向星
bool st[N];
int n, ans = N;
void add(int x, int y)//链式前向星
{
    to[idx] = y;
    ne[idx] = h[x];
    h[x] = idx++;
}
int dfs(int u)
{
    st[u] = true;//从u开始深搜
    int size = 0, sum = 0;//size用来记录连通块中的最大值，sum用来记录下面所有连通块所拥有的结点个数，用来计算上面剩下的结点数
    for(int i = h[u]; i != -1; i = ne[i])//遍历，开始深搜
    {
        int j = to[i];
        if(st[j]) continue;
        
        int s = dfs(j);//这一条通路下面的所有结点数
        size = max(size, s);//最大的连通块
        sum += s;//下面所有的结点个数
    }
    size = max(size, n - sum - 1);//将下面的最大连通块个数和上面那个剩余的连通块比较，看哪个大
    ans = min(ans, size);//最大连通块中的最小值
    return sum + 1;//返回下面连通块的数量
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);//构图
    }
    dfs(1);
    cout << ans;
    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
46
47
48
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int to[N], h[M], ne[M], idx;
int d[N];
int n, m;
void add(int a, int b)//构图
{
    to[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs(int x)//广搜
{
    d[1] = 0;
    queue<int> q;
    q.push(1);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = to[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}
int main()
{
    memset(h, -1, sizeof h);//不要忘记初始化
    memset(d, -1, sizeof d);
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs(1);
    return 0;
}

图的拓扑排序

每次将度为0的节点加入到“队列”中

用链式前向星存图，不要忘记初始化head数组！！！！

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int to[N], ne[M], head[M], idx;
int d[N], q[N];
int n, m;
void add(int x, int y)
{
    to[idx] = y, ne[idx] = head[x], head[x] = idx++;
}
bool TopSort()
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i++) if(!d[i]) q[++tt] = i;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = head[t]; i != -1; i = ne[i])
        {
            int j = to[i];
            if(--d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }
    if(!TopSort()) cout << -1;
    else
        for(int i = 0; i < n; i++) cout << q[i] << " ";
    return 0;
}

Dijkstra求最短路\(O(n^2)\)

设置一个集合，st为true就是在集合里面，否则就是不在那个集合里面；每次求不在集合里面的点到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
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int g[N][N];
bool st[N];
int dist[N];
int n, m;
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n - 1; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//找到距离1距离最小的点，并且这个点不在集合中
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        st[t] = true;//加入到集合中
        for(int j = 1; j <= n; j++)//更新距离
        {
            if(dist[j] > dist[t] + g[t][j]) dist[j] = dist[t] + g[t][j];
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f3f, sizeof g);
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    } 
    cout << dijkstra();
    return 0;
}

Dijsktra求最短路（堆优化版）(O(mlogm))

用priority_queue进行优化，使得找到距离1最近点的时间复杂度变为O(1)，以类似于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
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
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5e4 + 10, M = 2 * N;
int to[N], h[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int n, m;   

typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q;

void add(int x, int y, int z)
{
    to[idx] = y;
    ne[idx] = h[x];
    w[idx] = z;
    h[x] = idx++; 
}
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push({0, 1});
    while(q.size())
    {
        auto t = q.top();
        int d = t.first, x = t.second;
        q.pop();
        if(st[x]) continue;
        st[x] = true;
        for(int i = h[x]; i != -1; i = ne[i])
        {
            int j = to[i];
            if(dist[j] > dist[x] + w[i])
            {
                dist[j] = dist[x] + w[i];
                q.push({dist[j], j});
            }
        }
    }
    if(dist[n] != 0x3f3f3f3f) return dist[n];
    return -1;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    cout << dijkstra();
    return 0;
}

Spfa(处理存在负边权的情况)(O(mk))

因为边权可能为负值，只能用spfa算法，不能用dijkstra算法；spfa算法是以“层序”的方式进行不断更新节点距离，也就是说，会用某一层的所有结点去更新下一层次的节点，而不是像dijkstra一样使用贪心的策略，这样就可以保证即使前面的边权大、后面有负边权也可以更新到。

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int to[N], ne[N], w[N], head[N], idx;
int dist[N];
bool st[N];
int n, m;
queue<int> q;
void add(int x, int y, int z)
{
    to[idx] = y, ne[idx] = head[x], w[idx] = z, head[x] = idx++;
}
void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    st[1] = true;
    q.push(1);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = head[t]; i != -1; i = ne[i])
        {
            int j = to[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    spfa();
    if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible";
    else cout << dist[n];
    return 0;
}

Spfa判断是否存在负环(O(n)~O(mn))

如果存在负环，那么一旦进入这个负环，就会一直循环，因为只要在负环里面dist就会一直减，所以可以计算每个节点距离最短的路上有几个结点，如果大于等于n必定存在负环，因为如果只存在正环或者不存在环，那么最长的应该是n-1；因为负环不一定是从结点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
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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 2010,M = 10010;
int to[M], ne[M], w[M], head[N], idx;
bool st[N];
int dist[N], cnt[N];
int n, m;
void add(int x, int y, int z)
{
    to[idx] = y, ne[idx] = head[x], w[idx] = z, head[x] = idx++;
}
bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = head[t]; i != -1; i = ne[i])
        {
            int j = to[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;
                if(!st[j]) 
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    if(spfa()) cout << "Yes";
    else cout << "No";
    return 0;
}

Spfa的SLF优化

对于要加入到队列中的u，如果dist[u]要小于队首元素v的dist[v]，则加入到队头，否则加入到队尾；这时候就需要用双端队列dque

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
deque<int> q;
void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    st[1] = true;
    q.push_back(1);
    while(q.size())
    {
        int t = q.front();
        q.pop_front();
        st[t] = false;
        for(int i = head[t]; i != -1; i = ne[i])
        {
            int j = to[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    //添加部分
                    if(q.size() && dist[j] < dist[q.front()])
                        q.push_front(j);
                    else q.push_back(j);
                }
            }
        }
    }
}

BellmanFord（处理有限制条件的情况）(O(mn))

利用一个循环，保证循环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
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], cpy[N];
struct Edge
{
    int a, b, w;
}edges[M];

void BellmanFord()
{
    memset(dist, 0x3f3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < k; i++)
    {
        memcpy(cpy, dist, sizeof dist);
        for(int j = 0; j < m; j++)
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], cpy[e.a] + e.w);
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    int x, y, z;
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y >> z;
        edges[i].a = x, edges[i].b = y, edges[i].w = z;
    }
    BellmanFord();
    if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n];
    return 0;
}

Floyd\((O(n^3))\)

  1. 不能处理负边权回路
  2. \(d[i][j]\)表示从i到j的距离
  3. floyd中必须先遍历k，因为最后遍历k会导致更新i、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
#include <iostream>
using namespace std;
const int N = 210, M = 20010, INF = 1e9;
int d[N][N];
int n, m, x, y, z;
void floyd()
{
    for(int 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]);
            }
        }
    }
}
int main()
{
    int k;
    cin >> n >> m >> k;
    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--)
    {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
    }
    floyd();
    while(k--)
    {
        cin >> x >> y;
        if(d[x][y] > INF / 2) cout << "impossible" << '\n';
        else cout << d[x][y] << '\n';
    }
    return 0;
}

Prim求最小生成树

类似于dijkstra算法，每次循环找到一个最近的节点加入到最小生成树中，要考虑孤立点！！！需判断这个点的距离是不是无穷大，即判断是否连通，如果不联通就输出impossible，如果符合要求就更新距离

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 1e5 + 10;
int dist[N], st[N];
int g[N][N];
int n, m, u, v, w;
void prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    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[j] < dist[t])) t = j;
        }
        if(dist[t] == 0x3f3f3f3f) 
        {
            cout << "impossible";
            return;
        }
        st[t] = 1;
        res += dist[t];
        for(int i = 1; i <= n; i++)
        {
            if(dist[i] > g[i][t] && !st[i]) dist[i] = g[i][t];
        }
    }
    cout << res;
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m--)
    {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }
    prim();
    return 0;
}

Kruskal求最小生成树

  1. 根据边的权值大小从小到大排序
  2. 每次取一条边，利用并查集判断是否会形成环（即它的两个节点是否在一个集合）
  3. 最后根据取的边的数量，如果小于n - 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 20;
int p[N];//保存并查集
struct E
{
    int a, b, w;
    bool operator < (const E& e)
    {
        return this->w < e.w;
    }
}edges[N * 2];
int n, m;
int res = 0, cnt = 0;
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void Kruskal()
{
    for(int i = 1; i <= m; i++)
    {
        int pa = find(edges[i].a);
        int pb = find(edges[i].b);
        if(pa != pb)
        {
            res += edges[i].w;
            cnt++;
            p[pa] = pb;
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }
    sort(edges + 1, edges + m + 1);
    Kruskal();
    if(cnt < n - 1) cout << "impossible";
    else cout << res;
    return 0;
}

染色法判定二分图

利用dfs，没染色设为0，a颜色为1，b颜色为2，两个相连，一个染a一个染b，即一个是1，另一个是3 - 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010 * 2;//因为是无向图，存两遍
int to[N], ne[N], head[N], idx;
int n, m;
int color[N];//0是未染色，1是红色，2是黑色
void add(int x, int y)
{
    to[idx] = y, ne[idx] = head[x], head[x] = idx++;
}
bool dfs(int u, int c)
{
    color[u] = c;
    for(int i = head[u]; i != -1; i = ne[i])
    {
        int j = to[i];
        if(!color[j])//如果未涂色
        {
            if(!dfs(j, 3 - c)) return false;//染色并递归
        }
        else if(color[j] && color[j] != 3 - c)//如果染色了并且矛盾 
            return false;
    }
    return true;
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    while(m--)
    {
        int x, y;	cin >> x >> y;
        add(x, y);	add(y, x);//无向图，一条边存两次
    }
    for(int i = 1; i <= n; i++)
    {
        if(!color[i])//这个点未染色
        {
            if(!dfs(i, 1))
            {
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes";
    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
46
47
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int to[N], ne[N], head[N], idx;
int n1, n2 ,m;
int st[N], match[N];
void add(int x, int y)
{
    to[idx] = y, ne[idx] = head[x], head[x] = idx++;
}
bool find(int x)
{
    for(int i = head[x]; i != -1; i = ne[i])
    {
        int j = to[i];
        if(!st[j])
        {
            st[j] = 1;
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n1 >> n2 >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);//因为只从一边向另一边匹配，所以只用存一边
    }
    int res = 0;
    for(int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof st);
        if(find(i)) res++;
    }
    cout << res;
    return 0;
}