題目鏈接：

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

題目大意：

給一無向圖，n個點，m條邊，每條邊有個長度，且不一樣。定義f(i,j)表示從節點i到節點j的所有路徑中的最大邊權值的最小值。有q個詢問，每個詢問有個t,求f(i,j)>=t的種數。

解題思路：

并查集+簡單dp+二分。

比賽的時候各種TLE和MLE。只是查找方式不對。

隊友 思路，先按邊從小到大排序考慮，對于每條邊E該邊兩個節點為a、b,如果a、b不在同一個聯通塊，則a聯通塊中點集A和b聯通塊中點集B的f值一定為E（因為E升序）。恰好能使其通路。

map[i]表示以權值為i的邊作為f值的點對個數。

sum[i]表示以大于等于第i大邊權值的權值作為f值得點對總的個數。

對于每一個t,在排序了的sig[i](能取的邊權值）中二分找到大于等于它的最小的小標j。輸出sum[j]即可。

注意：

求點對個數時要乘以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; //對邊排序

}



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為根的聯通塊點的個數

       }

       for(int i=1;i<=m;i++)

       {

           int ra=find(edge[i].a);

           int rb=find(edge[i].b);

           if(ra!=rb) //不在一個聯通塊內，兩個塊內的點通過該邊連接，f值為該邊

           {

               if(myp.find(edge[i].c)!=myp.end())

                   myp[edge[i].c]=myp[edge[i].c]+num[ra]*num[rb]*2;

                else

                    myp[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); //對邊權值排序

       memset(sum,0,sizeof(sum));//sum[i]表示以大于等于第i大邊權值的權值作為f值得點對總的個數。

       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;

}




  

?

?

并查集+二分-hdu-4750-Count The Pairs