首页 > 其他分享 >图论总结——拓扑排序

图论总结——拓扑排序

时间：2024-01-21 23:56:15浏览次数：24  
标签：nxt 图论 return int 拓扑 cnt cnt2 排序 head

图论总结——拓扑排序

例 \(1\) ：排水系统（不是很模板的模板题）

思路

模板题，但是要进行分数约分，所以又不是很模板直接进行计算即可。注意计算过程中很可能爆 \(long ~~ long\) 类型范围，需要用 \(int128\) 类型进行存储。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 3e5 + 50;
int n,m,cnt;
int head[N],in[N],deg[N],res[N],tot;
__int128 gcd(__int128 x,__int128 y)
{
	if(y == 0)
		return x;
	return gcd(y,x%y);
}
struct edge{
	int to,nxt;
}e[N];
struct ans{
	__int128 p,q;
}ans[N];
void add(int u,int v)
{
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
	return;
}
void write(__int128 n) {
	if(n >= 10)	write(n/10);
	putchar(n%10 + '0');
}
signed main()
{
	scanf("%lld %lld",&n,&m);
	for(int i = 1;i <= n;i++)
	{
		int x;
		scanf("%lld",&x);
		if(x == 0)
			res[++tot] = i;
		deg[i] = x;
		while(x--)
		{
			int y;
			scanf("%lld",&y);
			add(i,y);
			in[y]++;
		}
	}
	queue<int> q;
	for(int i = 1;i <= n;i++)
	{
		ans[i].q = 1;
		if(in[i] == 0)
			q.push(i),ans[i].p = 1;
	}
	while(!q.empty())
	{
		int x = q.front();q.pop();
		for(int i = head[x];i;i=e[i].nxt)
		{
			int y = e[i].to;
			__int128 yy = ans[x].p * ans[y].q;
			ans[y].p = ans[y].p * ans[x].q * deg[x];
			ans[y].q = ans[y].q * ans[x].q * deg[x];
			ans[y].p = ans[y].p + yy;
			__int128 xx = gcd(ans[y].q,ans[y].p);
			if(xx != 0)
				ans[y].q /= xx;ans[y].p /= xx;
			in[y]--;
			if(in[y] == 0)q.push(y);
		}
	}
	for(int i = 1;i <= tot;i++)
		write(ans[res[i]].p),putchar(' '),write(ans[res[i]].q),putchar('\n');
	return 0;
}

例 \(2\) ：菜肴制作

思路

套路题，考虑正面直接模拟不是很好做，现在考虑在反图上用贪心的思想做。

我们发现一个性质，如果现在有一个菜品编号较大的菜，那么我们就要尽量让菜品编号比它小的菜在它的前面，这样做肯定是满足题意的最优解。

利用上述性质就可以完成题目了，具体地，考虑反图代表的实际意义为，做这个菜之前要做哪些菜，所以进行拓扑的意义就为确定从最后依次往前做那些菜，那么我们就先在反图上求字典序最大的拓扑序，最后再反过来就一定为最终的解。

下面我们来进行证明这个贪心的正确性：

定义两个拓扑序中更优的一个为“最小序”更小的拓扑序。

求证：一个 DAG 的拓扑序中“最小序”最小的的一个拓扑序，是反向字典序最大的一个。

证明：

首先，当 \(∣V∣=1\) 时结论显然。

其次，假设结论对于 \(∣V∣<n\) 均成立。设图 \(G=(V,E)\) 中最小点编号为 \(x\)，其中 \(∣V∣=n\)，则整个点集分为两部分：

  • \(S =\left \{ z|存在一条路径~z \to x \right \}\)
  • \(T = V - S\)

特别地，有 \(x \in S\)。

\(Lemma~1\)：令 \(m:=|S|\)。则最小序最小的拓扑序 \(a\) 一定满足 \(\left \{a_x|1 \le x \le m\right \} = S\) 且 \(a_m = x\)。

