图论 List

题目

#A 小 K 的农场 (Unaccepted)
    #B 信息传递 (Unaccepted)
    #C 最短路计数 (Accepted)
    #D 通往奥格瑞玛的道路 (Accepted)

#E 公路修建 (Unaccepted)

#F 货车运输 (Unaccepted)

#G 图的m着色问题 (Unaccepted)

1. DFS & BFS

// 八皇后

// Au: GG

#include <cstdio>

#include <cmath>

using namespace std;

int v[15], n, ans = 0;

bool f[15];

void dfs(int i) {

    if (i > n) {

        ans++;

        if (ans <= 3) {

            for (int j = 1; j <= n; j++) {

                printf("%d ", v[j]);

            }

            printf("\n");

        }

        return;

    }

    for (int k = 1; k <= n; k++) {

        if (f[k]) continue;

        bool pd = true;

        for (int j = 1; j < i; j++)

            if (v[j] == k || abs(i - j) == abs(v[j] - k)) pd = false;

        if (pd) {

            v[i] = k;

            f[k] = true;

            dfs(i + 1);

            f[k] = false;

            v[i] = 0;

        }

    }

}

int main() {

    scanf("%d", &n);

    dfs(1);

    printf("%d", ans);

    return 0;

}

// 马的遍历

// Au: GG

#include <iostream>

#include <algorithm>

#include <queue>

#include <cmath>

#include <cstring>

#include <cstdio>

#include <cstdlib>

using namespace std;

int n, m;

int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2};

int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int map[400 + 3][400 + 3];

struct bbc {

    int x, y, n;

} s;

queue<bbc> q;

int main() {

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

    scanf("%d%d%d%d", &n, &m, &s.x, &s.y);

    map[s.x][s.y] = 0;

    q.push(s);

    while (!q.empty()) {

        bbc a;

        for (int i = 0; i < 8; i++) {

            a = q.front();

            int bx = a.x + dx[i];

            int by = a.y + dy[i];

            if (bx < 1 || bx > n || by < 1 || by > m || map[bx][by] != -1)

                continue;

            a.x = bx;

            a.y = by;

            a.n++;

            q.push(a);

            map[bx][by] = a.n;

        }

        q.pop();

    }

    for (int k = 1; k <= n; k++) {

        for (int r = 1; r <= m; r++)

            printf("%-5d", map[k][r]);

        printf("\n");

    }

    return 0;

}

/* Luogu P1126 机器人搬重物

 * Au: GG

 */

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 53;

int n, m, g[N][N], endx, endy;

bool d[N][N][4];

struct status {

    int x, y, t;

    char d;

} sta;

queue<status> q;

char ltd(char dir) {

    if (dir == 'N') return 'W';

    else if (dir == 'W') return 'S';

    else if (dir == 'S') return 'E';

    else return dir = 'N';

}

char rtd(char dir) {

    if (dir == 'N') return 'E';

    else if (dir == 'E') return 'S';

    else if (dir == 'S') return 'W';

    else return 'N';

}

int did(char dir) {

    if (dir == 'N') return 0;

    else if (dir == 'E') return 1;

    else if (dir == 'S') return 2;

    else return 3;

}

int main() {

    int h;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++) {

            scanf("%d", &h);

            if (h) {

                g[i][j] = -1;

                g[i + 1][j] = -1;

                g[i][j + 1] = -1;

                g[i + 1][j + 1] = -1;

            }

        }

    scanf("%d%d%d%d %c", &sta.x, &sta.y, &endx, &endy, &sta.d);

    sta.x++; sta.y++; endx++; endy++;

    sta.t = 0; d[sta.x][sta.y][did(sta.d)] = true;

    q.push(sta);

    while (!q.empty()) {

        status a = q.front(), b;

        q.pop();

        if (a.x == endx && a.y == endy) {

            printf("%d\n", a.t); return 0;

        }

        d[a.x][a.y][did(a.d)] = true;

        // printf("Status a(%d, %d, %c) = %d\n", a.x, a.y, a.d, a.t);

        // Creep & Walk & Run

        for (int step = 1; step <= 3; step++) {

            if (a.d == 'N') {

                b.x = a.x - step; b.y = a.y;

            } else if (a.d == 'S') {

                b.x = a.x + step; b.y = a.y;

            } else if (a.d == 'W') {

                b.x = a.x; b.y = a.y - step;

            } else {

                b.x = a.x; b.y = a.y + step;

            }

            b.d = a.d; b.t = a.t + 1;

            if (g[b.x][b.y] == 0 && !d[b.x][b.y][did(b.d)]) {

                if (b.x > 1 && b.x < n + 1 && b.y > 1 && b.y < m + 1)

                    q.push(b);

                else break;

            } else break;

        }

        // Left

        b.x = a.x; b.y = a.y; b.t = a.t + 1;

        b.d = ltd(a.d);

        if (!d[b.x][b.y][did(b.d)])

            if (b.x > 1 && b.x < n + 1 && b.y > 1 && b.y < m + 1)

                q.push(b);

        // Right

        b.x = a.x; b.y = a.y; b.t = a.t + 1;

        b.d = rtd(a.d);

        if (!d[b.x][b.y][did(b.d)])

            if (b.x > 1 && b.x < n + 1 && b.y > 1 && b.y < m + 1)

                q.push(b);

    }

    printf("-1\n");

    return 0;

}

/*

9 10

0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0 0 0

0 0 0 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 1 0

7 2 2 7 S

*/

