P2483-[template]k short circuit /[sdoi2010] Magic pig college [chairman tree, pile]

On the subject

Topic link :https://www.luogu.com.cn/problem/P2483

---

The main idea of the topic

Give a $n$ A little bit $m$ A weighted digraph with edges , Find the largest $k$ bring $1\sim n$ Before $k$ The sum of the short path lengths does not exceed $E$.

$2\le n\le 5000,1\le m\le 2\times 10^5,1\le E\le 10^7$

---

Their thinking

Let's start with $n$ A reverse shortest path tree running out , Note that the shortest path tree here is a real tree , We from $DAG$ Some edges of the tree are casually mentioned to form a tree , With $n$ Root .

Then consider that we take out other paths that are not on the tree , Then these edges must meet the end point of the previous edge $t$ It must start on the next side $s$ In the subtree .

If we can determine such an ordered edge set, it is equivalent to determining such a unique path .

Then consider an edge $(x,y,w)$ The edge weight of is regarded as $di{s}_y-di{s}_x+w$, So the final path length is $di{s}_1$ Add the weight sum of these edges .

Then consider how to extend our solution , Let's say that our current edge set $E$ The penultimate and last of are respectively $(x^{\prime },y^{\prime },w^{\prime }),(x,y,w)$

So we have two ways to extend ：

1. Add an edge at the end , The starting point of this side must be $y$ or $y$ The ancestors of the .
2. Replace the last edge , This edge must start from $y^{\prime }$ Or the side of its ancestors that is just more powerful than the current one .

Because there are repeated edge weights , Let's give each side a specific order .

Then maintain the state of the last two sides with the heap , The chairman tree maintains a weight segment tree of all outgoing edges of each point's ancestor .

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=2e5+10,M=N<<5;
const double eps=1e-8;
struct edge{
    
	int x,y;
	bool ban;
	double w;
}e[N];
struct node{
    
	int to,next,w;
}a[N];
int n,m,tot,ans,ls[N],ban[N],fa[N],rt[N];
double f[N],k;bool v[N];map<int,int> u[N];
vector<int> T[N],ot[N];
priority_queue<pair<double,int> >_q;
priority_queue<pair<double,pair<int,int> > >q;
struct SegTree{
    
	int cnt,w[M],ls[M],rs[M];
	int Change(int x,int L,int R,int pos){
    
		int p=++cnt;w[p]=w[x]+1;
		if(L==R)return p;int mid=(L+R)>>1;
		if(pos<=mid)ls[p]=Change(ls[x],L,mid,pos),rs[p]=rs[x];
		else rs[p]=Change(rs[x],mid+1,R,pos),ls[p]=ls[x];
		return p;
	}
	int Ask(int x,int L,int R,int k){
    
		if(k>R||!w[x])return 0;
		if(L==R)return L;int mid=(L+R)>>1;
		if(k>mid)return Ask(rs[x],mid+1,R,k);
		int ans=Ask(ls[x],L,mid,k);
		if(!ans)ans=Ask(rs[x],mid+1,R,k);
		return ans;
	}
}S;
void addl(int x,int y,int w){
    
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;a[tot].w=w;
	return;
}
void dij(){
    
	for(int i=1;i<n;i++)f[i]=1e100;
	_q.push(mp(0,n));
	while(!_q.empty()){
    
		int x=_q.top().second;_q.pop();
		if(v[x])continue;v[x]=1;
		for(int i=ls[x];i;i=a[i].next){
    
			int y=a[i].to;
			if(f[x]+e[a[i].w].w<f[y]){
    
				f[y]=f[x]+e[a[i].w].w;
				ban[y]=a[i].w;fa[y]=x;
				_q.push(mp(-f[y],y));
			}
		}
	}
	return;
}
bool cmp(edge x,edge y)
{
    return x.w<y.w;}
void dfs(int x){
    
	for(int i=0;i<ot[x].size();i++)
		rt[x]=S.Change(rt[x],1,m,ot[x][i]);
	for(int i=0;i<T[x].size();i++)
		rt[T[x][i]]=rt[x],dfs(T[x][i]);
	return;
}
void solve(){
    
	int x=S.Ask(rt[1],1,m,0);
	q.push(mp(-f[1]-e[x].w,mp(1,x)));
	while(!q.empty()){
    
		double w=-q.top().first;
		int x=q.top().second.first;
		int y=q.top().second.second;
		q.pop();
		if(k+eps<w){
    ans++,ans--;return;}
		k-=w;ans++;
		int p=S.Ask(rt[e[y].y],1,m,1);
		if(p)q.push(mp(-w-e[p].w,mp(e[y].y,p)));
		p=S.Ask(rt[x],1,m,y+1);
		if(p)q.push(mp(-w+e[y].w-e[p].w,mp(x,p)));
	}
}
int main()
{
    
// freopen("P2483_3.in","r",stdin);
	scanf("%d%d%lf",&n,&m,&k);
	for(int i=1;i<=m;i++){
    
		scanf("%d%d%lf",&e[i].x,&e[i].y,&e[i].w);
		addl(e[i].y,e[i].x,i);
	}
	dij();
	if(k<f[1])return puts("0")&0;k-=f[1];ans++;
	for(int i=1;i<n;i++)e[ban[i]].ban=1;
	for(int i=1;i<n;i++)T[fa[i]].push_back(i);
	for(int i=1;i<=m;i++)
		if(!e[i].ban&&e[i].x!=n)
			e[i].w=f[e[i].y]+e[i].w-f[e[i].x];
		else swap(e[i],e[m]),m--,i--;
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)ot[e[i].x].push_back(i);
	dfs(n);solve();
	printf("%d\n",ans);
	return 0;
}