12.22~12.23拓扑排序（字典序顺序），dij再理解，链式前向星，pta题目

存储图，就是要存储图的所有点的信息以及所有边的信息

在邻接矩阵中，矩阵行列代表边的起点终点，元素代表边的权重

在邻接表中，点数组存储第一条边的指针，编号，边里存储下一条边的指针、编号，以及边自身的信息

B3644 【模板】拓扑排序 / 家谱树

题目描述

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。

输入格式

第?11?行一个整数?�N（1≤�≤1001≤N≤100），表示家族的人数。接下来?�N?行，第?�i?行描述第?�i?个人的后代编号?��,�ai,j?，表示?��,�ai,j??是?�i?的后代。每行最后是?00?表示描述完毕。

输出格式

输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。

节点编号堆，保证字典序

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
//目的就是得到边的关系，以及每个点的入度信息，在输入的时候做了点手脚
vector<int>u[101];
priority_queue<int, vector<int>, greater<int>>q;
int n, du[101];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int t;
		while (cin>>t) {
			if (!t)break;
			u[i].push_back(t);
			du[t]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!du[i])q.push(i);
	}
	while (!q.empty()) {
		int cur = q.top();
		q.pop();
		cout << cur << " ";
		for (int i = 0; i < u[cur].size(); i++) {
			du[u[cur][i]]--;
			if (!du[u[cur][i]])q.push(u[cur][i]);
		}
	}
	return 0;
}

其余的话，用队列，数组都可以?

链式前向星版

struct edge {
	int v, w, next;
}e[10005];
int head[101], deg[101];
int n;
queue<int>q;
void t() {
	for (int i = 1; i <= n; i++) {
		if (!deg[i]) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = head[x]; i; i = e[i].next) {
			deg[e[i].v]--;
			if (!deg[e[i].v])q.push(e[i].v);
		}
	}
}

拓扑排序

一个工程被分解成n个子任务，编号为0至n-1。要完成整个工程需要完成所有的子任务。其中一些子任务必须先于另外一些子任务被完成。给定各子任务之间的先后关系，请编写程序给出一个合理的任务完成顺序，若工程不可行，程序亦能识别。

输入格式:

输入第一行为两个整数n和e，均不超过100。n表示子任务数。接下来e行，表示已知的两个子任务间的先后关系，每行为两个整数a和b，表示任务a必须先于任务b完成。

输出格式:

若工程不可行（一些子任务以自己为先决条件），输出“unworkable project”；若工程可行，输出为1行整数，每个整数后一个空格，为n个子任务的编号，表示子任务的完成顺序，如果有多种可能的顺序，则输出字典序最小者。

注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。

堆存储度为0的节点编号

这个堆并不是说就是堆优化，而只是说能保证最后排出来是一个字典序

实际上应用队列就是已经优化后了，即就是能保证每次遍历到的点都是度为0的点，而不用类似与dij的，需要遍历才能找到符合条件的了

精简版

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
priority_queue<int, vector<int>, greater<int>>q;
vector<int>u[101];
int n, e, cnt = 0;
int du[101];
int main() {
	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int s, v;
		cin >> s >> v;
		du[v]++;
		u[s].push_back(v);
	}
	for (int i = 0; i < n; i++) {
		if (!du[i])q.push(i);
	}
	while (!q.empty()) {
		int cur = q.top();
		q.pop();
		cnt++;
		cout << cur << " ";
		for (int i = 0; i < u[cur].size(); i++) {
			du[u[cur][i]]--;
			if (!du[u[cur][i]])q.push(u[cur][i]);
		}
	}
	if (cnt != n)cout << "unworkable project";
	return 0;
}

