Tarjan縮點

或許更好的閱讀體驗

P3387 【模板】縮點

思路

既然時縮點的模板，那么縮點自然少不了了，縮點后我們的到新的有向無環圖，然后再利用這個無環圖去找一條最大權值的路徑，路徑和即為答案。

我們改如何選取起點來避免不必要的計算，假設存在一條路徑，我們的最大值一定時從起點開始的，所以我們選取所有的縮點以后入度為零的點去bfs，然后不斷更新最大路徑值。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c > '9' || c < '0') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N1 = 1e4 + 10, N2 = 1e5 + 10;int head[N1], to[N2], nex[N2], cnt = 1; int dfn[N1], low[N1], visit[N1], scc[N1], point[N1], value[N1], n, m, tot, sum; int x[N2], y[N2]; int stk[N1], top;int head1[N1], to1[N2], nex1[N2], cnt1 = 1; int in[N1];void tarjan(int rt) {dfn[rt] = low[rt] = ++tot;visit[rt] = 1;stk[++top] = rt;for(int i = head[rt]; i; i = nex[i]) {if(!dfn[to[i]]) {tarjan(to[i]);low[rt] = min(low[rt], low[to[i]]);}else if(visit[to[i]]) {low[rt] = min(low[rt], dfn[to[i]]);}}if(dfn[rt] == low[rt]) {sum++;do {visit[stk[top]] = 0;scc[stk[top]] = sum;value[sum] += point[stk[top]];top--;}while(stk[top + 1] != rt);} }void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void bfs() {queue<pair<int, int>> q;for(int i = 1; i <= sum; i++)if(in[i] == 0)q.push(make_pair(i, value[i]));int ans = 0;while(!q.empty()) {int temp = q.front().first;ans = max(ans, q.front().second);for(int i = head1[temp]; i; i = nex1[i])q.push(make_pair(to1[i], q.front().second + value[to1[i]]));q.pop();}printf("%d\n", ans); }int main() {// freopen("in.txt", "r", stdin);n = read(), m = read();for(int i = 1; i <= n; i++)point[i] = read();for(int i = 1; i <= m; i++) {x[i] = read(), y[i] = read();add(x[i], y[i]);}for(int i = 1; i <= n; i++)if(!dfn[i])tarjan(i);for(int i = 1; i <= m; i++)//縮點后重新建邊。if(scc[x[i]] != scc[y[i]]) {in[scc[y[i]]]++;to1[cnt1] = scc[y[i]];nex1[cnt1] = head1[scc[x[i]]];head1[scc[x[i]]] = cnt1++;}bfs();return 0; }

Popular Cows

思路

顯然是一道縮點的題目，縮點完后，我們可以知道如果一個強連通分量的出度為零，并且只有一個強連通分量的初讀為零，那么縮點后的圖一定時聯通的，這個時候出度為零的強連通分量重的點的個數就是我們要求的答案。

代碼

// #include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <stdlib.h> #include <queue> #include <stack> #include <vector> #include <bitset>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c > '9' || c < '0') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N1 = 1e4 + 10, N2 = 5e4 + 10;int head[N1], to[N2], nex[N2], cnt = 1; int visit[N1], dfn[N1], low[N1], scc[N1], sz[N1], n, m, tot, sum; int x[N2], y[N2], out[N1]; int stk[N1], top;void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void tarjan(int rt) {visit[rt] = 1, stk[++top] = rt;dfn[rt] = low[rt] = ++tot;for(int i = head[rt]; i; i = nex[i]) {if(!dfn[to[i]]) {tarjan(to[i]);low[rt] = min(low[rt], low[to[i]]);}else if(visit[to[i]])low[rt] = min(low[rt], dfn[to[i]]);}if(dfn[rt] == low[rt]) {sum++;do {scc[stk[top]] = sum;sz[sum]++;visit[stk[top]] = 0;top--;}while(rt != stk[top + 1]);} }int main() {// freopen("in.txt", "r", stdin);while(scanf("%d %d", &n, &m) != EOF) {for(int i = 1; i <= n; i++)head[i] = visit[i] = sz[i] = out[i] = dfn[i] = 0;cnt = 1, tot = sum = top = 0;for(int i = 1; i <= m; i++) {x[i] = read(), y[i] = read();add(x[i], y[i]);}for(int i = 1; i <= n; i++)if(!dfn[i])tarjan(i);// puts("okkkkk");for(int i = 1; i <= m; i++)if(scc[x[i]] != scc[y[i]])out[scc[x[i]]]++;int num = 0, ans = 0;for(int i = 1; i <= sum; i++)if(out[i] == 0) {ans = sz[i];num++;}if(num != 1) puts("0");else printf("%d\n", ans);}return 0; }

Bomb

思路

容易想到爆炸就是一個傳遞的圖，當爆炸形成一個環的時候，明顯可以進行縮點操作，所以當我們進行完縮點之后，我們只要統計剩余的點中入度為零的點就行，同時我們需要的花費就是這些點所在的聯通分量中的花費最小的點。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const ll INF = 0x3f3f3f3f3f3f3f3f; const int N1 = 1e3 + 10, N2 = 1e6 + 10;int head[N1], to[N2], nex[N2], cnt; int visit[N1], dfn[N1], low[N1], scc[N1], n, sum, tot; int stk[N1], in[N1], top; ll cost[N1];struct point {ll x, y, c, r;void input() {x = read(), y = read(), r = read(), c = read();} }a[N1];ll dis(point a, point b) {return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void tarjan(int rt) {dfn[rt] = low[rt] = ++tot;stk[++top] = rt;visit[rt] = 1;for(int i = head[rt]; i; i = nex[i]) {if(!dfn[to[i]]) {tarjan(to[i]);low[rt] = min(low[rt], low[to[i]]);}else if(visit[to[i]])low[rt] = min(low[rt], dfn[to[i]]);}if(dfn[rt] == low[rt]) {sum++;do {scc[stk[top]] = sum;cost[sum] = min(cost[sum], a[stk[top]].c);visit[top[stk]] = 0;top--;}while(stk[top + 1] != rt);} }int main() {// freopen("in.txt", "r", stdin);int t = read();for(int cas = 1; cas <= t; cas++) {n = read();for(int i = 1; i <= n; i++) {head[i] = visit[i] = dfn[i] = low[i] = scc[i] = in[i] = 0;cost[i] = INF;a[i].input();}tot = sum = top = 0, cnt = 1;for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++) {ll d = dis(a[i], a[j]);if(d <= a[i].r * a[i].r)add(i, j);if(d <= a[j].r * a[j].r)add(j, i);}for(int i = 1; i <= n; i++)if(!dfn[i])tarjan(i);for(int i = 1; i <= n; i++)for(int j = head[i]; j; j = nex[j])if(scc[i] != scc[to[j]])in[scc[to[j]]]++;ll ans = 0;for(int i = 1; i <= sum; i++)if(in[i] == 0)ans += cost[i];printf("Case #%d: %lld\n", cas, ans);}return 0; }

總結

以上是生活随笔為你收集整理的Tarjan缩点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。