SPFA

AcWing 3305. 作物杂交（每日一题）

思路：

一个种子通过杂交获得，当且仅当前驱种子都存在，并且最短时间为前驱种子获得的时间的最大值加上最大的成熟种子的时间，所以可以看作是一个求最短路的问题。因为是由两个种子杂交获得一个种子，抽象为图的时候可以看作是两个节点指向同一条节点，要加两条有向边，定义邻接表的时候同时还要存储辅助的种子信息。最后用 spfaspfaspfa 或者 dijkstradijkstradijkstra 都可以求解。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;/*** @Description* @Author: PrinceHan* @CreateTime: 2023/3/6 7:52*/
public class Main {static final int N = 2005, M =200010, inf = 0x3f3f3f3f;static int[] d = new int[N];static int[] q = new int[M];static int[] st = new int[N];static int n, m, k, T, idx;// 存储杂交信息static int[] h = new int[N];static int[] e = new int[M];static int[] ne = new int[M];// 配种static int[] p = new int[M];static int[] w = new int[M];// 存储成熟时间static int[] g = new int[N];static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static int nextInt() throws IOException {in.nextToken();return (int)in.nval;}public static void add(int a, int b, int c) {e[idx] = c;p[idx] = b;w[idx] = Math.max(g[a], g[b]);ne[idx] = h[a];h[a] = idx++;}public static int spfa() {int hh = 0, tt = -1;for (int i = 1; i <= n; i++) {if (d[i] == 0) {q[++tt] = i;st[i] = 1;}}while (hh <= tt) {int u = q[hh++];st[u] = 0;for (int i = h[u]; ~i != 0; i = ne[i]) {int j = e[i];if (d[j] > Math.max(d[u], d[p[i]]) + w[i]) {d[j] = Math.max(d[u], d[p[i]]) + w[i];if (st[j] == 0) {q[++tt] = j;st[j] = 1;}}}}return d[T];}public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();k = nextInt();T = nextInt();Arrays.fill(d, inf);Arrays.fill(h, -1);for (int i = 1; i <= n; i++) {g[i] = nextInt();}while (m-- != 0) {int ti = nextInt();d[ti] = 0;}for (int i = 1; i <= k; i++) {int a = nextInt();int b = nextInt();int c = nextInt();add(a, b, c);add(b, a, c);}out.println(spfa());out.flush();}
}

Floyd

AcWing 4074. 铁路与公路（每日一题）

思路：

根据情况分别计算公路和铁路的最短路，可以使用 FloydFloydFloyd 、spfaspfaspfa 、DijkstraDijkstraDijkstra 进行求解。

FloydFloydFloyd：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;/*** @Description* @Author: PrinceHan* @CreateTime: 2023/3/7 8:56*/
public class Main {static final int N = 410, inf = 0x3f3f3f3f;static int[][] t = new int[N][N];static int[][] g = new int[N][N];static int n, m;static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();for (int[] ints : t) Arrays.fill(ints, 0x3f3f3f3f);for (int[] ints : g) Arrays.fill(ints, 1);for (int i = 1; i <= n; i++) {t[i][i] = 0;g[i][i] = 0;}while (m-- != 0) {int u = nextInt();int v = nextInt();t[u][v] = t[v][u] = 1;g[u][v] = g[v][u] = inf;}for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {t[i][j] = min(t[i][j], t[i][k] + t[k][j]);g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}}}int res = Math.max(t[1][n], g[1][n]);if (res == inf) out.println("-1");else out.println(res);out.flush();}}

