3 条题解

  • 1
    @ 2026-5-19 10:05:43

    提供一种我不会证正确性的做法

    既然要使最短路的长度刚好加一，那被加的这条边要刚好使所有的最短路径都经过它。

    于是跑一遍最短路，求由最短路径构成的图的所有割边。

    在所有最短路的长度被增加后，还要有路径长度为最短路加一的路径存在，不然实际上操作后最短路的长度就会被加上二。

    正着反着跑一遍最短路，遍历所有边，若两端点到起点终点的最短路加上这条边的长度刚好为最短路的长度加一，就说明存在。

    考虑到若被加的一条边会影响所有的最短路长度加一的路径，那么这条边就不能加。

    于是再用最短路长度加一的路径建一张图，继续求割边。

    最终答案就是所有最短路的割边且不是最短路长度加一的路径的割边的边。

    码：

    #include<bits/stdc++.h>
using namespace std;
#define int long long
const int MaxN=300000;
int n,m;
vector<tuple<int,int,int> >g[MaxN+1],t[MaxN+1],s[MaxN+1];
tuple<int,int,int>edge[MaxN+1];
struct Tarjan{
	vector<int>dfn,low;
	vector<bool>bridge;
	int sign;
	Tarjan(){}
	Tarjan(int n,int m,const vector<tuple<int,int,int> >*g){
		dfn=vector<int>(n+1,0);
		low=vector<int>(n+1,0);
		bridge=vector<bool>(m+1,0);
		sign=0;
		Dfs(1,0,g);
	}
	void Dfs(int u,int prt,const vector<tuple<int,int,int> >*g){
		dfn[u]=low[u]=++sign;
		for(auto&tup:g[u]){
			int v,id;
			tie(v,ignore,id)=tup;
			if(v==prt)continue;
			if(!dfn[v]){
				Dfs(v,u,g);
				low[u]=min(low[u],low[v]);
				if(dfn[u]<low[v])bridge[id]=true;
			}else low[u]=min(low[u],dfn[v]);
		}
		
	}
}tt,st;
struct HeapNode{
	HeapNode(){}
	HeapNode(int u,int val):u(u),val(val){}
	int u,val;
	bool operator<(const HeapNode&obj)const{return val>obj.val;}
};
int dis1[MaxN+1],dis2[MaxN+1];
bool vst[MaxN+1];
vector<pair<int,int> >par1[MaxN+1],par2[MaxN+1];
void Dijkstra(int st,int*dis,vector<pair<int,int> >*par){
	priority_queue<HeapNode>q;
	for(int i=1;i<=n;i++){
		dis[i]=LLONG_MAX;
		vst[i]=false;
		par[i].clear();
	}
	dis[st]=0;
	q.emplace(st,0);
	while(!q.empty()){
		int u=q.top().u;q.pop();
		if(vst[u])continue;
		vst[u]=true;
		for(auto&tup:g[u]){
			int v,d,id;
			tie(v,d,id)=tup;
			if(dis[u]+d<dis[v]){
				dis[v]=dis[u]+d;
				par[v]={{u,id}};
				q.emplace(v,dis[v]);
			}else if(dis[u]+d==dis[v])
				par[v].emplace_back(u,id);
		}
	}
}
void Dfs(int u){
	for(auto&pi:par1[u]){
		int prt=pi.first,id=pi.second;
		Dfs(prt);
		t[prt].emplace_back(u,0,id);
		t[u].emplace_back(prt,0,id);
	}
}
bool tag[MaxN+1];
void Dfs2(int u){
	if(tag[u])return;
	tag[u]=true;
	for(auto&pi:par1[u]){
		int prt=pi.first,id=pi.second;
		Dfs2(prt);
		s[prt].emplace_back(u,0,id);
		s[u].emplace_back(prt,0,id);
	}
}
void Dfs3(int u){
	if(tag[u])return;
	tag[u]=true;
	for(auto&pi:par2[u]){
		int prt=pi.first,id=pi.second;
		Dfs3(prt);
		s[prt].emplace_back(u,0,id);
		s[u].emplace_back(prt,0,id);
	}
}
void Solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		g[i].clear(),
		t[i].clear(),
		s[i].clear(),
		par1[i].clear(),
		par2[i].clear(),
		tag[i]=false;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].emplace_back(v,w,i);
		g[v].emplace_back(u,w,i);
		edge[i]=make_tuple(u,v,w);
	}
	Dijkstra(1,dis1,par1);
	Dfs(n);
	int stt=dis1[n];
	Dijkstra(n,dis2,par2);
	int flag=0;
	for(int i=1;i<=m;i++){
		int u,v,w;
		tie(u,v,w)=edge[i];
		if(dis1[u]+dis2[v]+w==stt+1){
			++flag;
			s[u].emplace_back(v,0,i);
			s[v].emplace_back(u,0,i);
			Dfs2(u);
			Dfs3(v);
		}
		swap(u,v);
		if(dis1[u]+dis2[v]+w==stt+1){
			++flag;
			s[u].emplace_back(v,0,i);
			s[v].emplace_back(u,0,i);
			Dfs2(u);
			Dfs3(v);
		}
	}
	for(int u=1;u<=n;u++){
		sort(s[u].begin(),s[u].end());
		s[u].resize(unique(s[u].begin(),s[u].end())-s[u].begin());
	}
	tt=Tarjan(n,m,t);
	st=Tarjan(n,m,s);
	if(!flag){
		cout<<"0\n\n";
		return;
	}else{
		vector<int>ans;
		for(int i=1;i<=m;i++)
			if(tt.bridge[i]&&!st.bridge[i])
				ans.push_back(i);
		cout<<ans.size()<<'\n';
		for(int val:ans)cout<<val<<' ';
		cout<<'\n';
	}
}
#undef int
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
		Solve();
	return 0;
}
    • 0
      @ 2026-5-19 10:52:18 
      #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,t;