证明：由于 \(x\) 在拓扑序上的位置越小，最小序就越小，所以 \(x\) 尽可能靠前更优。由拓扑序的定义，\(S - \left \{ x \right \}\) 中的所有点在拓扑序上一定排在 \(x\) 之前。

所以 \(a_m = x\) 是 \(p \ge m\) 的充分条件。

现将整个图可以分成三个子图，其点集分别为 \(\left \{ x \right \}\) 、\(S-\left \{ x \right \}\) 和 \(T\)。

由于 \(|S|+|T|=n\)，所以 \(|S− \left \{ x \right \}|,|T| < n\)，由假设得其结论成立。

因为 \(x\) 是编号最小的，将 \(x\) 向后移不能获得更大的反向字典序。而 \(S− \left \{ x \right \} ,T\) 的结论已证。于是对于图 \(G\) 结论成立。

所以对于任意的 DAG，由数学归纳法得结论均成立。

证毕。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 50;
int T;
int n,m,cnt,head[N],in[N],ans[N],tot,cnt2,head2[N];
struct edge{
	int to,nxt;
}e2[N];
void add2(int u,int v)
{
	e2[++cnt2].to = v;
	e2[cnt2].nxt = head2[u];
	head2[u] = cnt2;
	return;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		tot = 0;cnt2 = 0;
		scanf("%d %d",&n,&m);
		for(int i = 1;i <= n;i++)in[i] = 0,ans[i] = 0,head2[i] = 0;
		for(int i = 1;i <= m;i++)
		{
			int u,v;
			scanf("%d %d",&u,&v);
			add2(v,u);
			in[u]++;
		}
		priority_queue<int> q;
		for(int i = 1;i <= n;i++)
			if(in[i] == 0)
				q.push(i);
		int cntt = 0;
		while(!q.empty())
		{
			int x = q.top();q.pop();
			cntt++;
			ans[++tot] = x;
			for(int i = head2[x];i;i = e2[i].nxt)
			{
				int y = e2[i].to;
				in[y]--;
				if(in[y] == 0)q.push(y);
			}
		}
		if(cntt != n)
		{
			printf("Impossible!\n");
			continue;
		}
		for(int i = tot;i >= 1;i--)
			printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}

例 \(3\)：PUS (Pustynia)

思路

题目似乎看起来像数学题，其实不然，这与图论最短路中的一个经典应用有关——差分约束。

我们利用最短路的性质，如果一个整数 \(a_u \ge a_v\) ，那么就可以将点 \(u\) 连向点 \(v\) 且边的权值为 \(-1\)。然后我们就可以开心地根据题意模拟对每个点进行建边即可。

显然直接按照题意模拟建边的复杂度就为 \(\mathcal{O}(n ^ 3)\) 级别的。不能接受。

考虑进行一个小优化，每一个区间创立一个虚拟节点，其中 \(k\) 个点向虚拟节点连边权为 \(-1\) 的单向边，这个虚拟节点再向剩余 \(r-l+1-k\) 个点连边权为 \(0\) 的单向边。但很可惜，这样做时间复杂度也会炸掉，因为单次区间操作复杂度为 \(\mathcal{O}(n)\) 的，一共有 \(m\) 次操作，所以复杂度就为 \(\mathcal{O}(n ^ 2)\) 级别的。

