2019年電子科技大學ACM暑期前集訓圖論專題解題報告

A

這題要求調整部分邊的方向,把有環的有向圖中部分邊反向,使其變成無環圖,我們要求的是調整的邊的最大權值最小的方案。首先我們要知道一個原理,如果無環圖加入$A \to B$會使其變爲有環圖,那麼$B\to A$一定是連通的,那麼加入邊$B\to A$不會使其成環。那麼,我們刪掉某些邊得到無環圖之後,必然可以加回來得到無環圖。而如果我們刪除權值不大於ans的所有邊,我們可以很快地算出是否有環。如果有環,則ans一定小於答案,如果無環,則ans不小於答案。根據這一性質,我們可以二分套判環解決,判環使用拓撲方法,複雜度爲$O((m+n)logM)M$可以是最大邊權,也可以是邊權的中位數($O(n)$找中位數要多寫不少代碼,並且這題不必要)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
  int v, w;
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, M = 0;
  cin >> n >> m;
  vector<E> path[n + 1];
  FOR(i, 0, m) {
    int u, v, w;
    cin >> u >> v >> w;
    M = max(M, w);
    path[u].push_back({v, w});
  }
  int ans = M / 2;
  int tmp[2] = {0, M};
  do {
    vector<E> pathcpy[n + 1];
    int cnt[n + 1];
    RST(cnt);
    FOR(i, 1, n + 1) for (auto p : path[i]) if (p.w > ans) {
      pathcpy[i].push_back(p);
      ++cnt[p.v];
    }
    queue<int> q;
    FOR(i, 1, n + 1) if (!cnt[i]) q.push(i);
    int c = 0;
    while (!q.empty()) {
      ++c;
      int now = q.front();
      q.pop();
      for (auto p : pathcpy[now]) {
        --cnt[p.v];
        if (!cnt[p.v]) q.push(p.v);
      }
    }
    tmp[c == n] = ans + (c != n);//有環時答案大於ans,可以從ans+1開始
    ans = ((ll)tmp[0] + tmp[1]) / 2;
  } while (tmp[1] != tmp[0]);
  cout << ans;
}

B

這題是求免費一條邊的最小生成樹權值和,以及要使權值和等於該值的情況下,可以選擇的免費邊的數量。首先,最小生成樹的算法這裏不再累述,kruskal算法即可。然後根據貪心的思想易知第一個問題的答案爲最小生成樹總權值-最小生成樹上最大邊權值。然後難點就在於第二個問題。樹上權值最大的邊(可能有多條相等)如果能被另一條邊替代,那麼替代後免費新的邊,也能得到相同的結果。所以我們要找到可以替換樹上最大邊的邊。我們可以把最大邊去掉(第一次並查集記錄最大邊條數,第二次並查集參考G題),這樣樹就出現了中斷,然後我們需要尋找能夠把中斷補上的邊。我們沿用kruskal算法的並查集,即可輕鬆判斷一條邊是否能補上中斷。遍歷一遍邊即可,由最小生成樹的性質,小邊不可能替代大邊,所以權值小於樹上最大邊的邊可以直接略過。

最大部分的時間複雜度就是kruskal的時間複雜度,即$O(mlogm+mA(n)+n)$,其實複雜度最大的地方就是排序邊的O(mlogm)

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)

int fa[100001], depth[100001];
int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
  u = find(u), v = find(v);
  if (depth[u] > depth[v])
    fa[v] = u;
  else {
    fa[u] = v;
    if (depth[v] == depth[u]) ++depth[v];
  }
}
struct E {
  int u = 0, v = 0, w = 0;
  bool operator<(E x) const { return w < x.w; }
};
E edge[200005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int M = 0, n, m, i = 0, cm = 0;
  ll S = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    edge[i] = {u, v, w};
  }
  sort(edge, edge + m);
  for (auto p : edge)//第一次並查集
    if (i == n - 1)
      break;
    else if (find(p.u) == find(p.v))
      continue;
    else {
      ++i;
      connect(p.u, p.v);
      S += p.w;
      if (p.w > M) {
        M = p.w;
        cm = 1;
      } else if (p.w == M)
        ++cm;//記錄樹上最大邊的條數
    }
  for (int i = 1; i <= n; ++i) fa[i] = i;
  RST(depth);
  int cnt = i = 0;
  for (auto p : edge)
    if (i == n - 1 - cm)//跳過樹上最大邊
      break;
    else if (find(p.u) == find(p.v))
      continue;
    else {
      ++i;
      connect(p.u, p.v);
    }
  for (auto p : edge)//如果想進一步優化,可以保留第二次並查集的最後位置,然後從該位置-cm開始
    if (p.w >= M && find(p.u) != find(p.v)) ++cnt;
  cout << S - M << ' ' << cnt;
}

