n個點m條無向邊的圖,對于q個詢問,每次查詢點對間最小瓶頸路 >=f 的點對有多少。
最小瓶頸路顯然在kruskal求得的MST上。而輸入保證所有邊權唯一,也就是說f[i][j]肯定唯一了。
拿到這題第一反映是用次小生成樹的prim算法在求MST的同時求出每對點對的瓶頸路。幾乎就是一個模板題,無奈卻MLE。。。
于是換算法,用kruskal求MST,然后對于MST,離線LCA求出所有點對的瓶頸路。同 UVA 11354 Bond(MST + LCA) 然后剩下的就是讀入&二分查找輸出了。。無奈還是MLE!!!
最后。。。反思了一下。。。在kruskal的過程,當前加入的邊必定是新圖中最大的邊!也就是說,每次加入一條邊,求出當前圖中經過該邊的點對數就行了。。。求一個圖中經過該邊的點對數,將該邊割開,分別從兩個端點dfs,左邊能遍歷到x個點,右邊能遍歷到y個點,那么點對數就是x*y了。
原圖不連通的情況也是存在的吧,這個幾乎對算法不影響,只需在進入MST的點數==n的時候終止函數就行了。
?
#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<sstream>
#include<vector>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define LL long long
#define PB push_back
#define eps 1e-10
#define debug puts("**debug**")
using namespace std;
const int maxn = 10010;
const int maxm = 555555;
const int INF = 1e9;
int n, m, dfs_clock, q, f, cnt, fa[maxn];
LL sum[maxn*2];
bool seen[maxn];
vector<int> edge;
struct E
{
int u, v, w;
E(){}
E(int u, int v, int w) : u(u), v(v), w(w){}
bool operator < (const E& rhs) const
{
return w < rhs.w;
}
}e[maxm]; //kruskal的邊
vector<int> G[maxn]; //dfs用
inline void add(int a, int b)
{
G[a].PB(b);
G[b].PB(a);
}
int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }
void dfs(int u, int fa)
{
dfs_clock++;
REP(i, G[u].size())
{
int v = G[u][i];
if(v != fa) dfs(v, u);
}
}
void MST()
{
int ret = 0;
cnt = 1;
sum[0] = 0;
CLR(seen, 0);
sort(e, e+m);
REP(i, m)
{
int x = findset(e[i].u), y = findset(e[i].v);
if(x != y)
{
//統計進入森林的點數
if(!seen[e[i].u]) ret++;
if(!seen[e[i].v]) ret++;
seen[e[i].u] = 1;
seen[e[i].v] = 1;
fa[x] = y;
add(e[i].u, e[i].v);
//將邊切割雙向統計兩邊點數
dfs_clock = 0;
dfs(e[i].u, e[i].v);
int a = dfs_clock;
dfs_clock = 0;
dfs(e[i].v, e[i].u);
int b = dfs_clock;
//edge保存所有MST中邊 sum[i]為前i條邊和
edge.PB(e[i].w);
sum[cnt] = sum[cnt-1] + a*b;
cnt++;
}
if(ret == n) return ; //終止MST
}
return ;
}
void solve()
{
scanf("%d", &q);
while(q--)
{
scanf("%d", &f);
int t = lower_bound(edge.begin(), edge.end(), f) - edge.begin();
//找到f的lower_bound 答案便是總和減去小于f的點對和 注意乘以2
printf("%lld\n", (sum[cnt-1]-sum[t])*2);
}
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
REP(i, n) G[i].clear(), fa[i] = i;
edge.clear();
REP(i, m)
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
MST();
solve();
}
return 0;
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061
微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元