struct N{
	ll y,v,id;
	bool operator<(const N &n1)const{
		return v>n1.v;
	}
};
struct Edge{
	ll x,y,v;
}E[300010];
vector<N> e[300010];
ll d1[300010],d2[300010];
int vis[300010];
struct N2{
	int y,id;
};
vector<N2> e2[300010],pre1[300010],pren[300010];
void dijkstra(int x,ll dis[],vector<N2> pre[]){
	priority_queue<N> q;
	q.push({x,0});
	for(int i=1;i<=n;i++){
		dis[i]=1e18;vis[i]=0;
	}
	dis[x]=0;
	while(!q.empty()){
		N t=q.top();
		q.pop();
		if(vis[t.y])continue;
		vis[t.y]=1;
		for(N i:e[t.y]){
			if(dis[i.y]>dis[t.y]+i.v){
				dis[i.y]=dis[t.y]+i.v;
				q.push({i.y,dis[i.y]});
				pre[i.y]={{t.y,i.id}};
			}
			else if(dis[i.y]==dis[t.y]+i.v){
				pre[i.y].push_back({t.y,i.id}); 
			}
		}
	}
}
int dfn[300010],low[300010],tsp,brg[300010],v2[300010];
void tarjan(int x,int yid){
	dfn[x]=low[x]=++tsp;
	for(N2 i:e2[x])if(i.id!=yid){
		if(dfn[i.y]==0){
			tarjan(i.y,i.id);
			low[x]=min(low[x],low[i.y]);
			if(dfn[x]<low[i.y])brg[i.id]=1; 
		}
		else{
			low[x]=min(low[x],dfn[i.y]);
		}
	}
}
void dfs1(int x){
	if(v2[x])return ;
	v2[x]=1;
	for(N2 i:pre1[x]){
		dfs1(i.y);
		e2[x].push_back({i.y,i.id});
		e2[i.y].push_back({x,i.id});
	}
}
void dfsn(int x){
	if(v2[x])return ;
	v2[x]=1;
	for(N2 i:pren[x]){
		dfsn(i.y);
		e2[x].push_back({i.y,i.id});
		e2[i.y].push_back({x,i.id});
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)e[i].clear(),pre1[i].clear(),pren[i].clear();
		for(int i=1,x,y,v;i<=m;i++){
			cin>>x>>y>>v;
			e[x].push_back({y,v,i});
			e[y].push_back({x,v,i});
			E[i]={x,y,v};
		}
		dijkstra(1,d1,pre1);
		dijkstra(n,d2,pren);
		ll len=d1[n];
		for(int i=1;i<=n;i++)e2[i].clear();
		for(int i=1;i<=m;i++){
			int x=E[i].x,y=E[i].y,v=E[i].v;
			if(d1[x]+v+d2[y]==len){
				e2[x].push_back({y,i});
				e2[y].push_back({x,i});
			}
			if(d1[y]+v+d2[x]==len){
				e2[x].push_back({y,i});
				e2[y].push_back({x,i});
			}
		}
		for(int i=1;i<=n;i++)dfn[i]=low[i]=0;
		for(int i=1;i<=m;i++)brg[i]=0;
		tarjan(1,0);
		for(int i=1;i<=n;i++)v2[i]=0,e2[i].clear(),dfn[i]=low[i]=0;
		for(int i=1;i<=m;i++)vis[i]=brg[i],brg[i]=0;
		int fl=0;
		for(int i=1;i<=m;i++){
			int x=E[i].x,y=E[i].y,v=E[i].v;
			if(d1[x]+v+d2[y]==len+1){
				e2[x].push_back({y,i});
				e2[y].push_back({x,i});
				dfs1(x);
				dfsn(y);
				fl=1;
			}
			if(d1[y]+v+d2[x]==len+1){
				e2[x].push_back({y,i});
				e2[y].push_back({x,i});
				dfs1(y);
				dfsn(x);
				fl=1;
			}
		}
		if(!fl){
			cout<<"0\n\n";
			continue;
		}
		tarjan(1,0);
		vector<int> ans;
		for(int i=1;i<=m;i++){
			if(vis[i]&&!brg[i])ans.push_back(i);
		}
		cout<<ans.size()<<'\n';
		for(int i:ans){
			cout<<i<<" ";
		}
		cout<<'\n';
	}
	return 0;
}
      • 0
        @ 2026-5-19 10:46:33

        多测记得清空

        #include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
