2019年电子科技大学ACM暑期前集训图论专题解题报告

这题要求调整部分边的方向，把有环的有向图中部分边反向，使其变成无环图，我们要求的是调整的边的最大权值最小的方案。首先我们要知道一个原理，如果无环图加入$A \to B$会使其变为有环图，那么$B\to A$一定是连通的，那么加入边$B\to A$不会使其成环。那么，我们删掉某些边得到无环图之后，必然可以加回来得到无环图。而如果我们删除权值不大于ans的所有边，我们可以很快地算出是否有环。如果有环，则ans一定小于答案，如果无环，则ans不小于答案。根据这一性质，我们可以二分套判环解决，判环使用拓扑方法，复杂度为$O((m+n)logM)M$可以是最大边权，也可以是边权的中位数（$O(n)$找中位数要多写不少代码，并且这题不必要）

#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;
}

这题是求免费一条边的最小生成树权值和，以及要使权值和等于该值的情况下，可以选择的免费边的数量。首先，最小生成树的算法这里不再累述，kruskal算法即可。然后根据贪心的思想易知第一个问题的答案为最小生成树总权值-最小生成树上最大边权值。然后难点就在于第二个问题。树上权值最大的边（可能有多条相等）如果能被另一条边替代，那么替代后免费新的边，也能得到相同的结果。所以我们要找到可以替换树上最大边的边。我们可以把最大边去掉（第一次并查集记录最大边条数，第二次并查集参考G题），这样树就出现了中断，然后我们需要寻找能够把中断补上的边。我们沿用kruskal算法的并查集，即可轻松判断一条边是否能补上中断。遍历一遍边即可，由最小生成树的性质，小边不可能替代大边，所以权值小于树上最大边的边可以直接略过。

最大部分的时间复杂度就是kruskal的时间复杂度，即$O(mlogm+mA(n)+n)$，其实复杂度最大的地方就是排序边的O(mlogm)

代码及注释：

#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;
}

该题判断是否有欧拉路径，然后输出字典序最小的欧拉路径。判断欧拉路径根据出入度，所有点入度等于出度则有欧拉回路，入度比出度大一的点和出度比入度大一的点各一个（必须两者都有一个）则有欧拉路径（非回路）。然后是输出部分，如果是回路，要从有路的最小点作为起点。然后可以用一个dfs，从小的边开始搜，回溯的时候即可得到反向的欧拉路径，再反向输出即可。由于路径可能很长，搜索深度可能很深，dfs递归会发生栈溢出，可以加inline内联交给GNU的强大力量去解决（这样写甚至跑起来更快），也可以写非递归版的dfs（码量稍大）。复杂度$O(m)$

代码及注释：

#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!";
}

这题要求的是在一个有向，可能有环的正点权图上获取最大值。如果它是无环的，那么以终点的权作为边权求最长路即可（无环图不会到达一个点多次），因此，我们就考虑怎么处理环。这样就引入了缩点的概念(据说暴力也可以过?)，为了获取最大权，进入环中一个点后必然会把整个环吃完，然后从中选择合适的点出环。根据这一性质，我们可以找到图中的环（不一定是单层的环，标准的名称为强联通分量），把每一个环缩成一个点，权值为各点权值之和，环内点与环外点的路径都加在缩成的点上。实现的方法有Kosaraju、Tarjan（没错，又是这位图灵奖巨佬）等。本题以Kosaraju为例，从起点开始进行一次dfs，回溯时按顺序记录点，再在反向图上，按之前的记录逆序一次dfs，在第i次反向dfs中初次找到的点（当然，正向dfs中不可达的点要排除）就构成了第i个强联通分量。然后建立新图，按一开始说的无环图做法即可，正权图最长路相当于负权图最短路，使用spfa算法求解。Kosaraju的复杂度通常为$O(n+m)$，时间瓶颈在于spfa，复杂度最坏可达$O(mn)$

代码及注释：

#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;
}

这是本次的签到题，解题方法是根据贪心的思想，按权值从小到大取边，同时采用并查集判断边是否可取，这种算法被称为 kruskal算法，复杂度为$O(mlogm+mA(n)+n)$，瓶颈是边排序的$O(mlogm)$

代码：

#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;
}

这题的思路没有什么好说的，很明显的网络流板题。下面简单说一下网络流（以后有时间可能会单独写一篇博客，也很可能会鸽）

