T1
洛谷 P2047 社交网络
暴力 Floyd 跑出每两个点间最短路及其条数，然后暴力枚举算。
代码
#include <iostream>
#include <string.h>
#include <iomanip>
#include <queue>
#define int long long
using namespace std;
int n, m;
int dist[105][105];
int cnt[105][105];
signed main() {
cin >> n >> m;
memset(dist, 63, sizeof dist);
for (int i = 1; i <= m; i++) {
int u, v, ww;
cin >> u >> v >> ww;
dist[u][v] = min(dist[u][v], ww);
dist[v][u] = dist[u][v];
cnt[u][v] = cnt[v][u] = 1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
cnt[i][j] = cnt[i][k] * cnt[k][j];
} else if (dist[i][k] + dist[k][j] == dist[i][j])
cnt[i][j] += cnt[i][k] * cnt[k][j];
}
}
}
for (int i = 1; i <= n; i++) {
double ans = 0;
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (i == j || i == k || j == k)
continue;
if (dist[j][i] + dist[i][k] == dist[j][k])
ans += 1.0 * cnt[j][i] * cnt[i][k] / cnt[j][k];
}
}
cout << fixed << setprecision(3) << ans << "\n";
}
return 0;
}
T2
洛谷 P4189 星际旅行
首先题目保证每个点的值大于等于其度数，所以可以先把每个点遍历一遍。接下来如果有一条边两边的点剩下的都大于 \(0\)，那就可以在走到这两个点时在这两点间反复横跳来把其中一个消耗成 \(0\)。这样可以求得根的答案。接下来考虑往下推。假设我们已经知道了这个点的答案，要求其中一个儿子的答案。这个时候分类讨论。
-
当前点有剩余。直接走，儿子答案为当前点答案加 \(1\)。
-
当前点无剩余，但是儿子有至少一个儿子还有剩余。那就把从儿子上来的一条流退掉，换成从儿子到儿子的儿子再回儿子的一条流。这样儿子答案是当前点答案 \(+1\)，儿子的儿子剩余值 \(-1\)。
-
否则退掉从儿子上来的一条流，答案为当前点答案 \(-1\)，儿子剩余值 \(+1\)。
直接搞就行了。回溯时要记得把所有对剩余值的更改清掉。
代码
#include <iostream>
using namespace std;
int n;
int h[50005];
int deg[50005];
int head[50005], nxt[100005], to[100005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, deg[v]++; }
int f[50005];
int ans[50005];
int p[50005];
int cur;
void dfs1(int x, int fa) {
f[x] = fa;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs1(v, x);
int tmp = min(h[x], h[v]);
ans[1] += tmp * 2;
h[x] -= tmp;
h[v] -= tmp;
if (h[v])
p[x] = v;
}
}
}
void dfs2(int x) {
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != f[x]) {
if (h[x]) {
ans[v] = ans[x] + 1, --h[x];
dfs2(v);
++h[x];
} else if (p[v]) {
ans[v] = ans[x] + 1, h[p[v]]--;
dfs2(v);
h[p[v]]++;
} else {
ans[v] = ans[x] - 1, h[v]++;
dfs2(v);
h[v]--;
}
}
}
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
++u, ++v;
add(u, v);
add(v, u);
ans[1] += 2;
h[u]--, h[v]--;
}
dfs1(1, 0);
dfs2(1);
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
return 0;
}
T3
洛谷 P1963 变换序列
把一个点向能变到的点连边，构成一张二分图。则问题变为求一张二分图的字典序最小的完美匹配，且每个左部点的度数都为 \(2\)。使用匈牙利算法，倒着枚举每个点，对于每个点尽量选更小的匹配点。可以证明这样匹配出来就是字典序最小。
证明考虑先删去所有度数为 \(1\) 的右部点。设还剩 \(k\) 个右部点，则右部点总度数还剩 \(2n - 2(n - k) = 2k\)。而每个右部点的度数都大于等于 \(2\)，所以每个右部点的度数都只能为 \(2\)。又因为所有左部点度数也都为 \(2\)，所以每次换掉一个点的匹配时就只有一种剩下的情况。所以就能保证字典序最小。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
int n, S, T;
int d[10005];
vector<int> g[100005];
void add(int u, int v) {
g[u].emplace_back(v);
g[v].emplace_back(u);
}
int mat[2000005];
bool vis[2000005];
bool dfs(int x) {
if (vis[x])
return 0;
vis[x] = 1;
for (auto v : g[x]) {
if (!mat[v] || dfs(mat[v])) {
mat[v] = x;
mat[x] = v;
return 1;
}
}
return 0;
}
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n;
S = n * 2 + 1, T = S + 1;
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = n; i; i--) {
int x = ((i - 1 - d[i]) + n) % n + 1;
int y = (i - 1 + d[i]) % n + 1;
if (x < y)
swap(x, y);
add(i, x + n);
add(i, y + n);
}
for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
int x = 0;
for (int i = n; i; i--) {
memset(vis, 0, sizeof vis);
x += dfs(i);
}
if (x != n)
cout << "No Answer\n";
else {
for (int i = 1; i <= n; i++)
cout << mat[i] - n - 1 << " ";
}
return 0;
}
T4
洛谷 P1912 诗人小 G
首先有显然的状态与转移方程：\(dp[i] = \min\limits_{0 \le j < i} \{ dp[j] + |S[i] - S[j] + j - i - 1 - L|^p \}\)。可以发现这个转移具有决策单调性，所以利用决策单调性来优化 dp。
决策单调性优化 dp：
考虑每个点一开始的最优决策：\(\texttt{0000000}\)。在有了 \(dp[1]\) 之后，最优决策可能变成这样：\(\texttt{0001111}\)。然后可能是 \(\texttt{0001122}\)，\(\texttt{0001333}\)，以此类推。发现以每个决策为最优决策点的点是一段区间，所以我们用一个队列维护所有这样的区间，其中存若干三元组，分别表示某个决策的左右端点以及这个决策的位置。每次新加入一个决策 \(i\) 时，从右往左遍历这个队列。设队列最右侧的决策左端点为 \(l\)，决策点为 \(p\)，那如果 \(l\) 用 \(i\) 这个决策比 \(l\) 用 \(p\) 这个决策来的更优，那 \(p\) 这个决策就没有用了，可以直接扔掉。所以此时我们弹掉队列的右端点，直到 \(l\) 用 \(p\) 更优。此时由于 \(i\) 的加入，原本 \(p\) 的区间里可能出现一些用 \(i\) 更优的位置。这些位置一定是右边的一串，所以我们二分出第一个用 \(i\) 更优的位置 \(x\)，将 \(p\) 的区间的右端点设为 \(x - 1\)，然后加入新的决策 \(\{ x, n, i\}\)。然后我们再把队列最左边的决策的左端点设为 \(i + 1\)。这样每次算新的 dp 值时就把最左边的合法决策拿出来算一下就好了。记得扔掉左端点大于右端点的决策。
然后就是这个题 dp 要开 long double 存，不然要爆精度。
代码
#include <iostream>
#include <iomanip>
#include <math.h>
#define int long long
using namespace std;
const long long inf = 1000000000000000000ll;
int n, L, p;
inline long double qpow(long double x, int y) {
long double ret = 1;
while (y) {
if (y & 1)
ret = ret * x;
y >>= 1;
x = x * x;
}
return ret;
}
int S[100005];
long double dp[100005];
inline long double calc(int i, int j) { return dp[j] + qpow(abs(S[i] - S[j] + i - j - 1 - L), p); }
struct node {
int l, r, p;
} q[100005];
int ql, qr;
int Search(int ll, int rr, int x, int y) {
int l = ll, r = rr, mid, ans = rr + 1;
while (l <= r) {
mid = (l + r) >> 1;
if (calc(mid, x) <= calc(mid, y)) {
ans = mid, r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
string str[100005];
int f[100005];
int stk[100005], sz;
signed main() {
int tc;
cin >> tc;
while (tc--) {
cin >> n >> L >> p;
for (int i = 1; i <= n; i++) {
cin >> str[i];
S[i] = S[i - 1] + str[i].size();
}
ql = qr = 1;
q[qr] = (node) { 1, n, 0 };
for (int i = 1; i <= n; i++) {
while (q[ql].l > q[ql].r) ++ql;
dp[i] = calc(i, q[ql].p);
f[i] = q[ql].p;
while (q[qr].r < q[qr].l || (qr >= ql && calc(q[qr].l, i) <= calc(q[qr].l, q[qr].p))) --qr;
if (ql > qr)
q[++qr] = (node) { i, n, i };
else {
int x = Search(q[qr].l, q[qr].r, i, q[qr].p);
q[qr].r = x - 1;
q[++qr] = (node) { x, n, i };
}
q[ql].l = i + 1;
}
if (dp[n] > inf)
cout << "Too hard to arrange\n";
else {
cout << fixed << setprecision(0) << dp[n] << "\n";
sz = 0;
for (int i = n; i; i = f[i]) stk[++sz] = i;
stk[sz + 1] = 0;
for (int i = sz; i; i--) {
int p = stk[i + 1];
for (int j = p + 1; j <= stk[i]; j++) cout << str[j] << " \n"[j == stk[i]];
}
}
for (int i = 1; i <= 20; i++) cout << "-";
cout << "\n";
}
return 0;
}
T5
洛谷 P2805 植物大战僵尸
首先把所有植物向它所保护的植物连边，再向它左边的植物连边，表示要先吃掉这个植物才能吃掉那个。这样建出的图可能会存在环，而我们发现所有环能够到达的点都无法被吃掉。所以我们先拓扑一遍，能拓扑到的点都是无法被环所到达的。接下来我们把所有边反向，发现选了一个植物之后就要选所有其能够到达的。问题转化为求最大权闭合子图。
最大权闭合子图：
图中原有边容量为 \(+\infty\)，从源点向所有正权点连边，边权为该点的点权；从所有负权点向汇点连边，边权为该点点权的绝对值。然后求 所有正权点点权和 - 最小割 即为答案。首先所有原图中的边不会被割掉，所以所有被划到 \(S\) 集合的点能够到达的所有点一定也在 \(S\) 集合中。这样就保证了是闭合的。然后我们考虑一组割的意义。首先假设所有正权点都在 \(S\) 中。如果我们割掉一条正权点的边，那代表不把这个正权点划到闭合子图中，子图权值要减去其权值。如果我们割掉一条负权点的边，那代表把这个点划到闭合子图中，子图权值要加上其权值，也就是减去负的它的权值。这样我们求出最小割然后减一下就可以了。
代码
#include <iostream>
#include <vector>
#include <queue>
#define int long long
using namespace std;
const int inf = 2147483647;
int n, m, N;
int sc[605];
int in[605];
vector<int> g[605];
queue<int> q;
bool vis[605];
inline int f(int x, int y) { return (x - 1) * m + y; }
int pcnt[605];
int head[605], nxt[2000005], to[2000005], res[2000005], ecnt;
int cur[605];
void add(int u, int v, int ww) {
to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, res[ecnt] = ww;
to[++ecnt] = u, nxt[ecnt] = head[v], head[v] = ecnt, res[ecnt] = 0;
}
int S, T;
int dep[605];
bool bfs() {
q.push(S);
for (int i = 1; i <= T; i++) dep[i] = -1;
dep[S] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (res[i] && dep[v] == -1) {
dep[v] = dep[x] + 1;
q.push(v);
}
}
}
return (dep[T] != -1);
}
int dfs(int x, int flow) {
if (x == T)
return flow;
int ret = 0;
for (int i = cur[x]; i && flow; i = nxt[i]) {
cur[x] = i;
int v = to[i];
if (dep[v] == dep[x] + 1 && res[i]) {
int tmp = dfs(v, min(flow, res[i]));
if (tmp) {
res[i] -= tmp;
res[i ^ 1] += tmp;
flow -= tmp;
ret += tmp;
}
}
}
if (ret == 0)
dep[x] = -1;
return ret;
}
int dinic() {
int ret = 0;
while (bfs()) {
for (int i = 1; i <= T; i++) cur[i] = head[i];
ret += dfs(S, inf);
}
return ret;
}
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n >> m;
N = n * m;
S = N + 1, T = S + 1;
ecnt = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x = f(i, j);
cin >> sc[x];
cin >> pcnt[x];
for (int k = 1; k <= pcnt[x]; k++) {
int a, b;
cin >> a >> b;
++a, ++b;
g[x].emplace_back(f(a, b));
in[f(a, b)]++;
}
if (j ^ 1) {
g[x].emplace_back(f(i, j - 1));
in[f(i, j - 1)]++;
}
}
}
for (int i = 1; i <= N; i++) {
if (!in[i])
q.push(i);
}
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 1;
for (auto v : g[x]) {
in[v]--;
if (in[v] == 0)
q.push(v);
}
}
int s = 0;
for (int i = 1; i <= N; i++) {
if (!vis[i])
continue;
if (sc[i] < 0)
add(i, T, -sc[i]);
else
add(S, i, sc[i]), s += sc[i];
for (auto v : g[i]) {
if (vis[v])
add(v, i, inf);
}
}
cout << s - dinic() << "\n";
return 0;
}
T6
洛谷 P1758 管道取珠
由于是对平方求和，考虑变成两个人分别取，取出来的序列相同的方案数。这样就随便 dp 了。设 \(dp[i][j][k]\) 表示两个人目前都取了 \(i\) 个，一个人在第一管里取了 \(j\) 个，第二个在第一管里取了 \(k\) 个，目前取出来的序列相同的方案数。第一维滚动数组滚掉，然后转移随便搞搞就好。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#define int long long
using namespace std;
const int P = 1024523;
int n, m;
int dp[2][505][505];
string s, t;
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n >> m;
cin >> s >> t;
s = ' ' + s;
t = ' ' + t;
dp[0][0][0] = 1;
for (int i = 1; i <= n + m; i++) {
int x = (i & 1);
memset(dp[x], 0, sizeof dp[x]);
for (int j = max(0ll, i - m); j <= min(n, i); j++) {
for (int k = max(0ll, i - m); k <= min(n, i); k++) {
if (s[j] == s[k] && j && k)
dp[x][j][k] += dp[x ^ 1][j - 1][k - 1];
if (s[j] == t[i - k] && j && i - k)
dp[x][j][k] += dp[x ^ 1][j - 1][k];
if (t[i - j] == s[k] && i - j && k)
dp[x][j][k] += dp[x ^ 1][j][k - 1];
if (t[i - j] == t[i - k] && i - j && i - k)
dp[x][j][k] += dp[x ^ 1][j][k];
dp[x][j][k] %= P;
}
}
}
cout << dp[(n + m) & 1][n][n] << "\n";
return 0;
}
T7
洛谷 P2046 海拔
首先最终的答案一定是一堆海拔为 \(0\) 的构成且仅构成一个四连通块，一堆海拔为 \(1\) 的也构成且仅构成一个四连通块。因为如果有一个内部高度相等四连通块比与它四联通的所有点海拔都高，那一定可以把这整个四连通块的高度降低而使答案更优。这样就转化为一个最小割。然后又由于是平面图，我们使用平面图最小割等于对偶图最短路这个结论。也就是在源汇点间连边，构成一个附加面。然后构造出对偶图，但是不连附加面与开放面之间的边。然后我们跑出附加面对应的点到开放面对应的点之间的最短路即为最小割。证明考虑新图中一条路径就对应一组割，所以最短路就是最小割。画个图大概就能理解。
代码
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int S, T;
int head[250005], nxt[4000005], to[4000005], ew[4000005], ecnt;
void add(int u, int v, int ww) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, ew[ecnt] = ww; }
int dist[250005];
struct node {
int x, dis;
} tmp;
bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> q;
bool vis[250005];
void dijkstra() {
memset(dist, 63, sizeof dist);
q.push((node) { S, 0 });
dist[S] = 0;
while (!q.empty()) {
tmp = q.top();
q.pop();
int x = tmp.x;
if (vis[x])
continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dist[v] > dist[x] + ew[i]) {
dist[v] = dist[x] + ew[i];
q.push((node) { v, dist[v] });
}
}
}
}
int n;
inline int f(int x, int y) { return (x - 1) * n + y; }
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n;
S = n * n + 1, T = S + 1;
for (int i = 1; i <= n + 1; i++) {
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
if (i == 1)
add(f(1, j), T, x);
else if (i == n + 1)
add(S, f(n, j), x);
else
add(f(i, j), f(i - 1, j), x);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n + 1; j++) {
int x;
cin >> x;
if (j == 1)
add(S, f(i, 1), x);
else if (j == n + 1)
add(f(i, n), T, x);
else
add(f(i, j - 1), f(i, j), x);
}
}
for (int i = 1; i <= n + 1; i++) {
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
if (i == 1)
add(T, f(1, j), x);
else if (i == n + 1)
add(f(n, j), S, x);
else
add(f(i - 1, j), f(i, j), x);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n + 1; j++) {
int x;
cin >> x;
if (j == 1)
add(f(i, 1), S, x);
else if (j == n + 1)
add(T, f(i, n), x);
else
add(f(i, j), f(i, j - 1), x);
}
}
dijkstra();
cout << dist[T] << "\n";
return 0;
}