当前位置:网站首页>P2993 [fjoi2014] shortest path tree problem (Dijkstra & point divide and conquer)

P2993 [fjoi2014] shortest path tree problem (Dijkstra & point divide and conquer)

2021-08-10 08:44:10 wx6110fa547fd20

P2993 [FJOI2014] The shortest path tree problem (dijkstra& Point divide and conquer )

Ideas

part1

run dijkstra, Then sort the edges , Establish the shortest path spanning tree MPT

part2

Naked dots divide , The path length and number of edges of a subtree are preprocessed each time , Then use two side buckets to maintain ( The path is long , Number of paths ) Just two variables .

Time complexity : O ( m l o g n + n l o g 2 n ) O(mlogn+nlog^2n) O(mlogn+nlog2n)

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=3e4+5,M=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define hh(u,i) for(int i=h[u];i;i=e[i].nt)
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int n,m,k;
//if have char input #define should cancel
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline T& read(T& r) {
    r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
    while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
    return r = w ? -r : r;
}
vector<PII>g[N];
int d[N],vis[N];
void dij(){
	priority_queue<PII>q;mst(d,0x3f);d[1]=0;q.push({0,1});
	while(!q.empty()){
		int u=q.top().se,l=-q.top().fi;q.pop();
		if(l>d[u]) continue;
		for(auto [v,w]:g[u]){
			if(d[v]>d[u]+w) d[v]=d[u]+w,q.push({-d[v],v});
		}
	}
	for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
}
int h[N],cnt;
struct edge{
	int to,nt,w;
}e[M<<1];
void add(int u,int v,int w){
	e[++cnt]={v,h[u],w},h[u]=cnt;
	e[++cnt]={u,h[v],w},h[v]=cnt;
}
	//create MPT mininum path tree
void bud(int u){
	vis[u]=1;
	for(auto [v,w]:g[u]){
		if(vis[v]||d[v]!=d[u]+w) continue;
		add(u,v,w);bud(v);
	}
}
int sz[N],mx[N],rt,sum;
void grt(int u,int fa){
	mx[u]=0,sz[u]=1;
	 hh(u,i){
		int v=e[i].to,w=e[i].w;
		if(vis[v]||v==fa) continue;
		grt(v,u);
		sz[u]+=sz[v];mx[u]=max(mx[u],sz[v]);
	}
	mx[u]=max(mx[u],sum-sz[u]);
	if(mx[u]<mx[rt]) rt=u;
}
int tot;
PII dis[N],tmp[N],now[N];
PII ans;
int bkz;
void dfs(int u,int fa,int x,int y){
	if(y<k) dis[++tot]={x,y};
	 hh(u,i){
		int v=e[i].to,w=e[i].w;
		if(vis[v]||v==fa) continue;
		dfs(v,u,x+w,y+1);
	}
}
void cal(int u,int x,int y){
	 tot=0;dfs(u,0,x,y);
	 for(int i=1;i<=tot;i++){
	 	auto [x,y]=dis[i];//w len
	 	int z=k-1-y;
	 	auto [p,q]=tmp[z]; //w cnt
	 	if(x+p>ans.fi) ans={x+p,q};
	 	else if(x+p==ans.fi) ans.se+=q;
	 }
	 for(int i=1;i<=tot;i++){
	 	auto [x,y]=dis[i];
	 	auto [p,q]=tmp[y];
	 	if(x>p) tmp[y]={x,1};
	 	else if(x==p) tmp[y].se++;
	 	bkz=max(bkz,x);
	 }
}
void solve(int u){
	vis[u]=1;
	tmp[0]={0,1};bkz=0;
	hh(u,i){
	 	int v=e[i].to,w=e[i].w;
	 	if(!vis[v]) cal(v,w,1);
 	 }
 	 memset(tmp,0,sizeof(PII)*(bkz+2));
    hh(u,i){
    	int v=e[i].to;if(vis[v]) continue;
    	sum=mx[rt=0]=sz[v];grt(v,u);grt(rt,0);
    	solve(rt);
    }
}
int main(){
	read(n),read(m),read(k);
	for(int i=1,u,v,w;i<=m;i++){
		read(u),read(v),read(w);
		g[u].pb(v,w);
		g[v].pb(u,w);
	}
	dij();bud(1),mx[0]=sum=n;mst(vis,0);
	grt(1,0);grt(rt,0);
	solve(rt);
	printf("%d %d\n",ans.fi,ans.se);
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.
  • 85.
  • 86.
  • 87.
  • 88.
  • 89.
  • 90.
  • 91.
  • 92.
  • 93.
  • 94.
  • 95.
  • 96.
  • 97.
  • 98.
  • 99.
  • 100.
  • 101.
  • 102.
  • 103.
  • 104.
  • 105.
  • 106.
  • 107.
  • 108.
  • 109.
  • 110.
  • 111.
  • 112.
  • 113.
  • 114.
  • 115.
  • 116.
  • 117.
  • 118.
  • 119.
  • 120.
  • 121.
  • 122.
  • 123.
  • 124.
  • 125.
  • 126.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810084311898I.html

随机推荐