【数据结构OJ】实验10 拓扑排序与关键路径等

存一下代码：

A. 图综合练习–拓扑排序

整的很复杂

#include <iostream>

using namespace std;
const int N = 1005;
int n, d[N], top[N];
int q[N], v[N];
int h[N], e[N], ne[N], idx;

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

void sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}

void topsort(){
    int cnt = 0;
    int hh = 0, tt = -1;
    int t;
    for(int i = 1;i <= n; ++i)    if(d[i] == 0) q[++ tt] = i;
    while(hh <= tt){
        t = q[hh];
        top[cnt] = t;
        cnt ++;
        hh ++;
        int vi = 0;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            d[j] --;
            if(d[j] == 0)   v[vi++] = j;
        }
        sort (v, vi);
        for (int i = 0; i < vi; i++)    q[++ tt] = v[i];//cout << v[i] << ' ';
    }
    for (int i = 0; i < cnt; i++)   cout << top[i] - 1 << ' ';
    cout << endl;
}


void solve () {
    cin >> n;
    for (int i = 0; i <= n * n; i++)    h[i] = -1, d[i] = 0;
       
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x;  cin >> x;
            if (x == 1) add (i, j), d[j] ++;
        }
    }
    topsort ();
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

B. 关键路径-STL版

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int m[N][N], n, e, x, y;
int a[N][N], ans1[N], ans2[N], ans[N];
bool vis[N];
queue<int> q;

void topsort () {
    int tmp = n;
    while (tmp --) {
        for (int i = 0; i < n; i++) {
            int din = 0;
            for (int j = 0; j < n; j++)    din += a[j][i];
            if (din == 0 && vis[i] == 0) {
                vis[i] = true;
                q.push(i);
                for (int k = 0; k < n; k++) {
                    if (a[i][k] > 0)    a[i][k]--;
                }
            }
        }
    }
}

int main() {
    cin >> n >> e;
    for (int i = 0; i < e; i++)     cin >> x >> y >> m[x][y];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (m[i][j] != 0)    a[i][j] = 1;
            else    a[i][j] = 0;
        }
    }

    topsort ();
    auto q1 = q;
    auto q2 = q1;

    ans1[q.front()] = 0;
    q.pop();
    while (!q.empty()) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (m[i][q.front()] > 0) {
                ans[cnt] = ans1[i] + m[i][q.front()];
                cnt++;
            }
        }
        ans1[q.front()] = *max_element (ans, ans + cnt);
        q.pop();
    }

    stack<int> nq1;
    while (!q1.empty()) {
        nq1.push(q1.front());
        q1.pop();
    }
    queue<int> nq;
    while (!nq1.empty()) {
        nq.push(nq1.top());
        nq1.pop();
    }

    //逆top
    ans2[nq.front()] = ans1[nq.front()];
    nq.pop();
    while (!nq.empty()) {
    
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (m[nq.front()][j] > 0) {
                ans[cnt] = ans2[j] - m[nq.front()][j];
                cnt++;
            }
        }
        ans2[nq.front()] = *min_element (ans, ans + cnt);
        nq.pop();
    }

    for (int i = 0; i < n; i++)    cout << ans1[i] << " ";
    cout << endl;
    for (int i = 0; i < n; i++)    cout << ans2[i] << " ";
    cout << endl;;
}

C. 汉密尔顿回路

模拟走的过程

#include <bits/stdc++.h>

using namespace std;
const int N = 1005;
int n, m;
int e[N], ne[N], h[N], idx;
set <int> s[N];

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

void solve () {
    int p;
    cin >> p;
    vector <int> v;
    set <int> ss;
    for (int i = 0; i < p; i++) {
        int x;  cin >> x;
        v.push_back (x);
        ss.insert (x);
    }
    if (p != n + 1 || v[0] != v[p-1] || ss.size () != n) {
        puts ("NO");
        return ;
    }
    for (int i = 0; i < v.size () - 1; i++) {
        int a = v[i], b = v[i + 1];
        if (s[a].count (b) == 0) {
            puts ("NO");
            return ;
        }
    }   
    puts ("YES");
}

int main () {
    //memset (h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i< m; i++) {
        int a, b;
        cin >> a >> b;
        //add (a, b), add (b, a);
        s[a].insert (b), s[b].insert (a);
    }
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

D. 六度空间

因为数据水，floyd就过了

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int N = 1005, INF = 1e9;
int dis[N][N];
int h[N], e[N], ne[N], idx;