注释版

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n, e;
int du[101];
//邻接表就是每个节点，保存第一条边的指针，然后通过边的指向下一条边的指针去遍历完以该节点为起点的所有边
priority_queue<int, vector<int>, greater<int>>q;//存储的是节点编号，greater大于号，堆取反，则堆顶为最小，小顶堆
//即保证堆里的节点，按照编号从小到大严格排序
vector<int>g[101];//建立容器数组，还是相当于邻接表存储，只不过省略了边的指针信息，而是直接通过点去访问到以该点为起点的所有的边
//容器内存储的就是以该点为起点的所有边的编号,容器数组内的每个元素都是一个容器，容器内存储的就是边的编号
//由于是表示先后顺序，所以边没有权重，蕴含的信息唯有起点与终点，所以容器数组的容器里存储元素就是这条边的终点
void tpsort() {
	int num = 0;
	for (int i = 0; i < n; i++) {
		if (!du[i]) {
			q.push(i);//往堆里加入节点的编号,
		}
	}
	while (!q.empty()) {
		int u = q.top();
		cout << u << " ";
		q.pop();
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];//v表示以u为起点的第i条边的编号,为这条边所到达的终点
			du[v]--;
			if (!du[v]) {
				q.push(v);//队列里装的是迭代中入度为0的元素
			}
		}
		g[u].clear();//删边，表示遍历完后都取消掉
		num++;
	}
	if (num != n) {
		cout << "unworkable project";
	}
}
int main() {
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		du[b]++;
	}
	tpsort();
	return 0;
}

非堆存储度为0的节点（误）?

因为之前想到是加入的时候都是按字典序加入的，那么进行处理后，应该也都是字典序

//按照这样的顺序会有漏洞，比如一开始时可以做1，4，6，即初始时这些点入度为0
?? ?}//按照这个顺序，1先访问并删掉，假设2只需要完成1，那么1删完后2入队，但此时入队就会在4和6的后面
?? ?//而按照字典序的规则，此时应该完成2，所以就会不满足字典序
?? ?//所以满足入度为0的节点，存储时应该要以节点编号从小到大的方式去存储

即如果在处理队头元素时，队列不为空，如果队头元素处理产生了满足入队条件的，字典序更小的元素，那么它不会被优先处理，而是接着处理之前的队列元素，就会出现问题，就是应该要先处理字典序最小的元素

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int vnum, cnt = 0;
int e[105][105], d[105];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		e[u][v] = 1;
		d[v]++;
	}
	queue<int>q;
	for (int i = 0; i < n; i++) {
		if (!d[i])q.push(i);
	}
	vector<int>arr;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cnt++;
		arr.push_back(cur);
		for (int i = 0; i < n; i++) {
			if (e[cur][i]) {
				d[i]--;
				if (!d[i])q.push(i);
			}
		}
	}
	if (cnt == n) {
		for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
		}
	}
	else {
		cout << "unworkable project ";
	}
	return 0;
}

数组模拟，仿松弛（dij)，加break版

#include<vector>
using namespace std;
//采用松弛的思想
//用一个度数组，然后每次都是从头扫到尾，每次都只处理一个度为0的元素
//最多处理n次，即最外层迭代n轮
//处理就是访问这个节点的所有边，并对其终点的度数组做处理
//处理的条件是，未被处理过，且度为0
int du[101];
bool vis[101];
int g[101][101];
int n, e, cnt = 0;
vector<int>path;
int main() {
	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int u, v;
		cin >> u >> v;
		g[u][v] = 1;
		du[v]++;
	}
	for (int i = 1; i <= n; i++) {//外层循环n次
		for (int j = 0; j < n; j++) {//遍历度数组，从小到大，满足字典序
			if (!du[j] && !vis[j]) {//如果此时为0且未被访问过
				cnt++;
				vis[j] = 1;
				path.push_back(j);
				for (int k = 0; k < n; k++) {//访问处理这个点，把它联通的所有终点的度减去1
					if (g[j][k]) {
						du[k]--;
					}
				}
				break;//只处理一次，后续的的都不再处理，即目的是为了保证字典序，break掉当前遍历度数组的循环，进入下一轮迭代
				//就是说处理完后即使后续有度为0的也不再处理了，因为这次处理完后，可能前面就有了度为0的节点
				//如果不加break，就和那个直接队列的差不多了，但严格意义上还是不是的，
				//因为用队列的话，它的顺序是严格意义上的时间的层序遍历
				//而用数组模拟，就是混合的很乱的时间与次序都掺杂的顺序
				//比如123456，一开始能146，访问完1后能235，
				//那么队列的顺序就是146235，是层序的
				//而数组模拟就是1/23/4/5/6，即如果处理后在编号后是可以继续访问，而在编号前就不行，所以是层序与字典序混杂的一种方式
				//为了避免这种情况，就是每次访问度数组，只处理第一次遇到的，之后无论度发生什么变化都只从头开始遍历，这样就能保证严格意义上的字典序
			}
		}
	}
	if (cnt == n) {
		for (int i = 0; i < n; i++) {
			cout << path[i] << " ";
		}
	}
	else {
		cout << "unworkable project";
	}
	return 0;
}