C

該題判斷是否有歐拉路徑,然後輸出字典序最小的歐拉路徑。判斷歐拉路徑根據出入度,所有點入度等於出度則有歐拉回路,入度比出度大一的點和出度比入度大一的點各一個(必須兩者都有一個)則有歐拉路徑(非迴路)。然後是輸出部分,如果是迴路,要從有路的最小點作爲起點。然後可以用一個dfs,從小的邊開始搜,回溯的時候即可得到反向的歐拉路徑,再反向輸出即可。由於路徑可能很長,搜索深度可能很深,dfs遞歸會發生棧溢出,可以加inline內聯交給GNU的強大力量去解決(這樣寫甚至跑起來更快),也可以寫非遞歸版的dfs(碼量稍大)。複雜度$O(m)$

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int n, m, ans[2000005], pos = 0, cnt = 0;
vector<int> path[1000005];
inline void dfs(int s) {//遞歸版
  while (!path[s].empty()) {
    int p = path[s].back();
    path[s].pop_back();
    dfs(p);
    ans[cnt++] = p;
  }
}
void dfs(int s) {//非遞歸版
  int stack[2000005], top = 0;
  stack[++top] = s;
  while (top) {
    int x = stack[top];
    if (path[x].empty()) {
      top--;
      ans[cnt++] = x;
    } else {
      stack[++top] = path[x].back();
      path[x].pop_back();
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  int i[n + 1], o[n + 1];
  RST(i);
  RST(o);
  FOR(j, 0, m) {
    int u, v;
    cin >> u >> v;
    path[u].push_back(v);
    ++i[v], ++o[u];
  }
  int s = 0, t = 0;
  FOR(j, 1, n + 1) {
    if (o[j] == i[j])
      continue;
    else if (o[j] - i[j] == 1) {
      if (s) goto shame;
      s = j;
    } else if (o[j] - i[j] == -1) {
      if (t) goto shame;
      t = j;
    } else
      goto shame;
  }
  if ((bool)s ^ (bool)t) goto shame;
  for (auto &p : path) sort(p.begin(), p.end(), greater<int>());
  if (!s)
    while (!o[++s])
      ;
  dfs(s);
  //遞歸版起點要單獨輸出一下  cout << s << ' ';
  while (cnt) cout << ans[--cnt] << ' ';
  return 0;
shame:
  cout << "What a shame!";
}

F

這題要求的是在一個有向,可能有環的正點權圖上獲取最大值。如果它是無環的,那麼以終點的權作爲邊權求最長路即可(無環圖不會到達一個點多次),因此,我們就考慮怎麼處理環。這樣就引入了縮點的概念(據說暴力也可以過?),爲了獲取最大權,進入環中一個點後必然會把整個環喫完,然後從中選擇合適的點出環。根據這一性質,我們可以找到圖中的環(不一定是單層的環,標準的名稱爲強聯通分量),把每一個環縮成一個點,權值爲各點權值之和,環內點與環外點的路徑都加在縮成的點上。實現的方法有Kosaraju、Tarjan(沒錯,又是這位圖靈獎巨佬)等。本題以Kosaraju爲例,從起點開始進行一次dfs,回溯時按順序記錄點,再在反向圖上,按之前的記錄逆序一次dfs,在第i次反向dfs中初次找到的點(當然,正向dfs中不可達的點要排除)就構成了第i個強聯通分量。然後建立新圖,按一開始說的無環圖做法即可,正權圖最長路相當於負權圖最短路,使用spfa算法求解。Kosaraju的複雜度通常爲$O(n+m)$,時間瓶頸在於spfa,複雜度最壞可達$O(mn)$

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
  int v, l;
};
vector<int> path[3001], repath[3001];
int m, n, l[3001], dfn[3001], pos = 0, vis[3001], revis[3001], f[3001], point[3001], s, p[3001], dis[3001];
vector<E> fpath[3001];
inline void dfs(int now) {//正向dfs
  vis[now] = 1;
  for (auto &p : path[now])
    if (!vis[p]) dfs(p);
  dfn[pos++] = now;
}
inline void redfs(int now, int pos) {//反向dfs
  if (!vis[now] || revis[now]) return;
  revis[now] = 1;
  f[now] = pos;
  point[pos] += l[now];
  for (auto &p : repath[now]) redfs(p, pos);
}
void spfa() {
  RST(dis);
  queue<int> q;
  dis[f[s]] = point[f[s]];
  q.push(f[s]);
  bool has[3001] = {0};
  has[f[s]] = 1;
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    has[now] = 0;
    for (auto p : fpath[now])
      if (dis[p.v] < dis[now] + p.l) {
        dis[p.v] = dis[now] + p.l;
        if (!has[p.v]) {
          q.push(p.v);
          has[p.v] = 1;
        }
      }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  int u[m], v[m];
  FOR(i, 0, m) {
    cin >> u[i] >> v[i];
    path[u[i]].push_back(v[i]);
    repath[v[i]].push_back(u[i]);//反向圖
  }
  FOR(i, 1, n + 1) cin >> l[i];
  int np;
  cin >> s >> np;
  FOR(i, 0, np) cin >> p[i];
  RST(vis);
  dfs(s);
  int tmp = pos;
  pos = 0;
  RST(revis);
  for (int i = tmp - 1; i >= 0; --i) redfs(dfn[i], pos++);
  FOR(i, 0, m)
    if (f[u[i]] != f[v[i]])
      fpath[f[u[i]]].push_back({f[v[i]], point[f[v[i]]]});//建立縮點後的新圖
  spfa();
  int M = 0;
  FOR(i, 0, np) M = max(M, dis[f[p[i]]]);
  cout << M;
}

G

這是本次的簽到題,解題方法是根據貪心的思想,按權值從小到大取邊,同時採用並查集判斷邊是否可取,這種算法被稱爲 kruskal算法,複雜度爲$O(mlogm+mA(n)+n)$,瓶頸是邊排序的$O(mlogm)$

代碼:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
int fa[1001], depth[1001];
int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
  u = find(u), v = find(v);
  if (depth[u] > depth[v])
    fa[v] = u;
  else {
    fa[u] = v;
    if (depth[v] == depth[u]) ++depth[v];
  }
}
struct E {
  int u, v, w;
  bool operator<(E x) const { return w < x.w; }
};
E edge[500000];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k, pos = 0;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    edge[i] = {u, v, w};
  }
  sort(edge, edge + m);
  int result = 0;
  for (auto p : edge)
    if (n == k)
      break;
    else if (find(p.u) == find(p.v))
      continue;
    else {
      connect(p.u, p.v);
      --n;
      result += p.w;
    }
  cout << result;
}