思考还可以怎么优化，看到一个点向一个区间连边，可以使用线段树高效解决此类建图问题，最终时间复杂度为 \(\mathcal{O}(n~log_2~n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 6e6 + 50,K = 6e5 + 50;

int n,s,m,cnt,tot;
int head[K],a[K],b[K],in[K];
bool vis[K];
int dis[K];
struct edge{
	int to,nxt,w;
}e[N];
void add(int u,int v,int f)
{
	e[++cnt].to = v;
	e[cnt].w = f;
	e[cnt].nxt = head[u];
	head[u] = cnt;
	in[v]++;
	return;
}
void build(int p,int l,int r)
{
	tot = max(tot,p);
	if(l == r)
	{
		a[l] = p;
		return;	
	}
	add(p,p * 2,0);add(p,p * 2 + 1,0);
	int mid = (l + r) >> 1;
	build(p * 2,l,mid);build(p * 2 + 1,mid + 1,r);
	return;
}
void update(int p,int l,int r,int x,int y,int k)
{
	if(x <= l && r <= y)
	{
		add(k,p,0);
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid)update(p * 2,l,mid,x,y,k);
	if(y > mid)update(p * 2 + 1,mid + 1,r,x,y,k);
	return;
}
int main()
{
	cnt = 0;
	scanf("%d %d %d",&n,&s,&m);
	build(1,1,n);
	for(int i = 1;i <= s;i++)
	{
		int p,d;
		scanf("%d %d",&p,&d);
		b[a[p]] = d;dis[a[p]] = d;
	}
	for(int i = 1;i <= m;i++)
	{
		int l,r,k;
		scanf("%d %d %d",&l,&r,&k);
		tot++;
		int last = l;
		for(int j = 1;j <= k;j++)
		{
			int x;
			scanf("%d",&x);
			add(a[x],tot,-1);
			if(last < x)update(1,1,n,last,x - 1,tot);
			last = x + 1;
		}
		if(last <= r)update(1,1,n,last,r,tot);
	}
	queue<int> q;
	for(int i = 1;i <= tot;i++)
	{
		if(in[i] == 0)q.push(i);
		if(dis[i] == 0)dis[i] = 1e9;
	}
	while(!q.empty())
	{
		int x = q.front();q.pop();vis[x] = 1;
		for(int i = head[x];i;i = e[i].nxt)
		{
			int v = e[i].to;
			dis[v] = min(dis[v],dis[x] + e[i].w);
			if(b[v] && dis[v] < b[v])
			{
				printf("NIE\n");
				return 0;
			}
			in[v]--;
			if(in[v] == 0)q.push(v);
		}
	}
	for(int i = 1;i <= tot;i++)
	{
		if(dis[i] < 1 || vis[i] == 0)
		{
			printf("NIE\n");
			return 0;
		}
	}
	printf("TAK\n");
	for(int i = 1;i <= n;i++)
		printf("%d ",dis[a[i]]);
	return 0;
}

例 \(4\)：Elaxia的路线

思路

先分别把关于两对起点和终点的最短路图求出来，再取交集，然后进行 \(topo\)。当然直接这样做会有问题，因为最短路图是无向图，无法 \(topo\) 求出最短路图的交集的最长路。

那么可以考虑对求出来的最短路图的交集搞个方向，这样就能进行 \(topo\) 了。具体地，我们发现一个性质最终答案的路径长度不可能同时包含并行和相遇的边，也不可能不存在一条连续的包含并行和相遇的边的路径。正确性显然。

那么我们就可以进行分类讨论，固定一对起点和终点的最短路图的方向，另外一对起点和终点再判断是并行还是相遇的类型。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2050,M = 6e5 + 50;
int n,m,cnt,cnt2;
int s1,s2,t1,t2;
int head[N],head2[N],in[N];
ll dis1[N],dis2[N],dis3[N],dis4[N],F[N];
bool vis1[N],vis2[N],mark[N];
struct edge{
	int to,nxt,w;
}e[M],e2[M];
void add(int u,int v,int f)
{
	e[++cnt].w = f;
	e[cnt].nxt = head[u];
	e[cnt].to = v;
	head[u] = cnt;
	return;
}
void add2(int u,int v,int f)
{
	e2[++cnt2].w = f;
	e2[cnt2].nxt = head2[u];
	e2[cnt2].to = v;
	head2[u] = cnt2;
	return;
}
struct node{
	int pos,val;
	bool operator > (const node &x)const{
		return val > x.val;
	}
};
void dij(int s)
{
	priority_queue<node,vector<node>,greater<node> >q;
	dis1[s] = 0;
	q.push(node{s,dis1[s]});
	while(!q.empty())
	{
		node t = q.top();q.pop();
		int x = t.pos;
		if(vis1[x])continue;
		vis1[x] = 1;
		for(int i = head[x];i;i = e[i].nxt)
		{
			int v = e[i].to;
			if(dis1[v] > dis1[x] + e[i].w)
			{
				dis1[v] = dis1[x] + e[i].w;
				q.push(node{v,dis1[v]});
			}
		}
	}
	return;
}
void dij2(int s)
{
	priority_queue<node,vector<node>,greater<node> >q;
	dis2[s] = 0;
	q.push(node{s,dis2[s]});
	while(!q.empty())
	{
		node t = q.top();q.pop();
		int x = t.pos;
		if(vis2[x])continue;
		vis2[x] = 1;
		for(int i = head[x];i;i = e[i].nxt)
		{
			int v = e[i].to;
			if(dis2[v] > dis2[x] + e[i].w)
			{
				dis2[v] = dis2[x] + e[i].w;
				q.push(node{v,dis2[v]});
			}
		}
	}
	return;
}
int main()
{
	cnt = 0;cnt2 = 0;
	scanf("%d %d",&n,&m);
	scanf("%d %d %d %d",&s1,&t1,&s2,&t2);
	for(int i = 1;i <= n;i++)
	{
		dis1[i] = 1e18;
		dis2[i] = 1e18;
		head[i] = 0;
		head2[i] = 0;
		vis1[i] = 0;
		vis2[i] = 0;
	}
	for(int i = 1,u,v,w;i <= m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dij(s1);dij2(s2);
	for(int i = 1;i <= n;i++)
	{
		dis3[i] = dis1[i];
		dis4[i] = dis2[i];
		dis1[i] = 1e18;
		dis2[i] = 1e18;
		vis1[i] = 0;
		vis2[i] = 0;
	}
	dij(t1);dij2(t2);
	for(int i = 1;i <= n;i++)
	{
		swap(dis1[i],dis3[i]);
		swap(dis2[i],dis4[i]);
	}
	queue<int> q;
	ll ans = -1e18;
	for(int i = 1;i <= n;i++)
	{
		for(int j = head[i];j;j = e[j].nxt)
		{
			int v = e[j].to,w = e[j].w;
			if(dis1[i] + dis3[v] + w == dis1[t1])
				if(dis2[i] + dis4[v] + w == dis2[t2])
					add2(i,v,w),in[v]++,mark[i] = 1,mark[v] = 1;
		}
	}
	for(int i = 1;i <= n;i++)
		if(in[i] == 0 && mark[i])q.push(i);
	while(!q.empty())
	{
		int x = q.front();q.pop();
		for(int i = head2[x];i;i = e2[i].nxt)
		{
			int v = e2[i].to;
			F[v] = max(F[v],F[x] + e2[i].w);
			in[v]--;
			if(in[v] == 0)q.push(v);
		}
	}
	for(int i = 1;i <= n;i++)
		ans = max(ans,F[i]);
	memset(head2,0,sizeof(head2));
	memset(F,0,sizeof(F));
	memset(in,0,sizeof(in));
	memset(mark,0,sizeof(mark));
	cnt2 = 0;
	for(int i = 1;i <= n;i++)
	{
		for(int j = head[i];j;j = e[j].nxt)
		{
			int v = e[j].to,w = e[j].w;
			if(dis1[i] + dis3[v] + w == dis1[t1])
				if(dis2[v] + dis4[i] + w == dis2[t2])
					add2(i,v,w),in[v]++,mark[i] = 1,mark[v] = 1;
		}
	}
	for(int i = 1;i <= n;i++)
		if(in[i] == 0 && mark[i])q.push(i);
	while(!q.empty())
	{
		int x = q.front();q.pop();
		for(int i = head2[x];i;i = e2[i].nxt)
		{
			int v = e2[i].to;
			F[v] = max(F[v],F[x] + e2[i].w);
			in[v]--;
			if(in[v] == 0)q.push(v);
		}
	}
	for(int i = 1;i <= n;i++)
		ans = max(ans,F[i]);
	printf("%lld\n",ans);
	return 0;
}

例 \(5\)：数列恢复

思路

咕咕咕

标签：nxt,图论,return,int,拓扑,cnt,cnt2,排序,head
From： https://www.cnblogs.com/CQWYB/p/17978736

相关文章

  • 桶排序 -解决了什么问题
    桶排序法的优点高效的时间复杂度：在均匀分布的情况下，桶排序的平均时间复杂度接近线性，具有较高的排序效率。这是因为桶排序将元素分散到多个桶中，每个桶独立地进行排序，而不需要像比较排序算法那样逐个比较和交换元素。适用于外部排序：桶排序适用于需要排序的数据量非常大，无法全部......
  • sort排序疑惑
    今天做到了一道题是这样的：病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：1.老年人(年龄≥60岁)比非老年人优先看病。2.老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。3.非老年人按登记的先后顺序看病。输入格式第1行，输入一个小于10......
  • 排序算法的性能比较
    写在前面菜鸡博主最近放寒假了，打算接下来的一段时间内回顾一下以前学过的一些知识，也是为考研做一些准备吧。很菜，勿喷，希望能和大家一起学习，共同进步！主要目标和具体要求目标排序对于数据处理是一项十分重要和基础的工作。采用如下算法实现排序功能：插入排序、交换排序、选择排序......
  • 自定义排序
    问题：如何对数据进行自定义排序函数解决：=SORTBY(A2:A21,MATCH(A2:A21,E2:E11,))按自定义序列排序：选取数据中任一单元格》数据（或开始）》排序》自定义排序》勾选包含标题》次序》自定义序列》选取》确定》确定设置自定义序列：选取数据》文件》选项》自定义序列》从单元格导......
  • 排序算法与查找
    1.排序1.1冒泡排序冒泡排序，就是将相邻两个元素进行比较，如果前面那个元素和后面那个元素进行比较，如果前面元素比后者元素大，则进行交换位置。下面举例： 由图可知，共有5个元素，进行了四轮比较，假设有n个元素，则进行n-1轮比较(外部循环)。内部元素比较变化:第一轮把最大的元素给去......
  • compareTo、Comparator、TreeSet排序那些事
    前言：对于后端开发而言，学会对数据的自定义排序还是十分有必要的。需要用到排序的场景也是很多的，什么排行版展示、利用时间+别的条件排序、还有预接单的数据就是要展示在已接单的数据前面这种需求、等等。总之很重要的！一：对集合排序对以下的数据做展示顺序排序：未接单>预接单>已接单。（......
  • 最少交换次数 置换环 LeetCode 2471. 逐层排序二叉树所需的最少操作数目
    voidMain(){ varroot=newTreeNode(1) { left=newTreeNode(3) { left=newTreeNode(7), right=newTreeNode(6) }, right=newTreeNode(2) { left=newTreeNode(5), right=newTreeNode(4) } }; varr=newSolution().Minimu......
  • 148.排序链表
    1.题目介绍给你链表的头结点head，请将其按升序排列并返回排序后的链表。示例1：输入：head=[4,2,1,3]输出：[1,2,3,4]2.题解在147.对链表进行插入排序中我们使用插入排序的方式对于链表进行排序插入排序的时间复杂度是O(n^2)，其中n是链表的长度。这道题考虑时间复杂度......
  • 图论练习笔记
    P1606[USACO07FEB]LilypadPondG首先跳的过程肯定不会经过相同位置，所以之前经过的位置可以视为原状态，所以可以把添加的莲花数量视为当前路径长度，问题也就转化成了最短路计数。因为求的是添加莲花的方案数而不是经过路径的方案数，所以可以把已有的莲花连通块缩起来，以水格子为状......
  • Java - 排序
      冒泡排序升序排列importjava.util.Arrays;publicclassArrayDemo07{publicstaticvoidmain(String[]args){int[]a={1,4,5,3,14,12,51};int[]sort=sort(a);System.out.println(Arrays.toString(sort));}public......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99