继续图论。
346. 走廊泼水节 - AcWing题库
Kruskal模板应用,先把每个点看作一个集合,然后从小到大枚举边,每次把两个集合合并时,两个集合互相连边直至成局部完全图即可
#includeusing namespace std; const int N = 6010; struct Edge { int a, b, w; bool operator< (const Edge &t) const { return w < t.w; } }e[N]; int p[N], cnt[N]; int find(int x) { if(x != p[x]) p[x] = find(p[x]); return p[x]; } int main(void) { int t; cin >> t; while (t--) { int n; cin >> n; for (int i = 0; i < n - 1; i++) { int a, b, w; cin >> a >> b >> w; e[i] = {a, b, w}; } sort(e, e + n - 1); for (int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1; int res = 0; for (int i = 0; i < n - 1; i++) { int a = find(e[i].a), b = find(e[i].b), w = e[i].w; if (a != b) { res += (cnt[a] * cnt[b] - 1) * (w + 1); cnt[b] += cnt[a]; p[a] = b; } } cout << res << endl ; } return 0; }
1148. 秘密的牛奶运输 - AcWing题库
#includeusing namespace std; typedef long long LL; const int N = 510, M = 10010; int n, m; struct Edge { int a, b, w; bool f; bool operator< (const Edge &t) const { return w < t.w; } }edge[M]; int p[N]; int dist1[N][N], dist2[N][N]; int h[N], e[N * 2], w[N * 2], ne[N * 2], idx; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int find(int x) { if (x != p[x]) p[x] = find(p[x]); return p[x]; } void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[]) { d1[u] = maxd1, d2[u] = maxd2; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (j != fa) { int td1 = maxd1, td2 = maxd2; if (w[i] > td1) td2 = td1, td1 = w[i]; else if (w[i] < td1 && w[i] > td2) td2 = w[i]; dfs(j, u, td1, td2, d1, d2); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) { int a, b, w; cin >> a >> b >> w; edge[i] = {a, b, w}; } sort(edge, edge + m); for (int i = 1; i <= n; i ++ ) p[i] = i; LL sum = 0; for (int i = 0; i < m; i ++ ) { int a = edge[i].a, b = edge[i].b, w = edge[i].w; int pa = find(a), pb = find(b); if (pa != pb) { p[pa] = pb; sum += w; add(a, b, w), add(b, a, w); edge[i].f = true; } } for (int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]); LL res = 1e18; for (int i = 0; i < m; i ++ ) if (!edge[i].f) { int a = edge[i].a, b = edge[i].b, w = edge[i].w; LL t; if (w > dist1[a][b]) t = sum + w - dist1[a][b]; else if (w > dist2[a][b]) t = sum + w - dist2[a][b]; res = min(res, t); } cout << res << endl ; return 0; }
904. 虫洞 - AcWing题库
spfa判断负环
#includeusing namespace std; const int N = 510, M = 5210; int n, m1, m2; int h[N], e[M], ne[M], w[M], idx; int dist[N]; int q[N], cnt[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } bool spfa() { int hh = 0, tt = 0; memset(dist, 0, sizeof dist); memset(st, 0, sizeof st); memset(cnt, 0, sizeof cnt); for (int i = 1; i <= n; i++) { q[tt++] = i; st[i] = true; } while (hh != tt) { int t = q[hh++]; if (hh == N) hh = 0; st[t] = false; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; if (!st[j]) { q[tt++] = j; if (tt == N) tt = 0; st[j] = true; } } } } return false; } int main(void) { int T; cin >> T; while (T--) { cin >> n >> m1 >> m2; memset(h, -1, sizeof h); idx = 0; while (m1--) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } while (m2--) { int a, b, c; cin >> a >> b >> c; add(a, b, -c); } if (spfa()) puts("YES"); else puts("NO"); } return 0; }
361. 观光奶牛 - AcWing题库
01分数规划问题,先二分一个可能的答案,然后通过整理不等式,最后得出是否存在满足条件的正环
#includeusing namespace std; const int N = 1010, M = 5010; int n, m; int wf[N]; int h[N], e[M], wt[M], ne[M], idx; double dist[N]; int q[N], cnt[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } bool check(double mid) { memset(dist, 0, sizeof dist); memset(st, 0, sizeof st); memset(cnt, 0, sizeof cnt); int hh = 0, tt = 0; for (int i = 1; i <= n; i ++ ) { q[tt ++ ] = i; st[i] = true; } while (hh != tt) { int t = q[hh ++ ]; if (hh == N) hh = 0; st[t] = false; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] < dist[t] + wf[t] - mid * wt[i]) { dist[j] = dist[t] + wf[t] - mid * wt[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; if (!st[j]) { q[tt ++ ] = j; if (tt == N) tt = 0; st[j] = true; } } } } return false; } int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> wf[i]; memset(h, -1, sizeof h); for (int j = 0; j < m; j ++ ) { int a, b, c; cin >> a >> b >> c; add(a, b, c); } double l = 0, r = 1e6; // 浮点数二分 while (r - l > 1e-4) { double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } printf("%.2lfn", l); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)