spfaspfaspfa:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;/*** @Description* @Author: PrinceHan* @CreateTime: 2023/3/7 8:56*/
public class Main {static final int N = 410, M = 2 * N * N, inf = 0x3f3f3f3f;static int[][] g = new int[N][N];static boolean[] st = new boolean[N];static int[] h1 = new int[N], h2 = new int[N];static int[] e = new int[M], ne = new int[M];static int[] d = new int[N];static int n, m, idx;static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}public static void add(int[] h, int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}public static int spfa(int[] h, int f) {// 1-n的铁路                       1-n的公路if ((g[1][n] == 1 && f == 0) || (g[1][n] == 0 && f == 1)) return 1;Arrays.fill(d, inf);d[1] = 0;int[] q = new int[N * N];int hh = 0, tt = -1;q[++tt] = 1;st[1] = true;while (hh <= tt) {int t = q[hh++];st[t] = false;for (int i = h[t]; ~i != 0; i = ne[i]) {int j = e[i];if (d[j] > d[t] + 1) {d[j] = d[t] + 1;if (!st[j]) {q[++tt] = j;st[j] = true;}}}}return d[n];}public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();Arrays.fill(h1, -1);Arrays.fill(h2, -1);while (m-- != 0) {int a = nextInt();int b = nextInt();g[a][b] = g[b][a] = 1;add(h1, a, b);add(h1, b, a);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {if (g[i][j] == 0) {add(h2, i, j);add(h2, j, i);}}}int res = Math.max(spfa(h1, 0), spfa(h2, 1));if (res == inf) res = -1;out.println(res);out.flush();}}

最小生成树

AcWing 3728. 城市通电（每日一题）

思路：

本题是一个超级源点加最小生成树的综合题目。两城市之间的距离取得是曼哈顿距离，两城市之间的费用是曼哈顿距离与修建费用的乘积，由于数据范围比较大，可能会爆 intintint，因此要用 longlonglong 来存（javajavajava中）。

把 000 号城市作为超级源点，连接所有城市，更新所有城市的费用为新建发电站的费用。接着用 primprimprim 或者 kruskalkruskalkruskal 来计算最小生成树的长度。在计算过程中更新前驱节点，如果前驱节点是超级源点的话，则表示该点要建立发电站，否则这两点间连一条边。primprimprim 的时间复杂度要优于 kruskalkruskalkruskal 。

代码：

prim：prim：prim：

#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair PII;
#define x first
#define y secondconst int N = 2010, inf = 0x3f3f3f3f;
vector sta;
vector edges;
PII loc[N];
int pre[N];
int c[N], k[N];
LL d[N];
bool st[N];
int n;LL get_dist(int a, int b)
{LL d = (LL)(abs(loc[a].x - loc[b]. x) + abs(loc[a].y - loc[b]. y));return  d * (k[a] + k[b]);
}LL prim()
{LL res = 0;memset(d, 0x3f, sizeof d);d[0] = 0;st[0] = true;for (int i = 1; i <= n; i++) d[i] = c[i];for (int i = 0; i < n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ ){if (!st[j] && (t == -1 || d[t] > d[j])) t = j;}st[t] = true;res += d[t];if (!pre[t]) sta.push_back(t);else edges.push_back({pre[t], t});for (int j = 1; j <= n; j ++ ){if (d[j] > get_dist(t, j)){d[j] = get_dist(t, j);pre[j] = t;}}}return res;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ )scanf("%d%d", &loc[i].x, &loc[i].y);for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);for (int i = 1; i <= n; i ++ ) scanf("%d", &k[i]);LL res = prim();printf("%lld\n", res);printf("%d\n", sta.size());for (int s : sta) printf("%d ", s);puts("");printf("%d\n", edges.size());for (auto t : edges) printf("%d %d\n", t.x, t.y);return 0;
}

kruskal:kruskal:kruskal:

#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
typedef long long LL;
#define x first
#define y secondconst int N = 2010;vector sta;
vector lines;
struct Edge
{int a, b;LL w;bool operator< (const Edge &edge) const{return w < edge.w;}
} edges[N * N];
int c[N], k[N], p[N], x[N], y[N];
int n, cnt;int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d%d", &x[i], &y[i]);for (int i = 1; i <= n; i++){scanf("%d", &c[i]);edges[cnt++] = {0, i, c[i]};}for (int i = 1; i <= n; i++) scanf("%d", &k[i]);for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++){int d = abs(x[i] - x[j]) + abs(y[i] - y[j]);int val = k[i] + k[j];edges[cnt++] = {i, j, (LL) d * val};}sort(edges, edges + cnt);for (int i = 0; i <= n; i++) p[i] = i;LL res = 0;for (int i = 0; i < cnt; i++){Edge t = edges[i];int a = t.a, b = t.b;int fa = find(a), fb = find(b);if (fa != fb){p[fa] = fb;res += t.w;if (!a) sta.push_back(b);else lines.push_back({a, b});}}printf("%lld\n", res);printf("%d\n", sta.size());for (int a : sta) printf("%d ", a);puts("");printf("%d\n", lines.size());for (PII t : lines) printf("%d %d\n", t.x, t.y);return 0;
}