int main () {
    ios::sync_with_stdio (0);cin.tie (0);cout.tie (0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
        }
    }

    while (m --) {
        int a, b;
        cin >> a >> b;
        dis[a][b] = dis[b][a] = 1;
    }

    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                dis[i][j] = min (dis[i][j], dis[i][k]+ dis[k][j]);


    for (int i = 1; i <= n; i++) {
        cout << i << ": ";
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (dis[i][j] <= 6) cnt ++;
        }
        double xx = 100.0 * cnt / n;
        cout << fixed << setprecision (2) << xx << "%\n";
    }
}


//也就是求到该点距离<=6的点的个数(含自身)
//直接n遍dijkstra

E. 货币套汇（图路径）

#include <bits/stdc++.h>

using namespace std;
const int N = 35, inf = 1e9;
int n, m;
map <string, int> mp;
bool vis[N];
int cnt[N];
int h[N], e[N], ne[N], idx;
double w[N], dis[N];

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

bool spfa () {
    queue <int> q;
    vis[1] = true;
    cnt[1] = 1;
    dis[1] = 1;
    q.push(1);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
            double ww = dis[u] * w[i];
            if(dis[v] < ww) {
                dis[v] = ww;
                if(!vis[v]) {
                    vis[v] = false;
                    cnt[v] ++;
                    if(cnt[v] > n)  return true;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

void solve () {
    memset (h, -1, sizeof h), idx = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        mp[s] = i;
    }
    while (m --) {
        string x, y;
        double c;
        cin >> x >> c >> y;
        int a = mp[x], b = mp[y];
        add (a, b, c);
    }
    if (spfa ())    puts ("YES");
    else    puts ("NO");
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

//判正环

F. 拯救007

如代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 105, INF = 1e9;
int n, m;
int X[N], Y[N], a[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool Range (int x, int y) {
    if (x > -50 && x < 50 && y > -50 && y < 50)     return true;
    return false;
}

bool check_in (int x, int y) { //check能否从圆内跳到(x,y)
    //cout << x << ' ' << y << endl;
    if (x * x + y * y <= (m + 7.5) * (m + 7.5))     return true;
    return false;
} 

bool check_out (int x, int y) { //check能否从(x,y)跳出框
    //cout << x << ' ' << y << endl;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i] * m, yy = y + dy[i] * m;
        //cout << xx << ' ' << yy << endl;
        if (!Range (xx, yy))    return true;
    }
    return false;
} 

bool check (int xa, int ya, int xb, int yb) { //check(xa, ya)与(xb, yb)能否直接可达
    if ((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb) <= m * m) return true;
    return false;
} 

void print () {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
}

signed main () {
    cin >> n >> m;
    for (int i = 0; i < n; i++)    cin >> X[i] >> Y[i];
    vector <int> st; //可达起点的点
    for (int i = 0; i < n; i++) {
        if (check_in (X[i], Y[i]))  st.push_back (i);
    }
    vector <int> ed; //可跳出去的点
    for (int i = 0; i < n; i++) {
        if (check_out (X[i], Y[i]))  ed.push_back (i);
    }

    // for (int i = 0; i < n; i ++ )
    //     for (int j = 0; j < n; j ++ )
    //         if (i == j) a[i][j] = 0;
    //         else a[i][j] = INF;

    //处理任意可达的两点
    for (int i = 0; i < n; i++) {
        a[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (check (X[i], Y[i], X[j], Y[j])) a[i][j] = a[j][i] = 1;
        }
    }
    //print ();

    for (int k = 0; k < n; k ++)
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++) {
                if (a[i][k] && a[k][j]) a[i][j] = 1;
            }
                //a[i][j] = min (a[i][j], a[i][k]+ a[k][j]);

    //print ();

    for (auto i : st) {
        for (auto j : ed) {
            //cout << i << ' ' << j << endl;
            if (a[i][j]) {
                puts ("Yes");
                return 0;
            }
        }
    }
    puts ("No");
}

G. 先序+中序还原二叉树

dfs

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

int dfs(char *pre, char *in, int n) {
    if (n == 0)    return 0;
    int i;
    for (i = 0; i < n; i++) {
        if (in[i] == pre[0])    break;
    }
    int left = dfs(pre + 1, in, i);                     
    int right = dfs(pre + i + 1, in + i + 1, n - i - 1); 
    return max(left, right) + 1; 
}
int main() {
    int n;
    cin >> n;
    char pre[n + 1], in[n + 1]; //先序和中序
    cin >> pre >> in;
    cout << dfs(pre, in, n) << endl;
}

原文地址：http://www.cnblogs.com/CTing/p/16890117.html