第六場比賽題解

EZ?

z051：

針對每一點都做一次 dfs 看看能不能完全走訪就好。

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

int main() {
  int n, m, i, j, u, v;

  vector<int> g[105];  // graph
  int chk[105];
  stack<int> dfs;
  bool flag = false;

  cin >> n >> m;
  for (i = 0; i < m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      chk[j] = 0;
    }
    dfs.push(i);
    chk[i] = 1;
    while (!dfs.empty()) {
      int top = dfs.top();
      dfs.pop();
      for (auto k : g[top]) {
        if (chk[k] == 0) {
          dfs.push(k);
          chk[k] = 1;
        }
      }
    }
    for (j = 0; j < n; j++) {
      if (chk[j] == 0) {
        break;
      }
    }
    if (j == n) {
      flag = 1;
      break;
    }
  }
  cout << (flag == true ? "Yes" : "No") << endl;

  return 0;
}

z052：

因為此圖無環，也就是說，如果某一點沒有進入該點的路徑，他必為起點(不然會不到他)，若有兩個以上這樣的點，則不可能是 LAN 通圖。這是其中一位同學寫的 code 寫得很乾淨。

n, m = list(map(int, input().split()))
l = [-1] * n
for i in range(m):
  a, b = list(map(int, input().split()))
  l[b] += 1
if l.count(-1) > 1:
  print("No")
else:
  print("Yes")

z053：

在建圖的時候如果有一條路叫做 u v，則必須建兩條路徑 u->v, v->u，再來從任一一點開始走訪就好。

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, u, v, cnt = 0;
vector<int> g[1005000];  // graph
int chk[1005000] = {0};
stack<int> dfs;
bool flag = false;

int main() {
  cin >> n >> m;
  for (i = 0; i < m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  dfs.push(0);
  chk[0] = 1;

  while (!dfs.empty()) {
    int top = dfs.top();
    dfs.pop();
    for (auto k : g[top]) {
      if (chk[k] == 0) {
        dfs.push(k);
        chk[k] = 1;
      }
    }
  }
  for (j = 0; j < n; j++) {
    if (chk[j] == 0) {
      break;
    }
  }
  cout << (j == n ? "Yes" : "No") << endl;
  return 0;
}

z054：

有向無環圖，就算有負權重邊，也存在最長路徑
複雜度允許，直接用 bellman-ford algorithm：

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

int const maxe = 6010, maxv = 510;

int V, C, E, u[maxe], v[maxe], h[maxe];
int best, d[maxv];

int main()
{
  scanf("%d%d%d", &V, &C, &E);
  for(int i = 0; i < E; i++) scanf("%d%d%d", &u[i], &v[i], &h[i]);

  memset(d, -1, sizeof d);
  d[C] = best = 0;

  for(int i = 1; i < V; i++)
    for(int j = 0; j < E; j++) if(~d[u[j]]) {
      d[v[j]] = max(d[v[j]], d[u[j]] + h[j]);
      best = max(best, d[v[j]]);
    }

  printf("%d\n", best);

  return 0;
}

z055：

將所有路線依運送量由大排到小，再依序取邊配合 disjoint set 建立出 MST。
之後利用 LCA 求解…LCA 請自行上網查詢或參閱下方程式碼與註解@~@
pa[d][n] = 從點 n 往上找的第 2^d 個點
mn[d][n] = 從點 n 往上到 pa[d][n] 之間所有邊的最小權重
dep[n] = 點 n 在此 MST 中的深度 ( 樹根深度為 0 )

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

struct edge {
  int a, b, c;
} es[1000011];
vector<edge> g[100011];
int pa[20][100011], mn[20][100011], dep[100011];
int ds[100011];

int find(int i) //disjoint set
{
  if (ds[i] == i)
    return i;
  else
    return ds[i] = find(ds[i]);
}

void unite(int a, int b) //disjoint set
{
  ds[find(a)] = find(b);
}

void dfs(int i, int p, int c, int d) //DFS
{
  pa[0][i] = p;
  mn[0][i] = c;
  dep[i] = d;
  for (edge j : g[i])
    if (j.b != p)
      dfs(j.b, i, j.c, d + 1);
}

int lca(int a, int b) //LCA
{
  if (dep[a] > dep[b]) //保證點 a 必定不比點 b 還深
    swap(a, b);
  int ans = INF;
  for (int i = 19; i >= 0; i--) //此迴圈結束時，點 a 和點 b 深度相同
    if (dep[pa[i][b]] >= dep[a]) {
      ans = min(ans, mn[i][b]);
      b = pa[i][b];
    }
  for (int i = 19; i >= 0; i--) //此迴圈結束時，點 a 和點 b 的父親會相同
    if (pa[i][b] != pa[i][a]) {
      ans = min(ans, mn[i][b]);
      ans = min(ans, mn[i][a]);
      b = pa[i][b];
      a = pa[i][a];
    }
  if (a != b) {
    ans = min(ans, mn[0][b]);
    ans = min(ans, mn[0][a]);
  }
  return ans;
}

int main()
{
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++)
    scanf("%d%d%d", &es[i].a, &es[i].b, &es[i].c);
  sort(es, es+m, [](edge a, edge b) {return a.c > b.c;}); //將邊由大到小排序
  for (int i = 0; i < n; i++)
    ds[i] = i;
  for (int i = 0; i < m; i++) { //建立 MST
    if (find(es[i].a) != find(es[i].b)) {
      g[es[i].a].push_back({0, es[i].b, es[i].c});
      g[es[i].b].push_back({0, es[i].a, es[i].c});
      unite(es[i].a, es[i].b);
    }
  }

  dfs(0, 0, INF, 0); // 走訪 MST

  for (int i = 1; i < 20; i++)
    for (int j = 0; j < n; j++)
      pa[i][j] = pa[i - 1][pa[i - 1][j]];
  for (int i = 1; i < 20; i++)
    for (int j = 0; j < n; j++)
      mn[i][j] = min(mn[i - 1][j], mn[i - 1][pa[i - 1][j]]);

  int q;
  scanf("%d", &q);
  while (q--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", lca(a, b));
  }
}

第六場比賽 題解