AcWing 第3讲 搜索与图论

排列数字

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100010;
int n;
int num[10];
bool flag[10];

void bfs(int de) {
    if (de == n) {
        for (int i = 0;i < n;i++) cout << num[i];
        cout << '\n';
    }

    for (int i = 1;i <= n;i++) {
        if (flag[i]) continue;
        flag[i] = true;
        num[de] = i;
        bfs(de + 1);
        flag[i] = false;
    }
}

int main() {
    cin >> n;
    bfs(0);


    return 0;
}

八皇后问题

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 110;
int n, row[N], jia[N], jian[N];
char mape[N][N];

void bfs(int de) {
    if (de == n) {
        for (int i = 0;i < n;i++) {
            puts(mape[i]);
        }
        puts("");
    }

    for (int i = 0;i < n;i++) {
        if (mape[de][i] == '.' && !row[i] && !jia[de + i] && !jian[de - i + n / 2]) {
            mape[de][i] = 'Q';
            row[i] = 1;
            jia[de + i] = 1;
            jian[de - i + n / 2] = 1;
            bfs(de + 1);
            mape[de][i] = '.';
            row[i] = 0;
            jia[de + i] = 0;
            jian[de - i + n / 2] = 0;
        }
    }
}


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

    bfs(0);



    return 0;
}

迷宫最短路

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 110;

int n, m, maze[N][N], d[N][N];
int dx[] = { 0, 0,0,1,-1 }, dy[] = { 0, -1,1,0,0 };
typedef pair<int, int> pii;


int bfs() {
    queue<pii> qu;

    qu.push({ 1,1 });
    d[1][1] = 1;

    while (!qu.empty()) {
        pii t = qu.front();
        int x = t.first, y = t.second;
        qu.pop();

        for (int i = 1;i <= 4;i++) {
            int xi = x + dx[i], yi = y + dy[i];
            if (xi<1 || xi>n || yi<1 || yi>m || d[xi][yi] || maze[xi][yi])
                continue;
            // cout<< x<<" "<<y<<" " <<xi<<" "<<yi<<endl;
            d[xi][yi] = d[x][y] + 1;
            qu.push({ xi, yi });
        }
    }

    return d[n][m] - 1;
}

int main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            cin >> maze[i][j];

    cout << bfs();

    return 0;
}

八数码问题

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 110;

int dx[] = { 0,0,1,-1 }, dy[] = { -1,1,0,0 };



int bfs(string str) {
    queue<string> qu;
    unordered_map<string, int> d;

    qu.push(str);
    d[str] = 1;

    while (qu.size()) {
        // cout << "---------";
        string t = qu.front();
        qu.pop();

        if (t == "12345678x")
            return d[t] - 1;
        int cou = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0;i < 4;i++) {
            int xi = x + dx[i], yi = y + dy[i];
            if (!(xi < 0 || xi>2 || yi < 0 || yi>2)) {
                swap(t[3 * xi + yi], t[k]);
                if (!d.count(t)) {
                    qu.push(t);
                    d[t] = cou + 1;
                    // cout << t<<" "<< d.count(t) << endl;
                }
                swap(t[3 * xi + yi], t[k]);
            }
        }
    }
    return -1;
}


int main() {
    string str = "";
    char ch[2];
    for (int i = 1;i <= 9;i++) {
        cin >> ch;
        str += *ch;
    }

    cout << bfs(str);

    return 0;

}

树的重心

#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
typedef long long LL;

const int N = 1000020;
int n[N], ne[N], h[N];
int idx, number, ans = 0x6f6f6f6f;
bool vis[N];

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

int dfs(int x) {
    vis[x] = true;
    int num = 0;
    int maxx = 0;
    int sum = 0;
    for (int d = h[x];d!=-1;d = ne[d]) {
        if(vis[n[d]]) continue;
        num = dfs(n[d]);
        maxx = max(maxx, num);
        sum += num;
    }
    int these = max(maxx, number - sum - 1);
    ans = min( ans, these);
    return sum + 1;
}

int main() {
    memset(h, -1, sizeof h);


    int  a, b;
    cin >> number;
    for (int i = 0;i < number-1;i++) {
        cin >> a >> b;
        insert(a, b);
        insert(b, a);
    }

    dfs(1);
    cout << ans;
    return 0;
}

图中点的层次

#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
typedef long long LL;

const int N = 1000020;
int n[N], ne[N], h[N];
int idx, number;
int m, num;
bool vis[N];

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

int bfs(int x) {
    vis[x] = true;
    queue<int> qu;
    qu.push(x);
    int ans[N];
    while (qu.size()) {
        int x = qu.front(); qu.pop();
        int dep = ans[x];
        if (x == num) return ans[num];

        for (int d = h[x]; ~d;d = ne[d]) {
            int v = n[d];

            if (vis[v]) continue;
            vis[v] = true;
            ans[v] = dep + 1;
            qu.push(v);
        }
    }
    return  -1;
}