H

這題的思路沒有什麼好說的,很明顯的網絡流板題。下面簡單說一下網絡流(以後有時間可能會單獨寫一篇博客,也很可能會鴿)

網絡流是一個有若干條帶權(容量)邊組成的,固定源點和匯點的有向圖。本題要解決的是,從源點產生的流(本題中水流是個很形象的例子),經過各邊彙集到匯點,這樣的流的最大流量。顯然,對於每個點,流入流出的量相等,總流量守恆;同時,每條邊上的流量均不能超過該條邊的容量。在思考怎麼求出最大流的過程中,我們要了解一個非常重要的定理──增廣路定理。當我們找到網絡流中一條從源點到匯點的通路時,可以把這條通路的各段邊的容量減少一個值 $a$,最好的情況下下,這樣處理後的網絡的最大流就減少了 $a$,這樣的網絡我們稱之爲殘量(殘留容量)網絡,當殘量網絡中沒有上述通路時,殘量網絡的最大流爲0,原網絡的最大流爲$\sum a$,我們可以利用dfs找通路,$a$ 取路徑上的最小殘量,不斷循環得出結果。

然而,這樣做會存在一些問題

1.每次找到的路徑可以是最好的路連接徑嗎?似乎不是。這種情況我們在數據結構專題的K題(點此進入)中遇到過,當時我們在刪點的時候加入新的點來模擬反悔的操作。這裏我們也可以加入反向邊來模擬反悔的操作。 2.這樣反覆的dfs很耗時,可能會反覆搜某一條邊,尤其是各邊容量的極差很大時。該算法稱爲Ford-Fulkerson算法,複雜度爲$O(mC)$,通常只建議用來處理容量很小的圖,如單位容量簡單網絡最大流的快速算法(其實我並不會)的其中部分步驟可以用它。可以採用bfs,即Edmonds-Karp算法來改進,複雜度爲$O(nm^2)$。但是EK算法過這題似乎有點緊,有沒有更快的做法?dinic、ISAP、等(其實兩者原理很像,優化魔改之後界限並不是那麼清晰)。