/*

问题（估计是致命问题）给你一个图（点阵，不是块阵）

0 0 0 0 0 0 0

0 S 1 T 1 0 0

机器人在S处面向右方，根据你82-97行的前进代码，机器人可以到达T处，但是事实上并不能到达，所以题目数据的图（点阵）如下

 0 0 0 0 0 0-1-1 0 0 0

 0 0 0 0 0 0-1-1-1-1 0

 0 0 V-1-1 V 0 T-1-1 0

 0 0-1-1-1 0 0 0 0 0 0

 0 0-1-1 0 0-1-1 0 0 0

 0 0 V 0 0-1-1-1 0 0 0

 0 0 0-1-1-1-1 0 0 0 0

 0 0 S-1-1-1 0 0 0 0 0

-1-1 0 0 0 0 0 0-1-1 0

-1-1 0 0 0 0 0 0-1-1 0

7步的行径路径给你了

左转（面向右边）

左转（面向上方）

walk

run（这步其实不能走，但是按照你的代码是可以走的）

右转（面向右边）

run（这步其实也不能走，但是按照你的代码也是可以走的）

walk

以上七步S是起点V是途经点T是终点

连这个错误你都犯，你可以去面壁一天了。。。（什么时候可以穿墙了。。。）

还有，让zzh去面壁半天，连这么简单的错误都看不出来。

我先走了

——8：45 by dph

*/

/* P1118 [USACO06FEB]数字三角形Backward Digit Su…

 * Au: GG

 */

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 15;

int n, sum, tri[N][N], d[N];

bool v[N];

void triangle() { // triangle table

    for (int i = 1; i <= n; i++) tri[i][1] = tri[i][i] = 1;

    for (int i = 2; i <= n; i++)

        for (int j = 2; j < i; j++)

            tri[i][j] = tri[i - 1][j] + tri[i - 1][j - 1];

    // for (int i = 1; i <= n; i++) {

    //     for (int j = 1; j <= i; j++)

    //         printf("%d ", tri[i][j]);

    //     printf("\n");

    // }

}

bool dfs(int f, int s) {

    // printf("dfs(%d, %d, d = %d)\n", f, s, d[f - 1]);

    if (f > n) {

        if (s == sum) return true;

        else return false;

    }

    for (int i = 1; i <= n; i++)

        if (!v[i] && s + i * tri[n][f] <= sum) {

            v[i] = true; d[f] = i;

            if (dfs(f + 1, s + i * tri[n][f])) return true;

            v[i] = false;

        }

    return false;

}

int main() {

    scanf("%d%d", &n, &sum);

    triangle();

    if (dfs(1, 0)) {

        for (int i = 1; i <= n; i++) printf("%d ", d[i]);

    }

    return 0;

}

/* Luogu P1141 01迷宫

 * Au: GG

 */

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 1000 + 5;

int n, m, g[N][N]; int vis[N][N], vs, vcnt[100000 + 5];

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

struct point {

    int x, y;

};

int read() {

    char a = getchar();

    while (a != '0' && a != '1') a = getchar();

    return a - '0';

}

bool check(point i) {

    if (i.x < 1 || i.x > n) return false;

    if (i.y < 1 || i.y > n) return false;

    return true;

}

int bfs(int u, int v) {

    if (vis[u][v]) return vcnt[vis[u][v]]; 

    int cnt = 0; vs++;

    queue<point> q;

    point a, b; a.x = u, a.y = v;

    q.push(a);

    while (!q.empty()) {

        a = q.front();

        q.pop(); if (vis[a.x][a.y]) continue;

        vis[a.x][a.y] = vs; cnt++;

        for (int i = 0; i < 4; i++) {

            b.x = a.x + dx[i];

            b.y = a.y + dy[i];

            if (check(b) && (g[b.x][b.y] != g[a.x][a.y]) && !vis[b.x][b.y]) q.push(b);

        }

    }

    return vcnt[vs] = cnt;

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            g[i][j] = read();

        }

    }

    int xx, yy;

    while (m--) {

        scanf("%d%d", &xx, &yy);

        printf("%d\n", bfs(xx, yy));

    }

    return 0;

}

2. 最小生成树

// 最小生成树

// Au: GG

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <queue>

#include <algorithm>

using namespace std;

int n, m, f[5000 + 3], sum;

struct edge {

    int x, y, w;

    bool operator < (const edge &a) const {

        return w > a.w;

    }

} temp;

priority_queue<edge> G;

int find(int x) {

    return (f[x] == x) ? x : f[x] = find(f[x]);

}

void join(int x, int y) {

    f[find(y)] = find(x);

}

int main() {

    int x, y, z, flag = 0;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {

        scanf("%d%d%d", &x, &y, &z);

        temp.x = x; temp.y = y; temp.w = z; G.push(temp);

    }

    for (int i = 1; i <= n; i++) f[i] = i;

    while (!G.empty()) {

        temp = G.top(); G.pop();

        if (find(temp.x) != find(temp.y)) join(temp.x, temp.y), sum += temp.w, flag++;

    }

    if (flag < n - 1) printf("orz\n");

    else printf("%d\n", sum);

    return 0;

}

3. 并查集

/* 并查集

 * Au: GG

 */

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn = 10000 + 3;

int n, m, z, x, y, f[maxn];

int find(int x) {

    return (f[x] == x) ? x : f[x] = find(f[x]);

}

inline void join(int x, int y) {

    f[find(y)] = find(x);

}

int main() {

    scanf("%d%d", &n, &m);

    while (n--) f[n] = n;

    while (m--) {

        scanf("%d%d%d", &z, &x, &y);

        if (z == 1) {

            join(x, y);

        } else {

            if (find(x) == find(y)) printf("Y\n");

            else printf("N\n");

        }

    }

    return 0;

}

巴特西

图论 List

最新文章

热门文章