題目鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=4750

題目大意：

給一無(wú)向圖，n個(gè)點(diǎn)，m條邊，每條邊有個(gè)長(zhǎng)度，且不一樣。定義f(i,j)表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的所有路徑中的最大邊權(quán)值的最小值。有q個(gè)詢問(wèn)，每個(gè)詢問(wèn)有個(gè)t,求f(i,j)>=t的種數(shù)。

解題思路：

并查集+簡(jiǎn)單dp+二分。

比賽的時(shí)候各種TLE和MLE。只是查找方式不對(duì)。

隊(duì)友思路，先按邊從小到大排序考慮，對(duì)于每條邊E該邊兩個(gè)節(jié)點(diǎn)為a、b,如果a、b不在同一個(gè)聯(lián)通塊，則a聯(lián)通塊中點(diǎn)集A和b聯(lián)通塊中點(diǎn)集B的f值一定為E（因?yàn)镋升序）。恰好能使其通路。

map[i]表示以權(quán)值為i的邊作為f值的點(diǎn)對(duì)個(gè)數(shù)。

sum[i]表示以大于等于第i大邊權(quán)值的權(quán)值作為f值得點(diǎn)對(duì)總的個(gè)數(shù)。

對(duì)于每一個(gè)t,在排序了的sig[i](能取的邊權(quán)值）中二分找到大于等于它的最小的小標(biāo)j。輸出sum[j]即可。

注意：

求點(diǎn)對(duì)個(gè)數(shù)時(shí)要乘以2.

代碼：

?

#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #define eps 1e-6 #define INF 0x3fffffff #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;#define Maxn 11000 #define Maxm 510000 struct Edge {int a,b,c; }edge[Maxm]; map<int,int>myp;short int fa[Maxn],num[Maxn]; int n,m; int sum[Maxm],sig[Maxm];bool cmp(struct Edge aa,struct Edge bb) {return aa.c<bb.c; //對(duì)邊排序 }int find(int x) //并查集 路徑壓縮 {int tmp=x;while(x!=fa[x])x=fa[x];while(fa[tmp]!=x){int tt=fa[tmp];fa[tmp]=x;tmp=tt;}return x; }int main() {//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(~scanf("%d%d",&n,&m)){int a,b,c;myp.clear();for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);edge[i].a=a,edge[i].b=b,edge[i].c=c;sig[i]=c;}sort(edge+1,edge+m+1,cmp);for(int i=0;i<=n;i++){fa[i]=i;num[i]=1; //以i為根的聯(lián)通塊點(diǎn)的個(gè)數(shù)}for(int i=1;i<=m;i++){int ra=find(edge[i].a);int rb=find(edge[i].b);if(ra!=rb) //不在一個(gè)聯(lián)通塊內(nèi)，兩個(gè)塊內(nèi)的點(diǎn)通過(guò)該邊連接，f值為該邊{if(myp.find(edge[i].c)!=myp.end())myp[edge[i].c]=myp[edge[i].c]+num[ra]*num[rb]*2;elsemyp[edge[i].c]=num[ra]*num[rb]*2;fa[rb]=ra; //合并num[ra]+=num[rb];}}int q;scanf("%d",&q);sort(sig+1,sig+m+1); //對(duì)邊權(quán)值排序memset(sum,0,sizeof(sum));//sum[i]表示以大于等于第i大邊權(quán)值的權(quán)值作為f值得點(diǎn)對(duì)總的個(gè)數(shù)。sum[m]=myp[sig[m]];for(int i=m-1;i>=1;i--)sum[i]+=sum[i+1]+myp[sig[i]];for(int i=1;i<=q;i++){int tt;scanf("%d",&tt);int pos=lower_bound(sig+1,sig+m+1,tt)-sig;//二分查找位置printf("%d\n",sum[pos]);}}return 0; }

?

?

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

總結(jié)

以上是生活随笔為你收集整理的并查集+二分-hdu-4750-Count The Pairs的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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