我們把所有的節點根據與源點的距離分層,找增廣路時只取依層遞進的路徑,然後再重新分層,反覆循環。複雜度最大爲$O(mn^2)$(較松,還能加優化),具體實現如下(注意有註釋的地方)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
  int e, c;
};
int n, m, cur[201], tail = 0, depth[201];
bool visited[201];
edge edges[20001];
vector<int> path[201];
inline void addedge(int s, int e, int c) {//建圖時把反向邊位置也分配好,並且分配到正向邊位置^1,便於快速找反向邊
  edges[tail] = {e, c};
  path[s].push_back(tail++);
  edges[tail] = {s, 0};
  path[e].push_back(tail++);
}
bool dinic_bfs() {//通過bfs,逐層外擴,實現分層
  RST(depth);
  RST(visited);
  visited[1] = 1;
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (auto p : path[now]) {
      if (!visited[edges[p].e] && edges[p].c) {
        depth[edges[p].e] = depth[now] + 1;
        q.push(edges[p].e);
        visited[edges[p].e] = 1;
      }
    }
  }
  return visited[n];//如果匯點已不可達,說明已無增廣路,則結束循環,否則繼續
}
int dinic_dfs(int now, int cap) {
  if (now == n || !cap) return cap;
  for (auto &i = cur[now]; i < path[now].size(); ++i) {//加入cur數組實現當前弧優化,搜到每條點時之前已被搜過的點不會搜出新的增廣路路徑,因此可以直接跳過。
    auto &p = path[now][i];
    if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
      int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
      edges[p].c -= tmp;
      edges[p ^ 1].c += tmp;//反向邊加上相同的值,後面可以走這條反向邊來反悔之前選的邊
      if (tmp) return tmp;//找到有值的增廣路,返回
    }
  }
  depth[now] = -1;
  return 0;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  while (m--) {
    int s, e, c;
    cin >> s >> e >> c;
    addedge(s, e, c);
  }//首先建圖
  int result = 0;
  while (dinic_bfs()) {//然後開始跑分層
    RST(cur);
    int tmp;
    while ((tmp = dinic_dfs(1, INT_MAX >> 2))) result += tmp;//再在圖中跑符合要求的增廣路,找不到了就重新分層
  }
  cout << result;
}

I

這是一道很裸的有向圖(無向圖拆邊,然後做法也一樣)K短路問題,我們可以採用一個方向最短路算法初始化(dijkstra,spfa什麼的都可以,時間很鬆),一個方向A*啓發式搜索(這類題是$h(x)=h*(x)$的特例)的方法解題。最短路算法不再多說,對於A*算法,我們用一個優先隊列,從起點開始,每次擴展其直接可達的邊入隊,這樣的過程中,跑出i次第i短路時,它可以擴展出i+1次第i+1短路,由此,當某條邊出隊K次時可以終止,此時的路徑長度就是第k短路的長度。複雜度(貌似)$O(kmlogm)$

