NC14616. Build
描述
In country A, some roads are to be built to connect the cities。However, due to limited funds, only some roads can be built.That is to say，if the limit is 100$, only roads whose cost are no more than 100$ can be built.
Now give you n cities, m roads and the cost of each road wi (i=1..m). There are q queries, for each query there is a number k, represent the limit, you need to output the maximum number of pairs of cities that can reach each other.
输入描述
The first line consist of two integers, n,m, n the number of cities and m the number of roads. The next m lines , each line has three integers a,b,w, represent that you can bulid a road between city a and city b with cost w.
The next line an integer q, the number of querries. The next q lines each an integer k ,the limit of the fund.
n<10000, m < 10000, k < 10000, q<10000;
输出描述
For each querry ,you should output the anwser.
示例1
输入:
3 2 1 2 1 2 3 2 1 2
输出:
3
C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 760K, 提交时间: 2020-08-29 08:28:26
#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N=1e4+10;
const int INF=0x3f3f3f3f;
int n,m,q,x,res=0,cnt=1,ans[N],fa[N],Size[N];
struct Node {
int a,b,v;
bool friend operator<(Node c,Node d) {
return c.v<d.v;
}
} p[N];
int Find(int x) {
if(x==fa[x])return x;
return fa[x]=Find(fa[x]);
}
int main() {
Fox;
cin>>n>>m;
for(int i=1; i<=m; i++)cin>>p[i].a>>p[i].b>>p[i].v;
for(int i=1; i<=n; i++)fa[i]=i,Size[i]=1;
sort(p+1,p+1+m);
for(int i=1; i<=m; i++) {
int fx=Find(p[i].a),fy=Find(p[i].b);
if(fx==fy) {
ans[i]=ans[i-1];
continue;
}
fa[fx]=fy;
ans[i]=ans[i-1]+Size[fx]*Size[fy];
Size[fy]+=Size[fx];
}
cin>>q;
while(q--) {
cin>>x;
int l=0,r=m;
while(l<r) {
int mid=(l+r+1)>>1;
if(p[mid].v<=x)l=mid;
else r=mid-1;
}
cout<<ans[l]<<"\n";
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 928K, 提交时间: 2020-07-03 20:26:47
#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N=1e4+10;
const int INF=0x3f3f3f3f;
int n,m,q,x,res=0,cnt=1,ans[N],fa[N],Size[N];
struct Node{
int a,b,v;
bool friend operator<(Node c,Node d){
return c.v<d.v;
}
}p[N];
int Find(int x){
if(x==fa[x])return x;
return fa[x]=Find(fa[x]);
}
int main(){
Fox;
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>p[i].a>>p[i].b>>p[i].v;
for(int i=1;i<=n;i++)fa[i]=i,Size[i]=1;
sort(p+1,p+1+m);
for(int i=1;i<=m;i++){
int fx=Find(p[i].a),fy=Find(p[i].b);
if(fx==fy){
ans[i]=ans[i-1];
continue;
}
fa[fx]=fy;
ans[i]=ans[i-1]+Size[fx]*Size[fy];
Size[fy]+=Size[fx];
}
cin>>q;
while(q--){
cin>>x;
int l=0,r=m;
while(l<r){
int mid=(l+r+1)>>1;
if(p[mid].v<=x)l=mid;
else r=mid-1;
}
cout<<ans[l]<<"\n";
}
return 0;
}