歷屆試題 國王的煩惱 ? 時(shí)間限制：1.0s ? 內(nèi)存限制：256.0MB 問題描述 C國由n個(gè)小島組成，為了方便小島之間聯(lián)絡(luò)，C國在小島間建立了m座大橋，每座大橋連接兩座小島。兩個(gè)小島間可能存在多座橋連接。然而，由于海水沖刷，有一些大橋面臨著不能使用的危險(xiǎn)。

　　如果兩個(gè)小島間的所有大橋都不能使用，則這兩座小島就不能直接到達(dá)了。然而，只要這兩座小島的居民能通過其他的橋或者其他的小島互相到達(dá)，他們就會(huì)安然無事。但是，如果前一天兩個(gè)小島之間還有方法可以到達(dá)，后一天卻不能到達(dá)了，居民們就會(huì)一起抗議。

　　現(xiàn)在C國的國王已經(jīng)知道了每座橋能使用的天數(shù)，超過這個(gè)天數(shù)就不能使用了。現(xiàn)在他想知道居民們會(huì)有多少天進(jìn)行抗議。 輸入格式 輸入的第一行包含兩個(gè)整數(shù)n, m，分別表示小島的個(gè)數(shù)和橋的數(shù)量。
　　接下來m行，每行三個(gè)整數(shù)a, b, t，分別表示該座橋連接a號(hào)和b號(hào)兩個(gè)小島，能使用t天。小島的編號(hào)從1開始遞增。 輸出格式 輸出一個(gè)整數(shù)，表示居民們會(huì)抗議的天數(shù)。 樣例輸入 4 4
1 2 2
1 3 2
2 3 1
3 4 3 樣例輸出 2 樣例說明 第一天后2和3之間的橋不能使用，不影響。
　　第二天后1和2之間，以及1和3之間的橋不能使用，居民們會(huì)抗議。
　　第三天后3和4之間的橋不能使用，居民們會(huì)抗議。 數(shù)據(jù)規(guī)模和約定 對(duì)于30%的數(shù)據(jù)，1<=n<=20，1<=m<=100；
　　對(duì)于50%的數(shù)據(jù)，1<=n<=500，1<=m<=10000；
　　對(duì)于100%的數(shù)據(jù)，1<=n<=10000，1<=m<=100000，1<=a, b<=n， 1<=t<=100000。

?

?

題目鏈接：國王的煩惱

這題很容易想到用逆序的辦法來求連通分支的變化情況，而且顯然對(duì)于同一天若出現(xiàn)多個(gè)地方的抗議，也只算一次，因?yàn)轭}目要算的是抗議的天數(shù)而不是次數(shù)，然而抱著1A的心態(tài)提交了一發(fā)結(jié)果只有10分…………，最后發(fā)現(xiàn)這里有個(gè)坑，假如有兩個(gè)邊天數(shù)相同，但前面的先被處理且合并失敗，那么后面的雖然合并成功但是跟最后一天的天數(shù)相同，因此不會(huì)被算到答案里去……，因此只要把更新的語句放到if里面就可以過了

代碼：

#include <stdio.h> #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); typedef pair<int, int> pii; typedef long long LL; const double PI = acos(-1.0); const int N = 10010; const int M = 100010; struct info {int a, b, t;bool operator<(const info &rhs)const{return t > rhs.t;} }; info E[M]; int pre[N];void init() {CLR(pre, -1); } int Find(int n) {return pre[n] == -1 ? n : pre[n] = Find(pre[n]); } bool joint(int a, int b) {a = Find(a);b = Find(b);if (a == b)return false;pre[a] = b;return true; } int main(void) {int n, m, i;while (~scanf("%d%d", &n, &m)){init();for (i = 0; i < m; ++i)scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].t);sort(E, E + m);int ans = 0;int last = -1;for (i = 0; i < m; ++i){if (joint(E[i].a, E[i].b) && E[i].t != last){++ans;last = E[i].t;//如果把這句放到括號(hào)外，則會(huì)出錯(cuò)，實(shí)際上last更準(zhǔn)確的來說是維護(hù)最后“成功”合并的day}}printf("%d\n", ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Blackops/p/6531211.html

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯历届试题 国王的烦恼（并查集逆序加边+坑）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。