prim和Kruskal太久不打,都忘光啦。
题目大意:
给n个点和m条边,每个点有一个高度h[i],给定的m条边都有三个参数u,v,k表示u和v点有一天长度为k的边。其中这条边只能从高度高的地方连向高度低的地方。(两个点高度相同时就是无向边,否则是有向边)
现在你可以从点1开始,问最多可以访问到的点的数量,以及在访问尽量多的点的前提下,让总路程最短。
他有一种特异功能,可以无消耗无限制的回到之前去过的点。
n<=10^5,m<=10^6
思路:
首先根据题意我们可以完成建图。然后判断最多的点数量,我们可以从1开始直接bfs或者dfs求连通块数量。
接着考虑第二个问题,其实如果是无向图,就变成最小生成树了。但是本题是有向图,有向图不能直接套最小生成树,因为可能本身选的这条边是非连通块内的或者是不能直接到达的,据说求有向图的最小生成树叫做最小树形图,据说解决的算法叫做朱刘算法,复杂度是O(n^3)。本题显然不可能。
参考了题解,解法比较巧妙。
对边按照指向点的高度排序,高度相同按长度排序。
然后进行Kruskal求解。
这样做可以解决问题的原因在于,我们先取的边一定是高度更高的边,把高度较高的取完以后,再去看高度低的边,就可以保证不会出现先取了高度低的边。
代码:
#include<bits/stdc++.h> using namespace std; int n,m,h[100040],tot,head[100040],vis[100040]; int fa[100040]; long long sum; int finda(int x){ if(x!=fa[x])fa[x]=finda(fa[x]); return fa[x]; } struct node{ int u,to,next,w; bool operator <(const node& a)const{ if(h[to]==h[a.to])return w<a.w; return h[to]>h[a.to]; } }e[2000400]; void init(){ tot=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); } void add(int a,int b,int c){ tot++; e[tot].u=a; e[tot].to=b; e[tot].next=head[a]; e[tot].w=c; head[a]=tot; } int ans; void dfs(int x){ vis[x]=1; ans++; for(int i=head[x];~i;i=e[i].next){ int y=e[i].to; if(vis[y])continue; dfs(y); } } void kruskal(int x){ for(int i=0;i<=n;i++)fa[i]=i; int cnt=1; for(int i=1;i<=tot;i++){ int u,v; u=e[i].u;v=e[i].to; if(vis[u]&&vis[v]){ u=finda(u);v=finda(v); if(u!=v){ fa[u]=v; sum+=e[i].w; } } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++)cin>>h[i]; init(); for(int i=1;i<=m;i++){ int u,v,k; scanf("%d%d%d",&u,&v,&k); if(h[u]>h[v])add(u,v,k); else if(h[u]<h[v])add(v,u,k); else { add(u,v,k);add(v,u,k); } } dfs(1); sort(e+1,e+1+tot); kruskal(1); cout<<ans<<' '<<sum<<endl; }