代碼及註釋

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
  int v;
  ll w;
};
struct status {
  int p;
  ll l;
  bool operator<(status b) const { return l > b.l; }
};
struct astar {
  int v;
  ll g, f;
  bool operator<(astar b) const { return f == b.f ? g > b.g : f > b.f; }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k, s, t;
  cin >> n >> m >> k >> s >> t;
  vector<edge> path[n + 1], repath[n + 1];
  ll dis[n + 1];
  int visited[n + 1];
  for (int i = 0; i < m; ++i) {//建立正向圖和反向圖
    int u, v, w;
    cin >> u >> v >> w;
    path[u].push_back({v, w});
    repath[v].push_back({u, w});
  }
  memset(dis, 0x3f, sizeof(dis));
  memset(visited, 0, sizeof(visited));
  priority_queue<status> q;
  dis[t] = 0;
  q.push({t, 0});
  while (!q.empty()) {//反向dijkstra算法求最短路,預處理出h(x)
    status now = q.top();
    q.pop();
    if (visited[now.p]) continue;
    visited[now.p] = 1;
    for (auto &p : repath[now.p]) {
      if (dis[p.v] > dis[now.p] + p.w) {
        dis[p.v] = dis[now.p] + p.w;
        q.push({p.v, dis[p.v]});
      }
    }
  }
  memset(visited, 0, sizeof(visited));
  priority_queue<astar> paths;//然後正向通過A*算法得出結果
  paths.push({s, 0, dis[s]});
  while (!paths.empty()) {
    astar now = paths.top();
    paths.pop();
    if (++visited[now.v] == k && now.v == t) {
      cout << now.f;
      return 0;
    };
    if (visited[now.v] > k) continue;
    for (auto p : path[now.v])
      paths.push({p.v, p.w + now.g, p.w + now.g + dis[p.v]});
  }
  cout << -1;//跑完之後仍找不到,則說明沒有
}

J

這道題目給了我們一個二分圖,然後希望求一個最小的點的數量,來覆蓋這一個二分圖的所有邊。我們求出最大匹配,在每個匹配的其中一個點上放置一個點即可覆蓋,因此該題實際上是求最大匹配數,我們把二分圖各邊的容量設爲1,然後加入源點s並依次連至左邊的元素,右邊的元素依次連至匯點t,該問題便轉化爲了一個網絡流問題,而且是單位容量的簡單網絡流。對於這種特殊情況的網絡流,可使用Hopcroft算法達到$O(m\sqrt n)$的複雜度,使用常規的dinic算法也可以平穩通過。以下代碼爲dinic算法(具體做法見H題)

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
  int e, c;
};
int a, b, m, cur[200002], tail = 0, depth[200002], End;
bool visited[200002];
edge edges[500000];
vector<int> paths[200002];
inline void addedge(int s, int e, int c) {
  edges[tail] = {e, c};
  paths[s].push_back(tail++);
  edges[tail] = {s, 0};
  paths[e].push_back(tail++);
}
bool dinic_bfs() {
  RST(depth);
  RST(visited);
  *visited = 1;
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (auto p : paths[now]) {
      if (!visited[edges[p].e] && edges[p].c) {
        depth[edges[p].e] = depth[now] + 1;
        q.push(edges[p].e);
        visited[edges[p].e] = 1;
      }
    }
  }
  return visited[End];
}
int dinic_dfs(int now, int cap) {
  if (now == End || !cap) return cap;
  for (auto &i = cur[now]; i < paths[now].size(); ++i) {
    auto &p = paths[now][i];
    if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
      int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
      edges[p].c -= tmp;
      edges[p ^ 1].c += tmp;
      if (tmp) return tmp;
    }
  }
  depth[now] = -1;
  return 0;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> a >> b >> m;
  End = a + b + 1;//0爲源點,1到a+b爲二分圖中點,a+b+1爲匯點
  while (m--) {
    int s, e;
    cin >> s >> e;
    addedge(s, e + a, 1);
  }
  FOR(i, 1, a + 1) addedge(0, i, 1);
  FOR(i, 1, b + 1) addedge(i + a, End, 1);//建好圖,後面就搬H題過來了
  int result = 0;
  while (dinic_bfs()) {
    RST(cur);
    int tmp;
    while ((tmp = dinic_dfs(0, INT_MAX >> 2))) result += tmp;
  }
  cout << result;
}

K

