Loading [MathJax]/extensions/tex2jax.js

[洛谷 4185][USACO18JAN]MooTube

题目链接

https://www.luogu.org/problem/P4185

题解

题目并不要求强制在线,我们可以将询问按 \(k\) 的值降序排序后离线解决本题。

我们用并查集维护连通块,对于每个询问,我们将边权大于等于给定的边权 \(k\) 的边加入图中,对于一个点 \(v\),满足条件的点数为其所在连通块大小 -1。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include <cstdio>
#include <algorithm>
using namespace std;
struct edge
{
int u,v,w;
}e[100005];
struct query
{
int k,v,id;
}a[100005];
int fa[100005],siz[100005],ans[100005];
bool cmp1(const edge&a,const edge&b)
{
return a.w>b.w;
}
bool cmp2(const query&a,const query&b)
{
return a.k>b.k;
}
void unionn(int x,int y)
{
if(x==y)return;
fa[y]=x;
siz[x]+=siz[y];
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
fa[i]=i,siz[i]=1;
for(int i=1;i<n;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&a[i].k,&a[i].v);
a[i].id=i;
}
sort(e+1,e+n,cmp1);
sort(a+1,a+q+1,cmp2);
int cur=1;
for(int i=1;i<=q;i++)
{
while(cur<=n&&a[i].k<=e[cur].w)
{
unionn(find(e[cur].u),find(e[cur].v));
cur++;
}
ans[a[i].id]=siz[find(a[i].v)]-1;
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
#include <cstdio> #include <algorithm> using namespace std; struct edge { int u,v,w; }e[100005]; struct query { int k,v,id; }a[100005]; int fa[100005],siz[100005],ans[100005]; bool cmp1(const edge&a,const edge&b) { return a.w>b.w; } bool cmp2(const query&a,const query&b) { return a.k>b.k; } void unionn(int x,int y) { if(x==y)return; fa[y]=x; siz[x]+=siz[y]; } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } int main() { int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1; for(int i=1;i<n;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); for(int i=1;i<=q;i++) { scanf("%d%d",&a[i].k,&a[i].v); a[i].id=i; } sort(e+1,e+n,cmp1); sort(a+1,a+q+1,cmp2); int cur=1; for(int i=1;i<=q;i++) { while(cur<=n&&a[i].k<=e[cur].w) { unionn(find(e[cur].u),find(e[cur].v)); cur++; } ans[a[i].id]=siz[find(a[i].v)]-1; } for(int i=1;i<=q;i++) printf("%d\n",ans[i]); return 0; }
#include <cstdio>
#include <algorithm>
using namespace std;
struct edge
{
 int u,v,w;
}e[100005];
struct query
{
 int k,v,id;
}a[100005];
int fa[100005],siz[100005],ans[100005];
bool cmp1(const edge&a,const edge&b)
{
 return a.w>b.w;
}
bool cmp2(const query&a,const query&b)
{
 return a.k>b.k;
}
void unionn(int x,int y)
{
 if(x==y)return;
 fa[y]=x;
 siz[x]+=siz[y];
}
int find(int x)
{
 return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
 int n,q;
 scanf("%d%d",&n,&q);
 for(int i=1;i<=n;i++)
  fa[i]=i,siz[i]=1;
 for(int i=1;i<n;i++)
  scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
 for(int i=1;i<=q;i++)
 {
  scanf("%d%d",&a[i].k,&a[i].v);
  a[i].id=i;
 }
 sort(e+1,e+n,cmp1);
 sort(a+1,a+q+1,cmp2);
 int cur=1;
 for(int i=1;i<=q;i++)
 {
  while(cur<=n&&a[i].k<=e[cur].w)
  {
   unionn(find(e[cur].u),find(e[cur].v));
   cur++;
  }
  ans[a[i].id]=siz[find(a[i].v)]-1;
 }
 for(int i=1;i<=q;i++)
  printf("%d\n",ans[i]);
 return 0;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理