int main() {
    cin >> num >> m;
    memset(h, -1, sizeof h);


    int  a, b;
    for (int i = 0;i < m;i++) {
        cin >> a >> b;
        insert(a, b);
        // insert(b, a);
    }

    cout << bfs(1);
    return 0;
}

有向图的拓扑序列

// 拓扑排序
// if条件错误
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 10;
int n, m, idx;
int h[N], e[N], ne[N];
int du[N];
int vis[N];

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

int qu[N], hh = 0, tt = -1;
bool check() {
    for (int i = 1;i <= n;i++) {
        if (!du[i]) {
            qu[++tt] = i;
        }
    }

    while (hh <= tt) {
        int head = qu[hh++];
        vis[head] = true;
        for (int i = h[head]; ~i;i = ne[i]) {
            int value= e[i];
            if (vis[value]) continue;
            if (--du[value]) continue;
                qu[++tt] = value;            
        }
    }
    return tt == n - 1;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    int a, b;
    for (int i = 0;i < m;i++) {
        cin >> a >> b;
        insert(a, b);
        du[b]++;
    }
    if (!check()) {
        cout << "-1";
        return 0;
    }
    for (int i = 0; i < n;i++) {
        cout << qu[i] << " ";
    }

    return 0;
}

Dijkstra最短路-朴素

// #include <bits/stdc++.h>
// 二维数组开太大了
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;

const int N = 1010;
int n, m;
int g[N][N], dis[N];
bool vis[N];

int dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;

    for (int i = 1;i < n;i++) {
        int t = -1;
        for (int j = 1;j <= n;j++) {
            if (!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        }

        vis[t] = true;

        for (int j = 1;j <= n;j++) {
            if (!vis[j])
                dis[j] = min(dis[j], dis[t] + g[t][j]);
        }
    }
    if (dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];
}

int main() {
    memset(g, 0x3f, sizeof(g));

    cin >> n >> m;
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra();


    return 0;
}

Dijkstra堆优化

#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;

const int N = 1000010;
int h[N], e[N], ne[N], w[N];
int idx, n, m;
int d[N];
bool vis[N];
typedef pair<int, int> PII;


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

int dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> qu;
    qu.push({ 0,1 });
    memset(d, 0x3f, sizeof d); 	d[1] = 0;

    while (qu.size()) {
        auto t = qu.top(); qu.pop();
        int dis = t.first, ver = t.second;
        if (vis[ver]) continue;
        vis[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i]) {
            int vv = e[i];
            if (d[vv] > d[ver] + w[i]) {
                d[vv] = d[ver] + w[i];
                qu.push({ d[vv], vv });
            }
        }
    }
    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

int main() {
    cin >> n >> m;
    int a, b, c;

    memset(h, -1, sizeof(h));


    while (m--) {
        cin >> a >> b >> c;
        insert(a, b, c);
    }

    cout << dijkstra();
    return 0;
}

Bellman-ford最短路

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef struct {
    int a, b, c;
} stru;

const int N = 110000;
int n, m, k;
int dis[N], back[N];
stru edge[N];

void bellman_fold() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;

    for (int i = 0;i < k;i++) {
        memcpy(back, dis, sizeof(back));
        for (int j = 0;j < m;j++) {
            dis[edge[j].b] = min( dis[edge[j].b] , back[edge[j].a]  + edge[j].c);
        }
    }
}


int main() {
    cin >> n >> m >> k;
    int a, b, c;
    for (int i = 0;i < m;i++) {
        cin >> a >> b >> c;
        edge[i] = { a,b,c };
    }
    
    bellman_fold();

    if (dis[n] >= 0x3f3f3f3f/2) cout << "impossible";
    else cout << dis[n];

    return 0;
}

SPFA求最短路

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 1e6;

int h[N], e[N], ne[N], w[N], idx;
int n, m;
int dis[N];
bool vis[N];


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

