題目描述:
?有N個比賽隊（1<=N<=500），編號依次為1屯远，2慨丐，3备闲，恬砂。泻骤。。亲轨。器虾，N進行比賽兆沙，比賽結(jié)束后葛圃，裁判委員會要將所有參賽隊伍從前往后依次排名，但現(xiàn)在裁判委員會不能直接獲得每個隊的比賽成績尚氛，只知道每場比賽的結(jié)果阅嘶，即P1贏P2抡蛙，用P1粗截，P2表示，排名時P1在P2之前∈幔現(xiàn)在請你編程序確定排名昂利。
輸入描述:
?輸入有若干組，每組中的第一行為二個數(shù)N（1<=N<=500）窝撵，M；其中N表示隊伍的個數(shù)襟铭，M表示接著有M行的輸入數(shù)據(jù)碌奉。接下來的M行數(shù)據(jù)中，每行也有兩個整數(shù)P1寒砖，P2表示即P1隊贏了P2隊赐劣。
輸出描述:
?給出一個符合要求的排名。輸出時隊伍號之間有空格哩都，最后一名后面沒有空格魁兼。
其他說明：
?符合條件的排名可能不是唯一的，此時要求輸出時編號小的隊伍在前漠嵌；輸入數(shù)據(jù)保證是正確的，即輸入數(shù)據(jù)確保一定能有一個符合要求的排名蟹瘾。
示例輸入:
4 3
1 2
2 3
4 3
輸出:
1 2 4 3

// 不斷尋找入度為0的頂點。
#include<iostream>
using namespace std;
const int VNUM = 501;
int cost[VNUM][VNUM];
int in[VNUM];
int ans[VNUM];
void topo(int n){
    int index = 1;
    for (int k = 0; k < n; k++){
        for (int i = 1; i <= n; i++){
            if (in[i] == 0){
                ans[index] = i;
                for (int j = 1; j <= n; j++){
                    if (cost[i][j] == 1){
                        in[j]--;
                    }
                }
                in[i] = -1;
                index++;
                break;
            }
        }
    }
    for (int i = 1; i < n; i++){
        cout << ans[i] << " ";
    }
    cout <<ans[n]<< endl;
}
int main(){
    int n, m;
    while (cin >> n >> m){
        int a, b;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                cost[i][j] = 0;
            }
            in[i] = 0;
        }
        for (int i = 0; i < m; i++){
            cin >> a >> b;
            // 防止重邊
            if (cost[a][b] == 0)
                in[b]++;
            cost[a][b] = 1;
        }
        topo(n);
    }
    return 0;
}

五、廣度優(yōu)先搜索和深度優(yōu)先搜索

問題描述：（勝利大逃亡）
?Ignatius被魔王抓走了,有一天魔王出差去了,這可是Ignatius逃亡的好機會.
?魔王住在一個城堡里,城堡是一個ABC的立方體,可以被表示成A個B*C的矩陣,剛開始Ignatius被關(guān)在(0,0,0)的位置,離開城堡的門在(A-1,B-1,C-1)的位置,現(xiàn)在知道魔王將在T分鐘后回到城堡,Ignatius每分鐘能從一個坐標(biāo)走到相鄰的六個坐標(biāo)中的其中一個.現(xiàn)在給你城堡的地圖,請你計算出Ignatius能否在魔王回來前離開城堡(只要走到出口就算離開城堡,如果走到出口的時候魔王剛好回來也算逃亡成功),如果可以請輸出需要多少分鐘才能離開,如果不能則輸出-1.

輸入：
?輸入數(shù)據(jù)的第一行是一個正整數(shù)K,表明測試數(shù)據(jù)的數(shù)量.每組測試數(shù)據(jù)的第一行是四個正整數(shù)A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它們分別代表城堡的大小和魔王回來的時間.然后是A塊輸入數(shù)據(jù)(先是第0塊,然后是第1塊,第2塊......),每塊輸入數(shù)據(jù)有B行,每行有C個正整數(shù),代表迷宮的布局,其中0代表路,1代表墻.(如果對輸入描述不清楚,可以參考Sample Input中的迷宮描述,它表示的就是上圖中的迷宮)
特別注意:本題的測試數(shù)據(jù)非常大,請使用scanf輸入,我不能保證使用cin能不超時.在本OJ上請使用Visual C++提交.

輸出:
?對于每組測試數(shù)據(jù),如果Ignatius能夠在魔王回來前離開城堡,那么請輸出他最少需要多少分鐘,否則輸出-1.

Sample Input

1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0

Sample Output
11