const int N=3e5+10,inf=1e18;
vector<PII>G[N],G2[N];
struct node{int x,y,c;}e[N];
int n,m,d[N],v[N],a[N],b[N],vv[N];map<PII,int>mp;
vector<int>pre[N],pre1[N];
void dij1(int st)
{
	priority_queue<PII,vector<PII>,greater<PII>>q;
	for(int i=1;i<=n;i++)d[i]=inf,v[i]=0;
	d[st]=0;q.push({0,st});
	while(!q.empty())
	{
		int x=q.top().se;q.pop();
		if(v[x])continue;v[x]=1;
		for(auto i:G[x])
		{
			int y=i.fi,w=i.se;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				pre[y].clear();pre[y].push_back(x);
				q.push({d[y],y});
			}
			else if(d[y]==d[x]+w)pre[y].push_back(x);
		}
	}
}
void dij2(int st)
{
	priority_queue<PII,vector<PII>,greater<PII>>q;
	for(int i=1;i<=n;i++)d[i]=inf,v[i]=0;
	d[st]=0;q.push({0,st});
	while(!q.empty())
	{
		int x=q.top().se;q.pop();
		if(v[x])continue;v[x]=1;
		for(auto i:G[x])
		{
			int y=i.fi,w=i.se;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				pre1[y].clear();pre1[y].push_back(x);
				q.push({d[y],y});
			}
			else if(d[y]==d[x]+w)pre1[y].push_back(x);
		}
	}
}
int dfn[N],low[N],cut[N],tsp,cnt;
void tarjan(int x,int f,int k)
{
	dfn[x]=low[x]=++tsp;
	for(auto i:G2[x])if(i.se!=f)
	{
		int y=i.fi,id=i.se;
		if(dfn[y]==0)
		{
			tarjan(y,id,k);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x])cut[id]=k;
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int v1[N],v2[N],vvv[N];
void make(int x)
{
	if(v1[x])return;v1[x]=1;
	for(int y:pre[x])
	{
		make(y);
		int id=mp[{x,y}];
		if(vvv[id])continue;vvv[id]=1;
		G2[x].push_back({y,id});
		G2[y].push_back({x,id});
	}
}
void make1(int x)
{
	if(v2[x])return;v2[x]=1;
	for(int y:pre1[x])
	{
		make1(y);
		int id=mp[{x,y}];
		if(vvv[id])continue;vvv[id]=1;
		G2[x].push_back({y,id});
		G2[y].push_back({x,id});
	}
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		G[i].clear(),G2[i].clear(),pre[i].clear(),pre1[i].clear();	
	for(int i=1;i<=m;i++)
		vv[i]=cut[i]=v1[i]=v2[i]=vvv[i]=0;
	tsp=cnt=0,mp.clear();
	for(int i=1;i<=m;i++)
	{
		int x,y,c;cin>>x>>y>>c;e[i]={x,y,c};
		G[x].push_back({y,c});
		G[y].push_back({x,c});
		mp[{x,y}]=mp[{y,x}]=i;
	}
	dij1(1);for(int i=1;i<=n;i++)a[i]=d[i];
	int len=d[n];
	dij2(n);for(int i=1;i<=n;i++)b[i]=d[i];
	deque<int>q;q.push_back(n);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int y:pre[x])
		{
			int id=mp[{x,y}];
			G2[x].push_back({y,id});
			G2[y].push_back({x,id});
			if(!vv[y])vv[y]=1,q.push_back(y);
		}
	}
	for(int i=1;i<=n;i++)dfn[i]=low[i]=0;
	tarjan(1,0,1);
	for(int i=1;i<=n;i++)dfn[i]=low[i]=0,G2[i].clear();
	bool bk=0;
	for(int i=1;i<=m;i++)
	{
		int x=e[i].x,y=e[i].y,w=e[i].c;
		if(a[x]+b[y]+w==len+1)
		{
			bk=1;
			make(x);make1(y);
			int id=mp[{x,y}];
			if(vvv[id])continue;vvv[id]=1;
			G2[x].push_back({y,id});
			G2[y].push_back({x,id});
		}
		if(a[y]+b[x]+w==len+1)
		{
			bk=1;
			make(y);make1(x);
			int id=mp[{x,y}];
			if(vvv[id])continue;vvv[id]=1;
			G2[x].push_back({y,id});
			G2[y].push_back({x,id});
		}
	}
	if(!bk)
	{
		cout<<0<<"\n\n";
		return ;
	}
	tarjan(1,0,0);
	vector<int>ans;
	for(int i=1;i<=m;i++)if(cut[i])ans.push_back(i);
	cout<<ans.size()<<'\n';
	for(int y:ans)cout<<y<<' ';cout<<'\n';
}
signed main()
{
	int t;cin>>t;
	while(t--)solve();
	return 0;
}
        • 1

        [COCI 2022/2023 #3] Baltazar

        信息

        ID
        7437
        时间
        4000ms
        内存
        512MiB
        难度
        9
        标签
        递交数
        15
        已通过
        3
        上传者
        1. Language
        2. 兼容模式
        3. 主题
        3. Worker 0, 10ms
        4. Powered by Hydro v5.0.1 Community