這題求的是免費K條邊的最短路。我們的一個容易想到的直觀的思路是做分層圖,把已經免費的次數作爲一個維度建圖,但是如果完整的建完整張圖,會導致內存超出,而分層圖中存在大量的重複邊,可以都從第一層取邊,然後再加上跨層的邊。但我覺得這題更好的思路是,最短路算法本質上是一個一維狀態的動態規劃(dijkstra偏向於貪心,是bfs的擴展,但其本質上仍然是動態規劃的一種),而這題我們需要的是一個二維的動態規劃。我們可以按照最短路算法思路,在其基礎上使用位置+已免費邊數的狀態替換位置狀態,在狀態轉移的過程中,由最短路算法的$dis[q]=min{dis[p]+w(p\to q)}$,拓展爲$dis[q][h]=min({dis[p][h]+w(p\to q)},{dis[p][h-1]})$,p爲所有存在邊$p\to q$的點。然後該方程的性質仍然滿足dijkstra的要求(轉移過程中$dis[q][h]$不小於$dis[p][h]$和$dis[p][h-1]$),因此可以按照dijkstra的思路,用修改版的dijkstra求解。複雜度$O(kmlogkn)$。spfa的話,直接交貌似會TLE,SLF優化貌似對這種情況效果比較好。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int s, t, k;
ll dis[10005][25];
struct status {//原版dijstra是位置+當前位置的最短路,這裏增加來b表示免費的次數
  int a = 0, b = 0;
  ll dis;
  bool operator<(status x) const { return dis > x.dis; }//注意這裏dis要靜態保存,去掉dis然後動態計算(return dis[a][b] > dis[x.a][x.b])會導致順序出錯,WA on 10
};
struct edge {
  int v = 0, w = 0;
};
vector<edge> path[10005];
ll dijkstra() {
  RSTV(dis, 0x7f);
  priority_queue<status> q;
  for (auto &p : dis[s]) p = 0;
  q.push({s, 0});
  bool visited[10005][25];
  while (!q.empty()) {
    status now = q.top();
    q.pop();
    if (visited[now.a][now.b]) continue;
    visited[now.a][now.b] = 1;
    for (auto &p : path[now.a]) {
      if (dis[p.v][now.b] > dis[now.a][now.b] + p.w) {
        dis[p.v][now.b] = dis[now.a][now.b] + p.w;
        q.push({p.v, now.b, dis[p.v][now.b]});
      }//第一種轉移,同正常的dijkstra
      if (now.b < k && dis[p.v][now.b + 1] > dis[now.a][now.b]) {
        dis[p.v][now.b + 1] = dis[now.a][now.b];
        q.push({p.v, now.b + 1, dis[p.v][now.b + 1]});
      }//第二種轉移,跨層,dis值不增加
    }
  }
  return dis[t][k];
}
signed main() {//建圖,跑最短路,輸出
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m >> k >> s >> t;
  while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    path[u].push_back({v, w});
    path[v].push_back({u, w});
  }
  cout << dijkstra();
}

L

這題有些複雜,購買物品需要花費,購買某個集合的所有物品可獲得相應的獎勵,答案要求是兩者差最大,而不是限制最大花費。這樣看起來比動態規劃中01揹包問題複雜得多。這種問題稱爲最大權閉合子圖問題,我們從源點連接所有的物品,所有集合連向匯點,容量均取正。然後根據包含關係,用無限容量的邊連接物品和集合。這樣一來,就可以用割去某個物品到源點的邊模擬購買此物品,某個集合被買完之後其到終點的流被切斷。這樣一來我們求一個割,即使得所有的邊都被割斷,所花費的最小代價,這樣對於每個集合,要麼獲得並且花費了相應的代價,要麼放棄了該集合。所有集合的總的壓歲錢數量減去此時的割,就是他可以剩下的壓歲錢。我們要求最大的剩餘壓歲錢,就要求最小割。顯然,我們按照最大流的路徑去割是最佳方案,這樣最小割就等於最大流(最大流做法見H題)。複雜度$O((n+m)^2\sum k)$

