图论水题日记

发布于：2025-07-26 ⋅ 阅读:(16) ⋅ 点赞:(0)

cf1805D

题意

给定一棵树，规定dis(u,v)≥kdis(u,v) \geq kdis(u,v)≥k时(u,v)(u,v)(u,v)之间存在一条无向边，求k=(1,2,...n)k=(1,2,...n)k=(1,2,...n)时图中的连通块个数

思路

  • 前置知识：树上一点到其最远的点一定是树直径的两个端点之一
  • 若一个点到其最远的点大于k，那么其一定是孤立点，我们可以计算出每个点在k为多少时变成孤立点，答案即为前缀和
  • 所以计算出直径两端点之后再计算出所有点到两端点的距离，则i点在k=max(dis1[i],dis2[i])+1k=max(dis1[i],dis2[i])+1k=max(dis1[i],dis2[i])+1时变成孤立点
  • 需要注意k=0时，连通块为1个，k>直径时，所有点都孤立，即n个连通块

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1e5+10;
vector<int>e[N];

void solve()
{
	int n;cin>>n;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
		e[b].pb(a);
	}
	
	vector<int>dep(n+1,-1);
	int root1,root2;
	int deepest=1;
	
	auto dfs=[&](auto && dfs,int u,int fa)->void
	{
		dep[u]=dep[fa]+1;
		if(dep[u]>dep[deepest]) deepest=u;
		for(auto ed:e[u])
		{
			if(ed==fa) continue;
			dfs(dfs,ed,u);
		}
	};
	
	
	dfs(dfs,1,0);
	root1=deepest;
	dfs(dfs,root1,0);
	root2=deepest;
	
	auto dfs1=[&](auto && dfs1,vector<int>&dis,int u,int fa)->void
	{
		dis[u]=dis[fa]+1;
		for(auto ed:e[u])
		{
			if(ed==fa) continue;
			dfs1(dfs1,dis,ed,u);
		}
	};
	
	vector<int>dis1(n+1,-1);
	dis1[root1]=0;
	dfs1(dfs1,dis1,root1,0);
	
	vector<int>dis2(n+1,-1);
	dis2[root2]=0;
	dfs1(dfs1,dis2,root2,0);
	
	//cout<<root1<<" "<<root2<<endl;
	//for(int i=1;i<=n;i++) cout<<dis1[i]<<" "<<dis2[i]<<endl;
	
	vector<int>ans(n+1);//k为i时增加孤点数
	for(int i=1;i<=n;i++) ans[max(dis1[i],dis2[i])+1]++;
	ans[0]=1;
	for(int i=1;i<=n;i++)
	{
		ans[i]+=ans[i-1];
		cout<<(i>dep[root2] ? n : ans[i])<<" \n"[i==n];
	}
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

cf1775D

题意

给定n个节点，若gcd(ai,aj)!=1gcd(a_i,a_j)!=1gcd(ai​,aj​)!=1则ai,aja_i,a_jai​,aj​之间存在一条无向边，且所有边权都为1，给定两点，求这两点的最短路上的节点个数已经路径

1≤n≤3⋅1051 \leq n \leq 3 \cdot 10^51≤n≤3⋅105
1≤ai≤3⋅1051 \leq a_i \leq 3 \cdot 10^51≤ai​≤3⋅105

思路

  • 考虑暴力做法,枚举所有i,ji,ji,j对其求gcd后建边后跑最短路，则时间复杂度是O(n2log)O(n^2log)O(n2log)不肯通过，考虑优化发现所有具备同一个因数的点都会连一条边，不妨将每个因数建立虚点，将所有包含此因数的点对其连边建图，这样做时间复杂度为O(nn)O(n \sqrt n)O(nn ​),但实际上我们只需要关注质因数即可，两个不互质的数一定有共同的质因数，这样时间复杂度为O(nlogn)O(nlogn)O(nlogn)
  • 具体做法为对于所有aia_iai​分解质因数，然后将其与质因数连边，一条边权为1的出边，一条边权为0的入边，然后跑dij求最短路即可

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=3e5+10;
struct edge{
	int v,w;
};
vector<edge>e[N<<1];