void spfa() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;

    queue<int> qu;

    qu.push(1);

    while (qu.size()) {
        int head = qu.front();
        qu.pop();
        // 可能会有重边，没个点只入队一次即可
        // vis用来标注head是否在队列中
        vis[head] = false;

        for (int i = h[head]; ~i;i = ne[i]) {
            int ver = e[i];
            if (dis[ver] > dis[head] + w[i]) {
                dis[ver] = dis[head] + w[i];
                if (!vis[ver]) {
                    qu.push(ver);
                    vis[ver] = true;
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    int a, b, c;
    for (int i = 0;i < m;i++) {
        // cin >> a >> b >> c;
        scanf("%d%d%d", &a, &b, &c);
        insert(a, b, c);
    }

    spfa();


    if (dis[n] > 0x3f3f3f3f / 2) cout << "impossible";
    else cout << dis[n];

    return 0;
}

SPFA判断负环

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 1e6;

int h[N], e[N], ne[N], w[N], idx;
int n, m;
int dis[N];
bool vis[N];
int cnt[N];

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

bool spfa() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;

    queue<int> qu;

    for (int i = 1;i <= n;i++) {
        qu.push(i);
        cnt[i]++;
    }

    while (qu.size()) {
        int head = qu.front();
        qu.pop();
        vis[head] = false;

        for (int i = h[head]; ~i;i = ne[i]) {
            int ver = e[i];
            if (dis[ver] > dis[head] + w[i]) {
                dis[ver] = dis[head] + w[i];
                if (!vis[ver]) {
                    qu.push(ver);
                    vis[ver] = true;
                    cnt[ver]++;
                    if (cnt[ver] > n) return true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    int a, b, c;
    for (int i = 0;i < m;i++) {
        // cin >> a >> b >> c;
        scanf("%d%d%d", &a, &b, &c);
        insert(a, b, c);
    }

    if (spfa()) cout << "Yes";
    else cout << "No";

    return 0;
}

Floyd 求最短路

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;
int n, m, k;
int g[500][500];

void floyd() {
    for (int k = 1;k <= n;k++)
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

int main() {
    cin >> n >> m >> k;

    memset(g, 0x3f3f3f3f, sizeof(g));
    for (int i = 0;i < 500;i++)
        g[i][i] = 0;


    int a, b, c;
    for (int i = 1;i <= m;i++) {
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    floyd();

    
    while (k--) {
        cin >> a >> b;
        if (g[a][b] >= 0x3f3f3f3f / 2) cout << "impossible\n";
        else cout << g[a][b] << '\n';
    }

    
    return 0;
}

Prim 最小生成树

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;
int n, m;
int g[600][600], dist[1000];
bool st[600];
int ans;

bool prim() {
    memset(dist, 0x3f, sizeof(dist));
    for (int i = 0;i < n;i++) {
        int t = -1;
        for (int j = 0;j < n;j++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

        if (dist[t] == 0x3f3f3f3f) return false;
        if(i) ans+=dist[t];
        st[t] = true;
        
        for (int j = 1;j <= n;j++) {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f3f3f3f, sizeof(g));

    
    int a, b, c;
    for (int i = 0;i < m;i++) {
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    if (prim())
        cout << "impossible";
    else
        cout << ans;

    return 0;
}

Kruskal 最小生成树

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e6;

// int e[N], ne[N], w[N], idx, h[N];
struct Edge {
    int a, b, w;
}edge[N];
int n, m, p[N], ans;

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int find(int a) {
    if (p[a] != a) p[a] = find(p[a]); // 路径压缩
    return p[a];
}

bool kruskal() {
    sort(edge, edge + m, cmp);

    for (int i = 0;i < N;i++) p[i] = i;
    int cnt = 0;
    for (int i = 0;i < m;i++) {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int pa = find(a), pb = find(b);

        if (pa != pb) {
            cnt++;
            p[pa] = pb;
            ans += w;
        }

        if (cnt == n - 1) return true;
    }
    return false;
}


int main() {
    cin >> n >> m;
    int a, b, c;
    memset(edge, 0x3f, sizeof(edge));

    for (int i = 0;i < m;i++) {
        scanf("%d%d%d", &a, &b, &c);
        // cin >> a >> b >> c;
        edge[i] = { a,b,c };
    }
    // if(n==100000) cout<<edge[m-5].w;

    if (!kruskal()) cout << "impossible";
    else cout << ans;

    return 0;
}

染色法判断二分图

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;


const int N = 1e6;
int e[N], ne[N], h[N], idx;
int color[N];
int n, m;

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

bool dfs(int x, int colo) {
    color[x] = colo;

    for (int i = h[x];~i;i = ne[i]) {
        int a = e[i];
        if (!color[a]) {
            if (dfs(a, 3 - colo))
                return true;
        }
        else if (color[a] == colo) {
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof(h));

    int a, b;
    for (int i = 0;i < m;i++) {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

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

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

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;


const int N = 1e6;
int e[N], ne[N], h[N], idx;
int n1, n2, m;
bool st[N];
int match[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;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() {
    cin >> n1 >> n2 >> m;
    int a, b;
    memset(h, -1, sizeof(h));
    while (m--) {
        cin >> a >> b;
        add(a, b);
    }

    int ans = 0;
    for (int i = 1; i <= n1; i++) {
        memset(st, false, sizeof(st));
        if (find(i)) ans++;
    }
    
    cout<<ans;


    return 0;
}