解題思路：DFS芦圾，每次向六個方向擴展，時間加1，采用queue數(shù)據(jù)結(jié)構(gòu)，第一次遍歷到出口 時即最短時間弃酌。
問題：第一段是網(wǎng)上答案乌询，第二段是我的代碼鬼佣。我的代碼一直出現(xiàn)內(nèi)存超限税迷，暫未找到原因。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
bool mark[50][50][50];
bool m[50][50][50];
int t;
int go[][3] =
{
    1, 0, 0,
    -1, 0, 0,
    0, 1, 0,
    0, -1, 0,
    0, 0, 1,
    0, 0, -1
};
struct e
{
    int x, y, z;
    int t;
};
queue <e> q;
int bfs(int a, int b, int c)
{
    while (!q.empty())
    {
        e now;
        now = q.front();
        q.pop();
        if (now.t >= t) {
            return  -1;
        }
        for (int i = 0; i<6; i++)
        {
            int nx = now.x + go[i][0];
            int ny = now.y + go[i][1];
            int nz = now.z + go[i][2];
            if (nx<0 || nx >= a || ny<0 || ny >= b || nz<0 || nz >= c) continue;
            if (mark[nx][ny][nz] == 1) continue;
            if (m[nx][ny][nz] == 1) continue;
            m[nx][ny][nz] = 1;
            e tmp;
            tmp.x = nx;
            tmp.y = ny;
            tmp.z = nz;
            tmp.t = now.t + 1;
            if (tmp.t <t) {
                q.push(tmp);
            }
            mark[nx][ny][nz] == 1;
            if (nx == a - 1 && ny == b - 1 && nz == c - 1)
                return tmp.t;
        }
    }
    return -1;
}
int main()
{
    int a, b, c;
    int k;
    while (scanf_s("%d", &k) != eof)
    {
        while (k--)
        {
            scanf_s("%d%d%d%d", &a, &b, &c, &t);
            for (int i = 0; i<a; i++)
            {
                for (int j = 0; j<b; j++)
                {
                    for (int k = 0; k<c; k++)
                    {
                        scanf_s("%d", &m[i][j][k]);
                        mark[i][j][k] = 0;
                    }
                }
            }
            while (!q.empty()) q.pop();
            e tmp;
            tmp.x = tmp.y = tmp.z = tmp.t = 0;
            q.push(tmp);
            mark[0][0][0] = 1;
            int rec = bfs(a, b, c);
            if (rec <= t && rec != -1) printf("%d\n", rec);
            else printf("-1\n");
        }
    }
    return 0;
}

#include<iostream>
#include<queue>
using namespace std;
const int MAX = 50;
int map[MAX][MAX][MAX];
bool mark[MAX][MAX][MAX];
int A, B, C, T;
struct Dot{
    int a;
    int b;
    int c;
    int t;
};
queue<Dot> Q;
void BFS(){
    while (Q.empty() == false){
        Dot dot = Q.front();
        int a = dot.a;
        int b = dot.b;
        int c = dot.c;
        int t = dot.t;
        if (a == A - 1 && b == B - 1 && c == C - 1 && !mark[a][b][c]){
            mark[a][b][c] = true;
            if (t <= T)
                cout << t << endl;
            else
                cout << -1 << endl;
            return;
        }
        if (t > T){
            cout << -1 << endl;
            return;
        }
        mark[a][b][c] = true;
        Dot temp;
        if (a > 0 && !mark[a - 1][b][c] && map[a - 1][b][c] == 0){
            temp.t = t + 1;
            temp.a = a - 1;
            temp.b = b;
            temp.c = c;
            Q.push(temp);
        }
        if (a<A-1&&!mark[a + 1][b][c] && map[a + 1][b][c] == 0){
            temp.t = t + 1;
            temp.a = a + 1;
            temp.b = b;
            temp.c = c;
            Q.push(temp);
        }
        if (b > 0 && !mark[a][b - 1][c] && map[a][b - 1][c] == 0){
            temp.t = t + 1;
            temp.a = a;
            temp.b = b-1;
            temp.c = c;
            Q.push(temp);
        }
        if (b<B-1&&map[a][b + 1][c] == 0 && !mark[a][b + 1][c]){
            temp.t = t + 1;
            temp.a = a ;
            temp.b = b+1;
            temp.c = c;
            Q.push(temp);
        }
        if (c > 0 && !mark[a][b][c - 1] && map[a][b][c - 1] == 0){
            temp.t = t + 1;
            temp.a = a;
            temp.b = b;
            temp.c = c-1;
            Q.push(temp);
        }
        if (c<C-1&&map[a][b][c + 1] == 0 && !mark[a][b][c + 1]){
            temp.t = t + 1;
            temp.a = a;
            temp.b = b;
            temp.c = c + 1;
            Q.push(temp);
        }
        Q.pop();
    }
}
int main(){
    int n;
    while (scanf_s("%d", &n) != EOF){
        scanf_s("%d%d%d%d", &A, &B, &C, &T);
        for (int i = 0; i < A; i++)
        {
            for (int j = 0; j < B; j++)
            {
                for (int k = 0; k < C; k++)
                {
                    map[i][j][k] = 0;
                    // cin >> map[i][j][k];
                    scanf_s("%d", &map[i][j][k]);
                    mark[i][j][k] = 0;
                }
            }
        }
        while (!Q.empty()){
            Q.pop();
        }
        Dot d;
        d.a = 0;
        d.b = 0;
        d.c = 0;
        d.t = 0;
        map[0][0][0] = 0;
        Q.push(d);
        BFS();
        if (!mark[A - 1][B - 1][C - 1])
            cout << -1 << endl;
    }
    return 0;
}