void solve()
{
	int n;cin>>n;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int st,ed;
	cin>>st>>ed;
	
	for(int i=1;i<=n;i++)
	{
		int x=a[i];
		for(int j=2;j*j<=x;j++)
		{
			if(x%j==0)
			{
				while(x%j==0) x/=j;
				e[i].pb({j+N,1});
				e[j+N].pb({i,0});
			}
		}
		if(x!=1)
		{
			e[i].pb({x+N,1});
			e[x+N].pb({i,0});
		}
	}
	
	priority_queue<PII,vector<PII>,greater<PII>>q;
	vector<int>dis(N<<1,inf);
	dis[st]=0;
	q.push({0,st});
	vector<int>vis(N<<1);
	map<int,int>last;
	
	
	while(!q.empty())
	{
		auto [cost,cur]=q.top();
		q.pop();
		
		if(vis[cur]) continue;
		vis[cur]=1;
		
		for(auto [v,w]:e[cur])
		{
			if(cost+w<dis[v])
			{
				last[v]=cur;
				dis[v]=cost+w;
				q.push({dis[v],v});
			}
		}
	}
	
	
	if(dis[ed]==inf) {cout<<-1<<endl;return;}
	vector<int>path;
	auto dfs=[&](auto &&dfs,int u)->void
	{
		if(u<N) path.pb(u);
		if(u==st) return;
		dfs(dfs,last[u]);
	};
	
	dfs(dfs,ed);
	reverse(all0(path));
	cout<<path.size()<<endl;
	for(auto t:path) cout<<t<<" ";
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

cf118E

题意

给定一张nnn个点,mmm条边的无向图，是否存在一种将其变为有向图的方法，使该图是一个强连通分量

思路

若图中存在割边则一定无解，使用tarjan判断图中是否有割边，可以发现有向边的构造方法恰为tarjan的访问顺序

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=2e6+10;
vector<int>head(N,-1);
int idx=0;
struct edge{
	int to,next;
}e[N];

int cnt;
int low[N],dfn[N],tot;
vector<PII>ans;

void add(int u,int v)
{
	e[idx].to=v;
	e[idx].next=head[u];
	head[u]=idx++;
}

void tarjan(int x,int fa)
{
	low[x]=dfn[x]=++tot;
	for(int i=head[x];~i;i=e[i].next)
	{
		int y=e[i].to;
		if(y==fa) continue;
		if(!dfn[y])
		{
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			ans.pb({x,y});
			if(low[y]>dfn[x]) cnt++;
		}
		else if(dfn[y]<dfn[x])
		{
			low[x]=min(low[x],dfn[y]);
			ans.pb({x,y});
		}
	}
}

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	
	tarjan(1,0);
	
	if(cnt) {cout<<0<<endl;return;}
	
	for(auto [x,y]:ans)
	{
		cout<<x<<" "<<y<<endl;
	}
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

cf999E

题意

nnn个点，mmm条边的有向图，如果要满足点sss可以到达所有点，需要添加几条边

思路

  • 对于一个强连通分量内的点只要可以到达其中一个，那么全部都可达
  • 观察样例可以发现答案即为缩点后入度为0的点的个数
  • 但需要注意s点所在连通块不纳入计算

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=5010;
vector<int>e[N];
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

vector<int>e1[N];

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed])
		{
			low[x]=min(low[x],dfn[ed]);
		}
	}
	
	if(dfn[x]==low[x])
	{
		int y;cnt++;
		do
		{
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
			++siz[cnt];
		}while(y!=x);
	}
}


void solve()
{
	int n,m,s;
	cin>>n>>m>>s;
	
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	//cout<<cnt<<endl;
	vector<int>din(n+1);
	for(int i=1;i<=n;i++)
	{
		for(auto ed:e[i])
		{
			if(scc[ed]!=scc[i])
			{
				e1[scc[i]].pb(scc[ed]);
				din[scc[ed]]++;
			}
		}
	}
	
	int ans=0;
	vector<int>st(n+1);
	for(int i=1;i<=cnt;i++)
	{
		if(i==scc[s]) continue;
		if(!din[i])
		{
			if(!st[i]) ans++;
			st[i]=1;
		}
	}
	
	cout<<ans<<endl;
	
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

cf25c

题意

给定nnn个点的最短距离矩阵(1≤n≤300)(1 \leq n \leq 300)(1≤n≤300),以及k条路径，代表新建一条aaa到bbb边权为ccc的路径，求每次新建路径之后所有点对的最短路之和

思路

由数据范围不难想到floyd,若每次新建路径边权小于之前的边权，就尝试对所有经过a,ba,ba,b点和b,ab,ab,a点的最短路径进行更新

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  



void solve()
{
	int n;cin>>n;
	vector<vector<ll>>dis(n+1,vector<ll>(n+1));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cin>>dis[i][j];
	}
	
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++) ans+=dis[i][j];
	}
	
	
	
	int m;cin>>m;
	while(m--)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		if(c>=dis[a][b]) {cout<<ans<<" ";continue;}
		dis[a][b]=dis[b][a]=c;
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i==j) continue;
				dis[i][j]=min(dis[i][j],dis[i][a]+dis[a][b]+dis[b][j]);
				dis[i][j]=min(dis[i][j],dis[i][b]+dis[b][a]+dis[a][j]);
			}
		}
		ans=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++) ans+=dis[i][j];
		}
		cout<<ans<<" ";
	}
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

