首页 > 代码库 > Count The Pairs

Count The Pairs

2024-07-18 20:04:16   224人阅读

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

题意：给你一个带权无向图，然后让你求这样的点对s，t，使得s--t的所有路径上的最大的边的最小值>=d,输出这样的点数有多少条。

题解：这一题的解法实在是太妙了。利用克努斯卡尔的生成树的额思想，先对所有的边排序，然后不断的加边，加边的同时处理出相应的方案数，把所有额情况都处理出来，查询的时候只要O(1)的输出就可以了。具体的看代码。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 const int N=1e5+10; 8 const int M=5e5+10; 9 int n,m,q,u,v,top,temp;10 int fa[N],sum[N],ans[N];11 struct Node{12    int u,v;13    int w;14    bool operator<(const Node a)const {15      if(w!=a.w)16         return w<a.w;17      else18         return u<a.u;19    }20 }edge[M];21 void init(){22   for(int i=1;i<=n;i++){23       fa[i]=i;24       sum[i]=1;25   }26   top=0;27   memset(ans,0,sizeof(ans));28 }29 int Find(int x){30    int s;31    for(s=x;s!=fa[s];s=fa[s]);32    while(s!=x){33       int temp=fa[x];34       fa[x]=s;35       x=temp;36    }37   return s;38 }39 int main(){40     while(~scanf("%d%d",&n,&m)){41         init();42         for(int i=1;i<=m;i++){43            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);44            edge[i].v++;edge[i].u++;45         }46        sort(edge+1,edge+m+1);47         vector<int>Q;48        for(int i=1;i<=m;i++){49           int x=Find(edge[i].u);50           int y=Find(edge[i].v);51           if(x!=y){52              ans[++top]=sum[x]*sum[y]*2;53              fa[x]=y;54              sum[y]+=sum[x];55              Q.push_back(edge[i].w);56           }57        }58        for(int i=1;i<=top;i++)59           ans[i]+=ans[i-1];60        scanf("%d",&q);61        for(int i=1;i<=q;i++){62          scanf("%d",&temp);63          int id=lower_bound(Q.begin(),Q.end(),temp)-Q.begin();64          printf("%d\n",ans[top]-ans[id]);65        }66     }67 }
View Code

 


联系
我们