代碼及註釋

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
  int e, c;
};
int n, m, t, depth[20002], tail = 0, cur[20002];
E edges[250000];
bool visited[20002];
vector<int> paths[20002];
inline void addedge(int s, int e, int c) {
  edges[tail] = {e, c};
  paths[s].push_back(tail++);
  edges[tail] = {s, 0};
  paths[e].push_back(tail++);
}
bool dinic_bfs() {
  RST(depth);
  RST(visited);
  visited[0] = 1;
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (auto p : paths[now]) {
      if (!visited[edges[p].e] && edges[p].c) {
        depth[edges[p].e] = depth[now] + 1;
        q.push(edges[p].e);
        visited[edges[p].e] = 1;
      }
    }
  }
  return visited[t];
}
int dinic_dfs(int now, int cap) {
  if (now == t || !cap) return cap;
  for (auto &i = cur[now]; i < paths[now].size(); ++i) {
    auto &p = paths[now][i];
    if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
      int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
      edges[p].c -= tmp;
      edges[p ^ 1].c += tmp;
      if (tmp) return tmp;
    }
  }
  depth[now] = -1;
  return 0;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  FOR(i, 1, m + 1) {
    int tmp;
    cin >> tmp;
    addedge(0, i, tmp);
  }
  t = m + n + 1;
  int sum = 0;
  FOR(i, m + 1, t) {
    int c, k;
    cin >> c >> k;
    sum += c;//計算所有集合的壓歲錢數量總和
    addedge(i, t, c);
    while (k--) {
      int tmp;
      cin >> tmp;
      addedge(tmp, i, INT_MAX >> 1);
    }
  }//建圖完,0爲源點,1到m爲物品,m+1到m+n爲集合,m+n+1爲匯點,然後跑最大流
  int result = 0;
  while (dinic_bfs()) {
    RST(cur);
    int tmp;
    while ((tmp = dinic_dfs(0, INT_MAX >> 1))) result += tmp;
  }
  cout << sum - result;//輸出結果
}

M

這題是一道差分約束,某兩個量存在一個大於關係,可以用一條權值爲1(它們至少相差1)的有向邊連接(小於則相反),等於就是權值爲0的雙向邊,這樣,然後從源點向每條邊添加權值爲最小值1的邊,這樣源點到每個點的最長路長度就是它的最小值,題目要求輸出的就是這些值的和。如果有環就說明存在矛盾。帶判環的spfa可以用來解決這個問題。複雜度$O(nm)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
  int v, l;
};
vector<edge> path[10001];
int dis[1001];
int spfa() {
  RSTV(dis, 0x80);
  queue<int> q;
  *dis = 0;
  int cnt[1001] = {0};
  q.push(0);
  bool has[1001] = {1};
  ++*cnt;
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    has[now] = 0;
    for (auto p : path[now])
      if (dis[p.v] < dis[now] + p.l) {
        dis[p.v] = dis[now] + p.l;
        if (!has[p.v]) {
          q.push(p.v);
          has[p.v] = 1;
          ++cnt[p.v];
          if (cnt[p.v] > 1000) return 0;
        }
      }
  }
  return 1;
}
int main() {
  int n, m;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  while (m--) {
    int a, b, o;
    cin >> o >> a >> b;
    switch (o) {
      case 1:
        path[b].push_back({a, 1});
        break;
      case 2:
        path[a].push_back({b, 1});
        break;
      case 3:
        path[a].push_back({b, 0});
        path[b].push_back({a, 0});
    }
  }//建圖,過程如前面的描述
  FOR(i, 1, n + 1) path->push_back({i, 1});
  int result = 0;
  if (spfa()) {
    FOR(i, 1, n + 1) result += dis[i];
    cout << result;
  } else//如果spfa跑失敗了就輸出-1
    cout << -1;
}

N

