P3469 [POI2008]BLO-Blockade

https://www.luogu.org/problem/P3469

題目描述

There are exactly nn towns in Byteotia.

Some towns are connected by bidirectional roads.

There are no crossroads outside towns, though there may be bridges, tunnels and flyovers. Each pair of towns may be connected by at most one direct road. One can get from any town to any other-directly or indirectly.

Each town has exactly one citizen.

For that reason the citizens suffer from loneliness.

It turns out that each citizen would like to pay a visit to every other citizen (in his host's hometown), and do it exactly once. So exactly n\cdot (n-1)n?(n?1) visits should take place.

That's right, should.

Unfortunately, a general strike of programmers, who demand an emergency purchase of software, is under way.

As an act of protest, the programmers plan to block one town of Byteotia, preventing entering it, leaving it, and even passing through.

As we speak, they are debating which town to choose so that the consequences are most severe.

Task Write a programme that:

reads the Byteotian road system's description from the standard input, for each town determines, how many visits could take place if this town were not blocked by programmers, writes out the outcome to the standard output.

給定一張無向圖，求每個點被封鎖之后有多少個有序點對(x,y)(x!=y,1<=x,y<=n)滿足x無法到達y

輸入格式

In the first line of the standard input there are two positive integers: nn and mm (1\le n\le 100?0001≤n≤100 000, 1\le m\le 500?0001≤m≤500 000) denoting the number of towns and roads, respectively.

The towns are numbered from 1 to nn.

The following mm lines contain descriptions of the roads.

Each line contains two integers aa and bb (1\le a<b\le n1≤a<b≤n) and denotes a direct road between towns numbered aa and bb.

輸出格式

Your programme should write out exactly nn integers to the standard output, one number per line. The i^{th}ith line should contain the number of visits that could not take place if the programmers blocked the town no. ii.

題意翻譯

題目描述

在Byteotia有n個城鎮(zhèn)。 一些城鎮(zhèn)之間由無向邊連接。 在城鎮(zhèn)外沒有十字路口，盡管可能有橋，隧道或者高架公路（反正不考慮這些）。每兩個城鎮(zhèn)之間至多只有一條直接連接的道路。人們可以從任意一個城鎮(zhèn)直接或間接到達另一個城鎮(zhèn)。 每個城鎮(zhèn)都有一個公民，他們被孤獨所困擾。事實證明，每個公民都想拜訪其他所有公民一次（在主人所在的城鎮(zhèn)）。所以，一共會有n*（n-1）次拜訪。

不幸的是，一個程序員總罷工正在進行中，那些程序員迫切要求購買某個軟件。

作為抗議行動，程序員們計劃封鎖一些城鎮(zhèn)，阻止人們進入，離開或者路過那里。

正如我們所說，他們正在討論選擇哪些城鎮(zhèn)會導致最嚴重的后果。

編寫一個程序：

讀入Byteotia的道路系統(tǒng)，對于每個被決定的城鎮(zhèn)，如果它被封鎖，有多少訪問不會發(fā)生，輸出結果。

輸入輸出格式

第一行讀入n，m，分別是城鎮(zhèn)數(shù)目和道路數(shù)目

城鎮(zhèn)編號1~n

接下來m行每行兩個數(shù)字a,b，表示a和b之間有有一條無向邊

輸出n行，每行一個數(shù)字，為第i個城鎮(zhèn)被鎖時不能發(fā)生的訪問的數(shù)量。

翻譯提供者：Park

輸入輸出樣例

輸入 #1復制

5 5 1 2 2 3 1 3 3 4 4 5

輸出 #1復制

8 8 16 14 8

思路：

每一個點被封鎖后，一定會有$ 2*(n-1)$ 個城市對無法到達，即該城市到剩余\(n-1\) 個城市和剩余$ n-1 $ 個城市到該城市。

還有一種情況，即一個其他城市對\(u->v\) 必須經過點x，那么節(jié)點x被封鎖后，也應該計算 u->v 這個貢獻。

在學習Tarjan算法的過程中我們知道無向圖中的割點就是把這個節(jié)點去掉后，剩下的圖變得不聯(lián)通。

來看下圖中的2號節(jié)點，如果該節(jié)點封鎖，那么上面的“0,1,4,5” 節(jié)點就無法和下面的“3”節(jié)點連接。

那么每一個節(jié)點封鎖后無法相互到達的節(jié)點對就要加上：

封鎖后產生的連通塊中的節(jié)點個數(shù)相互乘起來*2

封鎖后產生的連通塊中的節(jié)點個數(shù)可以在Tarjan算法中維護出來。

注意要把Tarjan中的

if (v == pre) { continue; }

這個語句要去掉，不然無法維護出Tarjan第一個訪問的節(jié)點的答案，

細節(jié)見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl #define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define du2(a,b) scanf("%d %d",&(a),&(b)) #define du1(a) scanf("%d",&(a)); using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;} void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}} void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}inline void getInt(int *p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ const int MAXN = 100010; const int MAXM = 1000010; struct Edge {int to, next;bool cut;//是否為橋的標記 } edge[MAXM]; int head[MAXN], tot; int Low[MAXN], DFN[MAXN], Stack[MAXN]; int Index, top; bool Instack[MAXN]; bool cut[MAXN]; int add_block[MAXN];//刪除一個點后增加的連通塊 int n, m; void addedge(int u, int v) {edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false;head[u] = tot++; } ll cntson[MAXN]; ll vans[maxn]; void Tarjan(int u, int pre) {ll z = 0ll;int v;cntson[u] = 1ll;Low[u] = DFN[u] = ++Index;for (int i = head[u]; i != -1; i = edge[i].next) {v = edge[i].to;if ( !DFN[v] ) {Tarjan(v, u);cntson[u] += cntson[v];if (Low[u] > Low[v]) {Low[u] = Low[v];}if (Low[v] >= DFN[u]) { //不是樹根vans[u] += z * cntson[v];z += cntson[v];}} else if ( Low[u] > DFN[v]) {Low[u] = DFN[v];}}vans[u] += z * (n - z - 1ll); } void solve(int N) {Index = top = 0;for (int i = 1; i <= N; i++)if (!DFN[i]) {Tarjan(i, i);}ll ans = 0ll;repd(i, 1, N) {printf("%lld\n", vans[i] + n - 1 << 1 );} } void init() {tot = 0;memset(head, -1, sizeof(head)); } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);init();scanf("%d %d", &n, &m);repd(i, 1, m) {int u, v;du2(u, v);addedge(u, v);addedge(v, u);}solve(n);return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11592807.html

總結

以上是生活随笔為你收集整理的洛谷 P3469 [POI2008]BLO-Blockade （Tarjan，割点）的全部內容，希望文章能夠幫你解決所遇到的問題。

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