【数据结构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;
}