之所以说是dij的思想，就是算法主体都是，外层为迭代，然后在每轮迭代中，找到符合要求的点，找到后进行处理，然后进行下一轮迭代。

不过这里拓扑的话，点的要求是满足入度为0，然后处理方式是把点联通的所有点的入度减1

dij的就是，要求找到dis里最小的，未被访问过的点，处理方式是根据这个点把联通的所有点进行松弛操作

这里加break,是把点的要求做进一步限制，即严格满足字典序，每轮迭代中只处理一次

复杂度对比分析?

?这个方法的复杂度为o(n^3)，即外面迭代n次，找度数组满足条件的最小字典序为n次，处理找到后的元素为n次；

可优化的地方就是找度数组满足字典序最小的时候，即用堆，让满足条件的节点按照字典序从小到大排，这样就是严格的字典序，每次只用处理队头元素；

由于无论如何都是要找齐N个节点，所以第一层迭代N次的复杂度是省不了的，处理的时候，可以不用遍历N次，采用邻接表可以，不过优化不了太多，只是在稀疏图时优化得多一点

struct edge {
	int target, start, w;
}e[10005];
struct cmp {
	bool operator()(edge a, edge b) {
		return a.w < b.w;
	}
};
int fa[105];
int n, m, ans = 0, cnt = 0;
priority_queue<edge, vector<edge>, cmp>q;
int find(int x) {
	if (x == fa[x]) {
		return x;
	}
	else {
		fa[x] = find(fa[x]);
		return fa[x];
	}
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
	fa[i] = i;
}
for (int i = 1; i <= m; i++) {
	cin >> e[i].start >> e[i].target >> e[i].w;
	q.push(e[i]);
}
while (!q.empty()) {
	int u = q.top().start, v = q.top().target;
	int fu = find(u), fv = find(v);
	q.pop();
	if (fu == fv)continue;
	ans +=
}

struct edge {
	int u, v, w;
}e[10005];
bool cmp(edge a, edge b) {
	return a.w < b.w;
}
int fa[105];
int n, m, cnt = 0, ans = 0;
int find(int x) {
	if (fa[x] == x) {
		return x;
	}
	else {
		fa[x] = find(fa[x]);
		return fa[x];
	}
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
	fa[i] = i;
}
for (int i = 1; i <= m; i++) {
	cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; i++) {
	int fu = find(e[i].u), fv = find(e[i].v);
	if (fu == fv)continue;
	cnt++;
	ans += e[i].w;
	fa[fu] = fv;
	if (cnt == n - 1)break;
}
if (cnt == n - 1)cout << ans;
else { cout << -1; }