這題,最少花費,可以讓人聯想到圖上面的最短路,而問題的關鍵就是怎麼建圖,即找到滿足要求的點(狀態)和轉移路徑。狀態的描述方式爲二進制(參考狀壓dp。然後跑dijkstra即可。(點和邊的判斷方式見註釋),複雜度貌似爲$O(2^n+2^{2(n-\overline m)}+2^{n-\overline m}C_{n-\overline m}^{k-\overline m})$,$\overline m$是$m$減去$m$對cp關係中環的數量,似乎$n$很大(15),$m$很小(1)的數據可以卡掉(如有錯誤請指正)

代碼及註釋

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
  int v, l;
};
int pos = 0, n, m, k, point[2 << 16];//末位表示潔姐姐,然後從右到左依次表示其他人
vector<E> path[2 << 16];
pii against[15];
bool judge_p(int x) {//判斷點(狀態)
  if ((x & 1)) return 1;//如果潔姐姐在當然沒問題
  FOR(i, 0, m)
  if (x >> against[i].first & 1 && x >> against[i].second & 1) return 0;//如果不在就要判斷有沒有cp,沒有才過關
  return 1;
}
int judge_e(int x, int y) {//判斷邊(轉移)
  int det = x ^ y, cnt = 0;
  if (max(x, y) - min(x, y) != det) return 0;//去掉既有有人上,又有人下的情況
  if (!(det & 1)) return 0;//去掉潔姐姐沒有參加的情況
  FOR(i, 0, 16) cnt += det >> i & 1;
  return cnt > k ? 0 : cnt;//參加的人不能超過k,滿足條件的輸出返回人數,作爲增加的邊的邊權。
}
void addedge(int u, int v, int l) {
  path[u].push_back({v, l});
  path[v].push_back({u, l});
}
int dijkstra() {
  priority_queue<pii> q;
  bool visited[2 << 16] = {0};
  int dis[2 << 16];
  RSTV(dis, 0x3f);
  *dis = 0;
  q.push({0, 0});
  while (!q.empty()) {
    pii now = q.top();
    q.pop();
    if (visited[now.first]) continue;
    visited[now.first] = 1;
    for (auto &p : path[now.first]) {
      if (dis[p.v] > dis[now.first] + p.l) {
        dis[p.v] = dis[now.first] + p.l;
        q.push({p.v, dis[p.v]});
      }
    }
  }
  return dis[(1 << (n + 1)) - 1] == 0x3f3f3f3f ? 0 : dis[(1 << (n + 1)) - 1];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  FOR(i, 0, m) {//記錄cp關係
    int u, v;
    cin >> u >> v;
    against[pos++] = make_pair(u, v);
  }
  pos = 0;
  int Max = (1 << (n + 1)) - 1;
  FOR(i, 0, 1 << (n + 1))
  if (judge_p(i) && judge_p(Max - i)) point[pos++] = i;//必須兩邊都ok,纔可以
  int tmp;
  FOR(i, 0, pos)
    FOR(j, i, pos)
      if ((tmp = judge_e(point[i], point[j]))) addedge(point[i], point[j], tmp);//遍歷點的所有組合,判斷並添加邊
  if ((tmp = dijkstra()))//跑最短路,到不了就輸出"mole"
    cout << tmp;
  else
    cout << "mole";
}

O

這題是在三維空間上面取一棵生成樹,求這棵樹的$\frac{\sum h}{\sum d}$的最小值。我們假設這個值爲ans,則${\sum h}\geq ans\sum d$,記最小生成樹上的邊集合爲$A$,則$\sum (e.h-ans \cdot e.d)=0,e\in A$。當ans過大時,$\sum (e.h-ans \cdot e.d) < 0,e\in A$,過小則反之。這樣一來,我們就可以用二分套最小生成樹來求解。最小生成樹部分用prim跑得飛快,用kruskal要慢一些,注意常數別太差還是能過。複雜度$O(Alognz)$,$A$爲最小生成樹的複雜度

代碼及註釋:(kruskal)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int fa[1001], depth[1001];
int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
  u = find(u), v = find(v);
  if (depth[u] > depth[v])
    fa[v] = u;
  else {
    fa[u] = v;
    if (depth[v] == depth[u]) ++depth[v];
  }
}
struct E {
  int u, v;
  double w;
  inline bool operator<(E x) const { return w < x.w; }
};
struct P {
  int x, y, z;
};
P points[1001];
E edge[500001];
int pos = 0;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  FOR(i, 0, n) cin >> points[i].x >> points[i].y >> points[i].z;
  double sum, ans = 10000000;
  bool a = 0;
  double tmp[2] = {0, 10000000};//中間開始二分
  do {
    ans = (tmp[0] + tmp[1]) / 2;
    pos = sum = 0;
    FOR(i, 0, n)
      FOR(j, i + 1, n)
        edge[pos++] = {i, j,
                   abs(points[i].z - points[j].z) -
                       ans * sqrt(((ll)points[i].x - points[j].x) *
                                      (points[i].x - points[j].x) +
                                  ((ll)points[i].y - points[j].y) *
                                      (points[i].y - points[j].y))};
    for (int i = 0; i < n; ++i) fa[i] = i;//每次要重新加邊
    RST(depth);
    int i = 0;
    sort(edge, edge + pos);
    for (auto &p : edge)
      if (i == n - 1)
        break;
      else if (find(p.u) == find(p.v))
        continue;
      else {
        ++i;
        sum += p.w;
        connect(p.u, p.v);
      }
    tmp[sum < 0] = ans;
  } while (abs(tmp[0] - tmp[1]) >= 0.0001);//精度1e-4
  cout << fixed << setprecision(3) << ans;
}
0%