Problem Description(非吃钐澹可樂）
?大家一定覺的運動以后喝可樂是一件很愜意的事情，但是seeyou卻不這么認(rèn)為。因為每次當(dāng)seeyou買了可樂以后疲吸，阿牛就要求和seeyou一起分享這一瓶可樂，而且一定要喝的和seeyou一樣多孵运。但seeyou的手中只有兩個杯子，它們的容量分別是N 毫升和M 毫升 可樂的體積為S （S<101）毫升　(正好裝滿一瓶) 咐熙，它們?nèi)齻€之間可以相互倒可樂 (都是沒有刻度的去团，且 S==N+M鞋吉，101＞S＞0，N＞0改抡，M＞0) 欠拾。聰明的ACMER你們說他們能平分嗎荆忍？如果能請輸出倒可樂的最少的次數(shù)，如果不能輸出"NO"岳守。

Input
?三個整數(shù) : S 可樂的體積 , N 和 M是兩個杯子的容量佣赖，以"0 0 0"結(jié)束。

Output
?如果能平分的話請輸出最少要倒的次數(shù)记盒，否則輸出"NO"憎蛤。

Sample Input
7 4 3
4 1 3
0 0 0

Sample Output
NO
3

#include<iostream>
#include<queue>
using namespace std;
struct Liquid{
    int n;
    int m;
    int s;
    int times;
};
bool mark[101][101][101];
queue<Liquid> Q;
int N, M, S;
void AtoB(int &a, int &b, int max){
    if (a + b > max){
        a = a + b - max;
        b = max;
    }
    else{
        b = a + b;
        a = 0;
    }
}
void push_back(int n, int m, int s, int t){
    if (n > N || m > M || s > S){
        return;
    }
    Liquid next ;
    if (mark[n][m][s] == false){
        next.n = n;
        next.m = m;
        next.s = s;
        next.times = t + 1;
        Q.push(next);
    }
}
int main(){
    while (true){
        cin >> S >> N >> M;
        bool flag = false;
        if (S == 0 && N == 0 && M == 0){
            return 0;
        }
        if (S % 2 != 0){
            cout << "NO" << endl;
            continue;
        }
        for (int i = 0; i <= N; i++){
            for (int j = 0; j <= M; j++){
                for (int k = 0; k <= S; k++)
                    mark[i][j][k] = 0;
            }
        }
        while (!Q.empty()){
            Q.pop();
        }
        Liquid temp;
        temp.n = 0;
        temp.m = 0;
        temp.s = S;
        temp.times = 0;
        Q.push(temp);
        while (Q.empty() == false){
            Liquid now = Q.front();
            Liquid next;
            Q.pop();
            int n, m, s, t;
            n = now.n;
            m = now.m;
            s = now.s;
            t = now.times;

            mark[n][m][s] = true;
            if ((n == S / 2 && m == S / 2) || (n == S / 2 && s == S / 2) || (m == S / 2 && s == S / 2)){
                cout << t << endl;
                flag = true;
                break;
            }
            AtoB(n, m, M);
            push_back(n, m, s, t);


            n = now.n;
            m = now.m;
            s = now.s;
            t = now.times;
            AtoB(n, s, S);
            push_back(n, m, s, t);


            n = now.n;
            m = now.m;
            s = now.s;
            t = now.times;
            AtoB(m, n, N);
            push_back(n, m, s, t);


            n = now.n;
            m = now.m;
            s = now.s;
            t = now.times;
            AtoB(m, s, S);
            push_back(n, m, s, t);


            n = now.n;
            m = now.m;
            s = now.s;
            t = now.times;
            AtoB(s, m, M);
            push_back(n, m, s, t);


            n = now.n;
            m = now.m;
            s = now.s;
            t = now.times;
            AtoB(s, n, N);
            push_back(n, m, s, t);


        }
        if (flag)
            continue;
        cout << "NO" << endl;
    }
    return 0;
}

此類題目應(yīng)先確認(rèn)狀態(tài)的轉(zhuǎn)移關(guān)系。
(x,y,z...) ---> (xx,yy,zz...).。
其次找清判斷結(jié)果的條件俩檬。

六萎胰、A*算法（拓展）
綜合了DFS/BFS和啟發(fā)式尋路算法。