题目

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

#E 公路修建 (Unaccepted)

#F 货车运输 (Unaccepted)

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

---

1. DFS & BFS

// 八皇后
// Au: GG

#include
#include
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
#include
#include
#include
#include
#include
#include
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 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
#include
#include
#include
#include
#include
#include
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 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
#include
#include
#include
#include
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
#include
#include
#include
#include
#include
#include
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
#include
#include
#include
#include
#include
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 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
#include
#include
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;
}