cf1272E

题意

给定n个元素的数组，若i+ai≤ni+a_i \leq ni+ai​≤n则iii与i+aii+a_ii+ai​之间存在一条代价为1的边，若i−ai≥1i-a_i \geq 1i−ai​≥1则则iii与i−aii-a_ii−ai​之间存在一条代价为1的边，对于每个aia_iai​求到达与其奇偶性不同的点的最小步数

思路

  • 考虑多源bfs，要求解偶数点到奇数点的最小步数，从所有奇数点出发，走反边跑bfs，奇数点到偶数点同理，相反即可

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=2e5+10;

vector<int>e[N];

void solve()
{
	int n;cin>>n;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=n;i++)
	{
		if(i+a[i]<=n) e[i+a[i]].pb(i);
		if(i-a[i]>=1) e[i-a[i]].pb(i);
	}
	
	
	vector<int>ans(n+1,-1),dis(n+1,1e9);
	queue<int>q;
	
	
	auto bfs=[&]()
	{
		while(!q.empty())
		{
			auto t=q.front();
			q.pop();
			
			for(auto ed:e[t])
			{
				if(dis[t]+1<dis[ed])
				{
					dis[ed]=dis[t]+1;
				    q.push(ed);
				}
				
			}
		}
	};
	
	
	for(int i=1;i<=n;i++)
	{
		if(a[i]%2==0)
		{
			q.push(i);
			dis[i]=0;
		}
	}
	bfs();
	for(int i=1;i<=n;i++)
	{
		if(a[i]&1) ans[i]=dis[i];
	}
	
	fill(all(dis),1e9);
	for(int i=1;i<=n;i++)
	{
		if(a[i]%2)
		{
			q.push(i);
			dis[i]=0;
		}
	}
	bfs();
	
	for(int i=1;i<=n;i++)
	{
		if(a[i]%2==0) ans[i]=dis[i];
	}
	
	for(int i=1;i<=n;i++) cout<<(ans[i]==1e9?-1:ans[i])<<" \n"[i==n];
	
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

cf1872F

题意

nnn个动物，其害怕的动物为aia_iai​,其价值为cic_ici​，如果一个动物被卖出时其害怕的动物还没有被卖出，则可以得到2∗ci2*c_i2∗ci​的收益，反之得到cic_ici​的收益，求一个排列代表可以获得最大收益的卖出动物的顺序

思路

我们把每个点向其害怕的点连一条出边，由于有n个点n条边，且每个点只有一条出边，所以图中必定有环，不难发现对于不在环内的点按拓扑序卖出更优，而对于在环内的点，贪心的想一定最后卖cic_ici​最小的点，这样环上的其他点都能得到2∗ci2*c_i2∗ci​的收益

  • 这题显然用拓扑排序做更快，自己用tarjan搞了半天，其实tarjan有一个很重要的性质，其scc出栈的顺序就是逆拓扑序，所以我们可以找到环上价值最小的点，将其加入答案数组中，由于这样做为逆拓扑排序，最后reverse输出即可

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1e5+10;
vector<int>e[N];

int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

int c[N];

vector<int>ans;

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed])
		{
			low[x]=min(low[x],dfn[ed]);
		}
	}
	
	if(dfn[x]==low[x])
	{
		int y;
		++cnt;
		vector<int>circle;
		do
		{
			y=stk[top--];
			instk[y]=0;
			circle.pb(y);
			scc[y]=cnt;
			++siz[cnt];
			//cout<<y<<endl;
		}while(y!=x);
		int len=circle.size();
		int mn=1e9;
		for(auto x:circle) mn=min(mn,c[x]);
		
		int pos=-1;
		for(int i=0;i<len;i++) if(c[circle[i]]==mn) {pos=i;break;}
		
		for(int i=pos;i<len;i++) ans.pb(circle[i]);
		for(int i=0;i<pos;i++) ans.pb(circle[i]);
	}
	
	
}


void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		dfn[i]=low[i]=0;
		stk[i]=instk[i]=0;
		scc[i]=siz[i]=0;
		tot=top=cnt=0;
		c[i]=0;
		ans.clear();
		e[i].clear();
	}
	
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		e[i].pb(x);
	}
	for(int i=1;i<=n;i++) cin>>c[i];
	
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	
	reverse(all0(ans));
	for(auto t:ans) cout<<t<<" ";
	cout<<endl;
	
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--)
	solve();
	
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布