2018.11.25。
A – HDU 1520
简单树形DP。
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 6000 + 5; struct node { LL id, cost; node(LL id_ = 0, LL cost_ = 0) : id(id_), cost(cost_) {} }; LL n, dp[maxn][2], a[maxn], in[maxn], vis[maxn]; vector <node> g[maxn]; void init() { memset(dp, 0, sizeof dp); memset(a, 0, sizeof a); memset(in, 0, sizeof in); memset(vis, 0, sizeof vis); for (LL i = 0; i < maxn; ++i) g[i].clear(); } void dfs(LL now) { vis[now] = 1; unsigned sz = g[now].size(); for (unsigned i = 0; i < sz; ++i) { if (!vis[g[now][i].id]) { dfs(g[now][i].id); dp[now][1] += dp[g[now][i].id][0]; dp[now][0] += max(dp[g[now][i].id][0], dp[g[now][i].id][1]); } } } int main() { ios::sync_with_stdio(false); while (cin >> n) { init(); for (LL i = 1; i <= n; ++i) { cin >> a[i]; } LL tl, tk, es; for (LL i = 1; i <= n - 1; ++i) { cin >> tl >> tk; ++in[tl]; g[tk].push_back(node(tl, a[tl])); } cin >> es >> es; for (LL i = 1; i <= n; ++i) { dp[i][0] = 0; dp[i][1] = a[i]; } for (LL i = 1; i <= n; ++i) { if (in[i] == 0) { dfs(i); cout << max(dp[i][0], dp[i][1]) << endl; } } } return 0; } |
B – POJ – 2631
树的直径裸题。
|
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 |
#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const LL maxn = 10000 + 5; struct edge { LL from, to, cost; edge(LL from = 0, LL to = 0, LL cost = 0) : from(from), to(to), cost(cost) {} }; vector <edge> g[maxn]; bool vis[maxn]; LL max_far = -1, max_node = -1; void dfs(LL now, LL far) { vis[now] = 1; if (far > max_far) { max_far = far; max_node = now; } unsigned sz = g[now].size(); for (unsigned i = 0; i < sz; ++i) { if (!vis[g[now][i].to]) { dfs(g[now][i].to, far + g[now][i].cost); } } vis[now] = 0; } int main() { ios::sync_with_stdio(false); LL u, v, w; while (cin >> u >> v >> w) { g[u].push_back(edge(u, v, w)); g[v].push_back(edge(v, u, w)); } memset(vis, 0, sizeof vis); dfs(1, 0); memset(vis, 0, sizeof vis); max_far = -1; dfs(max_node, 0); cout << max_far << endl; return 0; } |
C – CodeForces – 475B
Tarjan/Kosaraju裸题。（貌似贪心就能过）
|
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 |
#include <bits/stdc++.h> using namespace std; int n, m; string row, col; int low[400 + 1], dfn[400 + 1], belong[400 + 1], num[400 + 1], idx, cnt; bool inStk[400 + 1]; stack <int> stk; inline int get_x(int val) { return val / m; } inline int get_y(int val) { return val % m; } inline int get_val(int tx, int ty) { return tx * m + ty; } inline vector<int> get_adj(int tx, int ty) { vector <int> ret; if (row[tx] == '<' && ty - 1 >= 0) ret.push_back(get_val(tx, ty - 1)); if (row[tx] == '>' && ty + 1 < m) ret.push_back(get_val(tx, ty + 1)); if (col[ty] == '^' && tx - 1 >= 0) ret.push_back(get_val(tx - 1, ty)); if (col[ty] == 'v' && tx + 1 < n) ret.push_back(get_val(tx + 1, ty)); return ret; } void tarjan(int u) { low[u] = dfn[u] = ++idx; stk.push(u); inStk[u] = true; int tx = get_x(u), ty = get_y(u); vector <int> g = vector <int>(get_adj(tx, ty)); for (auto const &v: g) { if (!dfn[v]) { tarjan(v); if (low[u] > low[v]) low[u] = low[v]; } else if (inStk[v] && low[u] > dfn[v]) { low[u] = dfn[v]; } } int v; if (low[u] == dfn[u]) { ++cnt; do { v = stk.top(); stk.pop(); inStk[v] = false; belong[v] = cnt; ++num[cnt]; } while (v != u); } } int main() { ios::sync_with_stdio(false); cin >> n >> m; cin >> row >> col; for (int i = 0; i <= n * m - 1; ++i) { if (!dfn[i]) tarjan(i); } if (cnt == 1) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; } |
D – BZOJ – 1016
详见：最小生成树计数
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; void getInt(LL &x) { x = 0; char ch = getchar(); LL sgn = 1; while (ch < '0' || ch > '9') { if (ch == '-') sgn = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } x *= sgn; } void getInt(LL &x, LL &y) { getInt(x); getInt(y); } void getInt(LL &x, LL &y, LL &z) { getInt(x); getInt(y); getInt(z); } const LL maxn = 100 + 5, maxm = 1000 + 5; const LL modp = 31011; LL n, m; struct Edge { LL u, v, w; Edge(LL tu = 0, LL tv = 0, LL tw = 0) : u(tu), v(tv), w(tw) {} friend bool operator < (const Edge &ex, const Edge &ey) { return ex.w < ey.w; } } e[maxm]; struct DisjointSet { LL fa[maxn]; void init(LL n) { for (LL i = 0; i <= n; ++i) fa[i] = i; } LL find(LL u) { return fa[u] == u ? u : fa[u] = find(fa[u]); } void merge(LL u, LL v) { fa[find(u)] = find(v); } bool same(LL u, LL v) { return find(u) == find(v); } } sa, sb; void dfs(LL l, LL r, LL res, LL &ret) { #ifdef DEBUG printf("call dfs(l = %lld, r = %lld, res = %lld, ret = %lld)\n", l, r, res, ret); #endif if (l > r) { if (res == 0) ++ret; return; } if (!sb.same(e[l].u, e[l].v)) { DisjointSet tmp = sb; sb.merge(e[l].u, e[l].v); dfs(l + 1, r, res - 1, ret); sb = tmp; } dfs(l + 1, r, res, ret); } int main() { getInt(n, m); for (LL i = 1; i <= m; ++i) { getInt(e[i].u, e[i].v, e[i].w); } sa.init(n), sb.init(n); sort(e + 1, e + m + 1); LL p = 1, cnt = 0, cur = 0, ans = 1, tot = 0, val = 0; for (LL i = 1; i <= m + 1; ++i) { if (e[i].w != e[i - 1].w) { cur = 0; dfs(p, i - 1, cnt, cur); ans = ans * cur % modp; p = i; sb = sa; cnt = 0; } if (!sa.same(e[i].u, e[i].v)) { sa.merge(e[i].u, e[i].v); val += e[i].w; ++cnt; ++tot; } } if (tot == n - 1) printf("%lld\n", ans); else puts("0"); return 0; } |
E – HDU – 1874
最短路裸题。
|
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 |
#include <iostream> using namespace std; const int sup = 200 + 1; int n, m, g[sup][sup], u, v, w, s, t; int main() { while (cin >> n >> m) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { g[i][j] = (i == j) ? 0 : 1E9; } } for (int i = 1; i <= m; ++i) { cin >> u >> v >> w; g[u][v] = min(g[u][v], w); g[v][u] = min(g[v][u], w); } cin >> s >> t; for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j <n; ++j) { g[i][j] = min(g[i][j], g[i][k] + g[k][j]); } } } if (g[s][t] == 1E9) cout << "-1" << endl; else cout << g[s][t] << endl; } return 0; } |
F – UVA – 315
Tarjan算法求割点：根节点有两个或者两个以上子节点为割点，非根节点满足$low(v) \geq dfn(u)$则u为割点。
|
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; typedef long long LL; const LL maxn = 100 + 10; LL n; vector <LL> g[maxn]; LL pre[maxn], low[maxn], iscut[maxn], allocId, ans; LL tarjan(LL u, LL fa) { LL lowu = pre[u] = ++allocId; LL child = 0; for (auto v: g[u]) { if (!pre[v]) { ++child; LL lowv = tarjan(v, u); lowu = min(lowu, lowv); if (lowv >= pre[u]) iscut[u] = 1; } else if (pre[v] < pre[u] && v != fa) { lowu = min(lowu, pre[v]); } } if (fa < 0 && child == 1) iscut[u] = 0; low[u] = lowu; return lowu; } void init() { for (LL i = 0; i <= maxn; ++i) g[i].clear(); memset(pre, 0, sizeof pre); memset(low, 0, sizeof low); memset(iscut, 0, sizeof iscut); allocId = 0; ans = 0; } int main() { while (scanf("%lld", &n) && (n != 0)) { init(); LL head, to; char ch; while (scanf("%lld", &head) && (head != 0)) { while (scanf("%lld%c", &to, &ch)) { g[head].push_back(to); g[to].push_back(head); if (ch == '\n') break; } } for (LL i = 1; i <= n; ++i) { if (!pre[i]) tarjan(i, -1); } for (LL i = 1; i <= n; ++i) { if (iscut[i]) ++ans; } printf("%lld\n", ans); } return 0; } |
说点什么