最近公共祖先

AcWing 3555. 二叉树（每日一题）

思路：

本题数据范围比较小，用 spfaspfaspfa 当作求最短路的范围也能做，但是一旦数据范围比较大就有可能会超时。

求 LCALCALCA （最近公共祖先） 可以用倍增或者爬山法，时间复杂度分别为 O(logN)O(logN)O(logN)、O(N)O(N)O(N)。本题主要用倍增法求解。

倍增法求 LCALCALCA 问题，首先先将两个节点移动到同一层，再往上查找父节点，一直到祖先的下一层。这样就找到了祖先。两节点之间的路径长等于两节点的深度之和减去祖先深度之和的二倍。

代码：

#include 
#include 
#include 
using namespace std;const int N = 1010, M = 2 * N;
int h[N], e[M], ne[M], idx;
// fa[i][k] 表示从节点i开始，向上跳2^k步到达的节点编号
int fa[N][10], depth[N];
int q[N];
int n, m;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void bfs()
{memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;int hh = 0, tt = -1;q[++tt] = 1;while (hh <= tt){int t = q[hh++];for (int i = h[t]; ~i; i = ne[i]){int j = e[i];if (depth[j] > depth[t] + 1){depth[j] = depth[t] + 1;q[++tt] = j;fa[j][0] = t;for (int k = 1; k <= 9; k++)fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}
}int lca(int a, int b)
{// 从较深的节点开始查找if (depth[a] < depth[b]) swap(a, b);// 先将两个节点跳到同一层for (int k = 9; k >= 0; k--){// 如果跳过了根节点 深度为 则不会执行下面的语句if (depth[fa[a][k]] >= depth[b])a = fa[a][k];}// 同一层只有一个，找到了最近公共祖先if (a == b) return a;// 跳到公共祖先的下一层for (int k = 9; k >= 0; k--){if (fa[a][k] != fa[b][k]){a = fa[a][k];b = fa[b][k];}}return fa[a][0];
}int main()
{int t;scanf("%d", &t);while (t -- ){memset(h, -1, sizeof h);idx = 0;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ){int a, b;scanf("%d%d", &a, &b);if (a != -1) add(i, a), add(a, i);if (b != -1) add(i, b), add(b, i);}bfs();while (m -- ){int a, b;scanf("%d%d", &a, &b);int p = lca(a, b);printf("%d\n", depth[a] + depth[b] - 2 * depth[p]);}}return 0;
}

二分图

AcWing 1394. 完美牛棚（每日一题）

思路：

求二分图的最大匹配问题主要用到匈牙利算法。可以先用邻接表构建无向图。开一个数组用来记录每个单间匹配的奶牛。尝试某种匹配，如果当前单间没有匹配 或者匹配的奶牛可以匹配其他单间，则将该单间匹配当前的奶牛。然后模拟 nnn 次匹配，匹配成功一次答案就加1。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;/*** @Description* @Author: PrinceHan* @CreateTime: 2023/3/9 22:21*/
public class Main {// M要开大一点 max(si) * M 一个坑static final int N = 210, M = N * N;static int[] h = new int[N];static int[] e = new int[M];static int[] ne = new int[M];// match[i]表示第i个单间匹配了哪头奶牛static int[] match = new int[N];static boolean[] st = new boolean[N];static int n, m, idx;static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}public static void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}public static boolean find(int u) {for (int i = h[u]; ~i != 0; i = ne[i]) {int j = e[i];if (!st[j]) {st[j] = true;// 没有匹配 或者匹配了奶牛可以匹配其他单间if (match[j] == 0 || find(match[j])) {match[j] = u;return true;}}}return false;}public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();Arrays.fill(h, -1);for (int i = 1; i <= n; i++) {int s = nextInt();while (s-- != 0) {int x = nextInt();add(i, x);}}int res = 0;for (int i = 1; i <= n; i++) {// 模拟每次匹配 因此每次都要初始化Arrays.fill(st, false);if (find(i)) res++;}out.println(res);out.flush();}
}