Where are you
链接:
https://ac.nowcoder.com/acm/contest/272/D
来源:牛客网
题目描述
小(p)和他的朋友约定好去游乐场游玩,但是他们到了游乐场后却互相找不到对方了。
游乐场可以看做是一张(n)个点,(m)条道路的图,每条道路有边权(w_i),表示第一次经过该道路时的花费(第二次及以后经过时花费为(0))。
现在,小(p)要去找他的朋友,但他的朋友行踪很诡异,小(p)总是要遍历完这(n)个点才能找到他,同时小(p)希望总花费最小。
找到朋友的方案可能不唯一,小(p)想知道在这所有的方案中,有多少条边在每个方案中都会被经过。
输入描述:
第一行两个整数(n), (m),(p),分别表示点数,边数,小(p)的初始位置。
接下来(m)行,每行两个整数(u), (v), (w)表示从(u)到(v有)一条无向边,边权为(w)。
输出描述:
输出一个整数k,表示必须经过的边的数量。
说明
(2le n < m le 2 imes 10^5,1 le w le 10^6)
保证图联通,无自环无重边
比赛的时候wa了一晚上,-8了...后来发现错误是没有判(set)空然后(*s.begin())在(set)为空的时候居然是(0)...
正解不是很懂,想了一个(nlog^2n)的辣鸡做法。
思路:
先求出(MST),然后枚举不在(MST)上的边。如果这个边的两点在树上的路径中的边的权值小于等于这条边,那么树上的那条路径就是可以被取代的。
实现就是对两个点及它们的(LCA)打树上差分,然后(set)启发式合并一下就好了。
Code:
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
const int N=2e5+10;
struct node
{
int u,v,w;
bool friend operator <(node n1,node n2){return n1.w<n2.w;}
}E[N];
int n,m,f[N],used[N],ans;
int Find(int x){return f[x]=f[x]==x?x:Find(f[x]);}
void Merge(int x,int y){f[Find(x)]=Find(y);}
int head[N],to[N<<1],Next[N<<1],edge[N<<1],cnt;
void add(int u,int v,int w)
{
to[++cnt]=v,Next[cnt]=head[u],edge[cnt]=w,head[u]=cnt;
}
void krus()
{
for(int i=1;i<=n;i++) f[i]=i;
std::sort(E+1,E+1+m);
for(int i=1;i<=m;i++)
{
int u=E[i].u,v=E[i].v,w=E[i].w;
if(Find(u)!=Find(v))
{
Merge(u,v);
used[i]=1;
add(u,v,w),add(v,u,w);
}
}
}
int F[N][20],dep[N];
void dfs1(int now,int fa)
{
for(int i=1;F[now][i-1];i++) F[now][i]=F[F[now][i-1]][i-1];
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v!=fa)
{
F[v][0]=now;
dep[v]=dep[now]+1;
dfs1(v,now);
}
}
}
std::multiset <int > s[N];
std::vector <int > poi[N];
void dfs2(int now,int fa)
{
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==fa) continue;
dfs2(v,now);
if(s[v].empty()||*(s[v].begin())>edge[i]) ++ans;
if(s[now].size()<s[v].size()) std::swap(s[now],s[v]);
for(std::multiset<int>::iterator it=s[v].begin();it!=s[v].end();it++)
s[now].insert(*it);
s[v].clear();
}
for(int i=0;i<poi[now].size();i++)
{
if(poi[now][i]<0)
s[now].erase(s[now].find(-poi[now][i]));
else
s[now].insert(poi[now][i]);
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) return LCA(y,x);
for(int i=18;~i;i--)
if(dep[F[x][i]]>=dep[y])
x=F[x][i];
if(x==y) return x;
for(int i=18;~i;i--)
if(F[x][i]!=F[y][i])
x=F[x][i],y=F[y][i];
return F[x][0];
}
bool cmp(int n1,int n2){return n1>n2;}
int main()
{
int p;scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
krus();
dep[1]=1;dfs1(1,1);
for(int i=1;i<=m;i++)
{
int u=E[i].u,v=E[i].v,w=E[i].w;
if(used[i]) continue;
int lca=LCA(u,v);
poi[u].push_back(w);
poi[v].push_back(w);
poi[lca].push_back(-w);
poi[lca].push_back(-w);
}
dfs2(1,1);
printf("%d
",ans);
return 0;
}
2018.12.1