本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 21:36:59

就是对于所有前缀查询，可以把操作序列放在线段树上进行维护，每一个操作序列都对应log个区间，对于每一个区间暴力放进去与拿出来。

模板的代码

const int N=2e5+5;

int n;

struct DSU{
	int fa[N<<1],sum[N<<1];
	struct hhh{
		int u,v;
		bool tag;
	}stk[N];int hd;
	void init(){
		for(int i=1;i<=2*n;i++)
			fa[i]=i,sum[i]=1;
	}
	int fd(int x){
		return fa[x]==x?x:fd(fa[x]);
	}
	void merge(int x,int y){
		int fx=fd(x),fy=fd(y);
		if(fx!=fy){
			fx=fd(x+n);
			if(sum[fx]<sum[fy])
				swap(fx,fy);
			hd++;
			stk[hd]={fx,fy,stk[hd-1].tag};
			sum[fx]+=sum[fy];
			fa[fy]=fx;
			fx=fd(x);
			fy=fd(y+n);
			if(sum[fx]<sum[fy])
				swap(fx,fy);
			hd++;
			stk[hd]={fx,fy,stk[hd-1].tag};
			sum[fx]+=sum[fy];
			fa[fy]=fx;
		}else
			stk[++hd]={0,0,1},stk[++hd]={0,0,1};
	}
	void del(){
		sum[stk[hd].u]-=sum[stk[hd].v];
		fa[stk[hd].v]=stk[hd].v;
		hd--;
		sum[stk[hd].u]-=sum[stk[hd].v];
		fa[stk[hd].v]=stk[hd].v;
		hd--;
	}
}D;

struct Seg_Tree{
	vector<pir>v[N<<2];
	void update(int x,int l,int r,int L,int R,pir a){
		if(L<=l&&r<=R)
			v[x].pb(a);
		else{
			if(L<=mid)
				update(ls,l,mid,L,R,a);
			if(R>mid)
				update(rs,mid+1,r,L,R,a);
		}
	}
	void calc(int x,int l,int r){
		for(pir i:v[x])
			D.merge(i.fi,i.se);
		if(l==r)
			printf(D.stk[D.hd].tag?"No\n":"Yes\n");
		else{
			calc(ls,l,mid);
			calc(rs,mid+1,r);
		}
		int tmp=v[x].size();
		while(tmp--)
			D.del();
	}
}T;

signed main(){
	n=read();int m=read(),k=read();
	D.init();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),l=read()+1,r=read();
		T.update(1,1,k,l,r,{u,v});
	}
	T.calc(1,1,n);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-02 15:39:23

因为数据范围很小，一开始的思路是对每一个经过的无权边数量的方案都求一个最短路，如经过1条无权边的最短路，两条的最短路。。。

这里并不需要使经过的无权边不重复，因为我只关心这里面经过最短路小于等于L同时无权边最少的方案。容易发现这个方案一定不会有无权边被重复经过。

复杂度是 $\mathrm{O(n^2\log m)}$ ，如果每一条边都是无权边的话可能会过不去，但没有这样的数据。结果跑过了，，

然而题解区有一个更好的 $\mathrm{O(n\log m\log(mL))}$ 的方法。

发现同时给所有无权边加1，若存在答案且当前最短路小于 $L$ ，则最短路长度一定至少增加1。

然后只给其中一条边加1，最短路长度最多增加1。

直接给每一个无权边定一个序号，然后二分即可。需要判一下没有无权边和达不到L的情况。

code

struct edge{
	int v,w,nxt;
}e[M<<1];
int head[N],tott;
void add(int u,int v,int w){e[++tott]={v,w,head[u]},head[u]=tott;}

struct Edge{
	int u,v,w;
}E[M];

vector<int>eg;

int st,ed;

struct hhh{
	int u,w;
	bool operator<(hhh ano)const{
		return w>ano.w;
	}
};
priority_queue<hhh>q;

int dis[N];
bool vis[N];

int dij(){
	q.push({st,0});
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[st]=0;
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[u]+w<dis[v])
				dis[v]=dis[u]+w,q.push({v,dis[v]});
		}
	}
	return dis[ed];
}

int check(int x){
	int tmp=x%eg.size();
	for(int i:eg){
		if(tmp==0)
			e[2*i-1].w=e[2*i].w=x\/eg.size();
		else
			e[2*i-1].w=e[2*i].w=x\/eg.size()+1,tmp--;
	}
	return dij();
}

signed main(){
	int n=read(),m=read(),L=read();st=read(),ed=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		if(w==0)
			eg.pb(i);
		add(u,v,w);add(v,u,w);
		E[i]={u,v,w};
	}
	if(eg.size()==0){
		if(dij()==L){
			printf("YES\n");
			for(int i=1;i<=m;i++)
				print(E[i].u),pc(' '),print(E[i].v),pc(' '),print(E[i].w),pc('\n');
		}else
			printf("NO\n");
		return 0;
	}
	int l=eg.size(),r=(__int128)(eg.size())*1e9,ans=-1;
	while(l<=r){
		int tmp=check(mid);
		if(tmp<=L){
			if(tmp==L)
				ans=mid;
			l=mid+1;
		}else
			r=mid-1;
	}
	if(ans==-1)
		printf("NO\n");
	else{
		int tmp=ans%eg.size();
		for(int i:eg){
			if(tmp==0)
				E[i].w=ans\/eg.size();
			else
				E[i].w=ans\/eg.size()+1,tmp--;
		}
		printf("YES\n");
		for(int i=1;i<=m;i++)
			print(E[i].u),pc(' '),print(E[i].v),pc(' '),print(E[i].w),pc('\n');
	}
	return 0;
}