struct edge {
	int target, nx, w;
}e[10005];
int n, m, cnt = 0;
int head[105];
void add(int u, int v, int w) {
	e[++cnt].target = v;
	e[cnt].w = w;
	e[cnt].nx = head[u];
	head[u] = cnt;
}
#define inf 123456
int dis[105];
bool vis[105];
cin >> n >> m;
for (int i = 1; i <= n; i++) {
	dis[i] = inf;
}
for (int i = 1; i <= m; i++) {
	int u, v, w;
	cin >> u >> v >> w;
	add(u, v, w);
	add(v, u, w);
}
dis[1] = 0;
vis[1] = 1;
for (int i = head[1]; i; i = e[i].nx) {
	dis[e[i].target] = min(dis[e[i].target], dis[e[i].w]);
}
for (int i = 1; i <= n - 1; i++) {
	int mind = inf, u;
	for (int j = 2; j <= n; j++) {
		if (dis)
	}
}

链式前向星

//链式前向星，类似于图的邻接表法，结构体化边，然后用数组去记录点的信息
struct edge {
	int v, w, nx;
}e[1000];
int fir[100];
int cnt = 0;
void add(int u, int v, int w) {
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].nx = fir[u];
	fir[u] = cnt;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;//点数最大值
int n, m, cnt;//n个点，m条边
struct Edge
{
    int to, w, next;//终点，边权，同起点的上一条边的编号
}edge[maxn];//边集
int head[maxn];//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
void init()//初始化
{
    for (int i = 0; i <= n; i++) head[i] = -1;
    cnt = 0;
}
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
    cin >> n >> m;
    int u, v, w;
    init();//初始化
    for (int i = 1; i <= m; i++)//输入m条边
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);//加边
        /*
        加双向边
        add_edge(u, v, w);
        add_edge(v, u, w);
        */
    }
    for (int i = 1; i <= n; i++)//n个起点
    {
        cout << i << endl;
        for (int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }
    return 0;
}
/*
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
*/

遍历

for (int i = 1; i <= n; i++) {
	for (int j = head[i]; j; j = e[j].nx) {
		cout << e[j].v << e[j].w;
	}
}

第一层for循环是找每一个点，依次遍历以【1，n】为起点的边的集合。第二层for循环是遍历以 i 为起点的所有边，k首先等于head[ i ]，注意head[ i ]中存的是以 i 为起点的最后一条边的编号。然后通过edge[ j ].next来找下一条边的编号。我们初始化head为-1，所以找到你最后一个边（也就是以 i 为起点的第一条边）时，你的edge[ j ].next为 -1做为终止条件。

信使

战争时期，前线有?n?个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有?n?个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他k个哨所有通信联系的话，这个哨所内至少会配备k个信使）。

现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。

就是找到从单源点到各个点的最短路径的最长，即MAXMIN

dij

思想就是先用源点初始化，然后迭代N-1轮，每轮确定一个最小的dis，然后在确定的dis元素基础上进行松弛操作，

这里需要注意晚遇到的不一定是最长的，早遇到的不一定是最短的，晚遇到的点，可能通过松弛操作就会减少代价。这里想说的主要就是每轮迭代中找到的最小dij,并不一定是单调递增的，可能会因为某些点的松弛，导致路径的缩短

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int dis[101];
bool vis[101];
int n, m;
int g[101][101];
#define inf 1234567
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dis[i] = inf;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			g[i][j] = inf;
			if (i == j)g[i][j] = 0;
		}
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = w;
	}
	for (int i = 1; i <= n; i++) {
		dis[i] = g[1][i];
	}
	vis[1] = 1;
	for (int i = 1; i <= n - 1; i++) {
		int mind = inf, u;
		for (int j = 2; j <= n; j++) {
			if (!vis[j] && dis[j] < mind) {
				mind = dis[j];
				u = j;
			}
		}
		vis[u] = 1;
		for (int j = 2; j <= n; j++) {
			dis[j] = min(dis[j], dis[u] + g[u][j]);
		}
	}
	int maxd = 0;
	for (int i = 2; i <= n; i++) {
		maxd = max(maxd, dis[i]);
	}
	cout << maxd;
	return 0;
}

判选题

若完全不连通，各点相互独立，也是可以的

考虑到路径数量，即如果有条路径数量很多，那么加1后，这条路的权值和就变化很大

反之，路径数量越少越不容易受影响