网络流是一个有若干条带权（容量）边组成的，固定源点和汇点的有向图。本题要解决的是，从源点产生的流（本题中水流是个很形象的例子），经过各边汇集到汇点，这样的流的最大流量。显然，对于每个点，流入流出的量相等，总流量守恒；同时，每条边上的流量均不能超过该条边的容量。在思考怎么求出最大流的过程中，我们要了解一个非常重要的定理──增广路定理。当我们找到网络流中一条从源点到汇点的通路时，可以把这条通路的各段边的容量减少一个值 $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)$（较松，还能加优化），具体实现如下（注意有注释的地方）

#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;
}

这是一道很裸的有向图（无向图拆边，然后做法也一样）K短路问题，我们可以采用一个方向最短路算法初始化（dijkstra，spfa什么的都可以，时间很松），一个方向A*启发式搜索（这类题是$h(x)=h*(x)$的特例）的方法解题。最短路算法不再多说，对于A*算法，我们用一个优先队列，从起点开始，每次扩展其直接可达的边入队，这样的过程中，跑出i次第i短路时，它可以扩展出i+1次第i+1短路，由此，当某条边出队K次时可以终止，此时的路径长度就是第k短路的长度。复杂度（貌似）$O(kmlogm)$

代码及注释

#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;//跑完之后仍找不到，则说明没有
}

这道题目给了我们一个二分图，然后希望求一个最小的点的数量，来覆盖这一个二分图的所有边。我们求出最大匹配，在每个匹配的其中一个点上放置一个点即可覆盖，因此该题实际上是求最大匹配数，我们把二分图各边的容量设为1，然后加入源点s并依次连至左边的元素，右边的元素依次连至汇点t，该问题便转化为了一个网络流问题，而且是单位容量的简单网络流。对于这种特殊情况的网络流，可使用Hopcroft算法达到$O(m\sqrt n)$的复杂度，使用常规的dinic算法也可以平稳通过。以下代码为dinic算法（具体做法见H题）

代码及注释：

#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条边的最短路。我们的一个容易想到的直观的思路是做分层图，把已经免费的次数作为一个维度建图，但是如果完整的建完整张图，会导致内存超出，而分层图中存在大量的重复边，可以都从第一层取边，然后再加上跨层的边。但我觉得这题更好的思路是，最短路算法本质上是一个一维状态的动态规划（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优化貌似对这种情况效果比较好。

#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();
}

这题有些复杂，购买物品需要花费，购买某个集合的所有物品可获得相应的奖励，答案要求是两者差最大，而不是限制最大花费。这样看起来比动态规划中01背包问题复杂得多。这种问题称为最大权闭合子图问题，我们从源点连接所有的物品，所有集合连向汇点，容量均取正。然后根据包含关系，用无限容量的边连接物品和集合。这样一来，就可以用割去某个物品到源点的边模拟购买此物品，某个集合被买完之后其到终点的流被切断。这样一来我们求一个割，即使得所有的边都被割断，所花费的最小代价，这样对于每个集合，要么获得并且花费了相应的代价，要么放弃了该集合。所有集合的总的压岁钱数量减去此时的割，就是他可以剩下的压岁钱。我们要求最大的剩余压岁钱，就要求最小割。显然，我们按照最大流的路径去割是最佳方案，这样最小割就等于最大流（最大流做法见H题）。复杂度$O((n+m)^2\sum k)$

代码及注释

#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;//输出结果
}

这题是一道差分约束，某两个量存在一个大于关系，可以用一条权值为1（它们至少相差1）的有向边连接（小于则相反），等于就是权值为0的双向边，这样，然后从源点向每条边添加权值为最小值1的边，这样源点到每个点的最长路长度就是它的最小值，题目要求输出的就是这些值的和。如果有环就说明存在矛盾。带判环的spfa可以用来解决这个问题。复杂度$O(nm)$

#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;
}

这题，最少花费，可以让人联想到图上面的最短路，而问题的关键就是怎么建图，即找到满足要求的点（状态）和转移路径。状态的描述方式为二进制（参考状压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)的数据可以卡掉（如有错误请指正）

代码及注释

#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";
}

这题是在三维空间上面取一棵生成树，求这棵树的$\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）

#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;
}

推荐订阅源

Howard Cheung