博客

【王道机试】第十一章 图论

  • Post author:
  • Post category:其他



图论

有关问题：

并查集、最小生成树、最短路径、拓扑排序、关键路径

等。

如何

实现

作为抽象数据的图结构：

邻接矩阵、邻接表

。

文章目录



11.1 概述

图（Graph）定义为 G = (V, E)。也就是说，图是由顶点（Vertex）集合V和边（Edge）集合E组成的。

实现方式：邻接矩阵、邻接表



11.2 并查集（Union Find）

并查集用于处理一些不交集（Disjoint Sets）的合并和查询问题。

并查集有两个操作，分别是

查找（Find）

和

合并（Find）

。


查找

：确定元素属于哪个集合。步骤：不断向上查找，知道找到它的根节点，之后根据根节点是否相同来判断两个元素是否属于同一集合。


合并

：将两个子集合并成同一个集合。步骤：将一棵树作为另一棵树的子树，从而使得两棵树变成一棵更大的树。


避免树太高

：路径压缩（在查找某个特定结点的根节点时，将其与根节点之间的所有结点都指向根节点）、合并时将高度较低的树作为高度较高的树的子树进行合并。



例题11.1 畅通工程


提交网址

这个代码两种优化都用到了，需要好好理解。 

#include <iostream>
using namespace std;

const int MAXN = 1000;

int father[MAXN];
int height[MAXN];

void Initial(int n){
	for(int i=0; i<=n; i++){
		father[i] = i;
		height[i] = 0;
	}
} 

int Find(int x){	//查找根结点 
	if(x != father[x]){	//路径压缩 
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y){	//合并集合 
	x = Find(x);
	y = Find(y);
	if(x != y){	//矮树作为高树的子树 
		if(height[x] < height[y]){
			father[x] = y;
		}else if(height[y] < height[x]){
			father[y] = x;
		}else{
			father[y] = x;
			height[x]++;
		}
	}
	return;
}

int main(){
	int n, m;
	while(scanf("%d", &n) != EOF){
		if(n == 0) break;
		scanf("%d", &m);
		Initial(n);
		while(m--){
			int x, y;
			scanf("%d%d", &x, &y);
			Union(x, y);
		} 
		int answer = -1;
		for(int i=1; i<=n; i++){
			if(Find(i) == i){
				answer++;
			} 
		}
		printf("%d\n", answer);
	}
	return 0;
}



例题11.2 连通图

在图论中，并查集最常用来判断图是否为连通图，或用来求连通分量。

其实做了这几题下来发现

并查集的代码比较偏模板化

，如果能够熟悉这个套路，使用起来还是很方便的！

也可以用深度优先搜索来求，但是效率比较低。


提交网址
 

#include <iostream>
using namespace std;

const int MAXN = 1000;

int father[MAXN];
int height[MAXN];

void Initial(int n){
	for(int i=1; i<=n; i++){
		father[i] = i;
	}
}

int Find(int x){
	if(x != father[x]){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(height[x] > height[y]){
			father[y] = x;
		}else if(height[x] < height[y]){
			father[x] = y;
		}else{
			father[y] = x;
			height[x]++;
		}
	}
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		if(m == 0 && n == 0) break;
		Initial(n);
		while(m--){
			int x, y;
			scanf("%d%d", &x, &y);
			Union(x, y);
		}
		int cnt = 0;
		for(int i=1; i<=n; i++){
			if(Find(i) == i){
				cnt++;
			}
		}
		if(cnt == 1){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
	return 0;
}



例题11.3 Is it A Tree?


提交网址
 

#include <iostream>
using namespace std;

const int MAXN = 10000;

int father[MAXN];
int height[MAXN];
int inDegree[MAXN];
bool visit[MAXN];

void Initial(){
	for(int i=0; i<MAXN; i++){
		father[i] = i;
		height[i] = 0;
		inDegree[i] = 0;
		visit[i] = false;
	}
}

int Find(int x){
	if(x != father[x]){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(height[x] > height[y]){
			father[y] = x;
		}else if(height[y] > height[x]){
			father[x] = y;
		}else{
			father[y] = x;
			height[x]++;
		}
	}
	return;
}

bool IsTree(){
	bool flag = true;
	int component = 0;	//连通分量数目 
	int root = 0;		//根结点数目 
	for(int i=0; i<MAXN; i++){
		if(!visit[i]){
			continue;
		}
		if(father[i] == i){
			component++;
		}
		if(inDegree[i] == 0){
			root++;
		}else if(inDegree[i] > 1){
			flag = false;
		}
	}
	if(component != 1 || root != 1){
		flag = false;
	}
	if(component == 0 && root == 0){
		flag = true;
	}
	return flag;
}

int main(){
	int x, y;
	int caseNumber = 0;
	Initial();
	while(scanf("%d%d", &x, &y)){
		if(x == -1 && y == -1){
			break;
		}
		if(x == 0 && y == 0){
			if(IsTree()){
				printf("Case %d is a tree.\n", ++caseNumber);
			}else{
				printf("Case %d is not a tree.\n", ++caseNumber);
			}
			Initial();
		}else{
			Union(x, y);
			inDegree[y]++;
			visit[x] = true;
			visit[y] = true;
		}
	}
	return 0;
}



习题11.1 找出直系亲属


提交网址

占个坑，之后有时间再做。用并查集的思路的话，考虑到孩子不止一个，那么child用数组或者vector来存。



习题11.2 第一题


提交网址

综合map使用并查集。 

#include <iostream>
#include <map>
using namespace std;

map<int, int> father;
map<int, int> height;

int Find(int x){
	if(father.find(x) == father.end()){
		father[x] = x;
		height[x] = 0;
	}else{
		if(x != father[x]){
			father[x] = Find(father[x]);
		}
	}
	return father[x];
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(height[x] < height[y]){
			father[x] = y;
		}else if(height[y] < height[x]){
			father[y] = x;
		}else{
			father[y] = x;
			height[x]++;
		}
	}
}

int main(){
	int x, y;
	while(scanf("%d%d", &x, &y) != EOF){
		Union(x, y);
	}
	int cnt = 0;
	for(auto it = father.begin(); it != father.end(); it++){
		int tmp = it->first;
		if(tmp == father[tmp]){
			cnt++;
		}
	}
	printf("%d\n", cnt);
	return 0;
}



习题11.3 Head of a Gang


提交网址

再次占坑。。。下次一定！



11.3 最小生成树（MST）

两种算法：

Kruskal算法

和

Prim算法

。



例题11.4 还是畅通工程


提交网址

使用Kruskal算法，会涉及大量的集合操作，恰好可以使用并查集来实现。 

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 101;
struct Edge{
	int a, b;
	int len;
	bool operator< (const Edge& e) const{
		return len < e.len;
	}
};
Edge edge[MAXN * MAXN / 2];
int father[MAXN], height[MAXN];

void Initial(int n){
	for(int i=1; i<=n; i++){
		father[i] = i;
	}
}

int Find(int x){
	if(father[x] != x){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(height[x] > height[y]){
			father[y] = x;
		}else if(height[x] < height[y]){
			father[x] = y;
		}else{
			father[x] = y;
			height[y]++;
		}
	}
}

int Kruskal(int n, int edgeNumber){
	Initial(n);
	sort(edge, edge + edgeNumber);
	int length = 0;
	for(int i=0; i<edgeNumber; i++){
		if(Find(edge[i].a) != Find(edge[i].b)){
			Union(edge[i].a, edge[i].b);
			length += edge[i].len;
		}
	}
	return length;
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		if(n == 0) break;
		int edgeNumber = n * (n - 1) / 2;
		for(int i=0; i<edgeNumber; i++){
			scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].len);
		}
		printf("%d\n", Kruskal(n, edgeNumber));
	}
	return 0;
}



例题11.5 继续畅通工程


提交网址

和上一题一样，将已建的成本改为0即可。 

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 101;
struct Edge{
	int a, b;
	int len;
	bool operator< (const Edge& e) const{
		return len < e.len;
	}
};
Edge edge[MAXN * MAXN / 2];
int father[MAXN], height[MAXN];

void Initial(int n){
	for(int i=1; i<=n; i++){
		father[i] = i;
	}
}

int Find(int x){
	if(father[x] != x){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(height[x] > height[y]){
			father[y] = x;
		}else if(height[x] < height[y]){
			father[x] = y;
		}else{
			father[x] = y;
			height[y]++;
		}
	}
}

int Kruskal(int n, int edgeNumber){
	Initial(n);
	sort(edge, edge + edgeNumber);
	int length = 0;
	for(int i=0; i<edgeNumber; i++){
		if(Find(edge[i].a) != Find(edge[i].b)){
			Union(edge[i].a, edge[i].b);
			length += edge[i].len;
		}
	}
	return length;
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		if(n == 0) break;
		int edgeNumber = n * (n - 1) / 2;
		int status;
		for(int i=0; i<edgeNumber; i++){
			scanf("%d%d%d%d", &edge[i].a, &edge[i].b, &edge[i].len, &status);
			if(status == 1){
				edge[i].len = 0;
			}
		}
		printf("%d\n", Kruskal(n, edgeNumber));
	}
	return 0;
}



习题11.4 Freckles


提交网址
 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 101;
struct Edge{
	double a, b;
	double len;
	bool operator< (const Edge& e) const{
		return len < e.len;
	}
};
struct Vertex{
	double x, y;
};
Vertex vertex[MAXN];
Edge edge[MAXN * MAXN / 2];
int father[MAXN], height[MAXN];

void Initial(int n){
	for(int i=1; i<=n; i++){
		father[i] = i;
	}
}

int Find(int x){
	if(father[x] != x){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(height[x] > height[y]){
			father[y] = x;
		}else if(height[x] < height[y]){
			father[x] = y;
		}else{
			father[x] = y;
			height[y]++;
		}
	}
}

double Kruskal(int n, int edgeNumber){
	Initial(n);
	sort(edge, edge + edgeNumber);
	double length = 0;
	for(int i=0; i<edgeNumber; i++){
		if(Find(edge[i].a) != Find(edge[i].b)){
			Union(edge[i].a, edge[i].b);
			length += edge[i].len;
		}
	}
	return length;
}

double Distance(int i, int j){
	double xlen = vertex[i].x - vertex[j].x;
	double ylen = vertex[i].y - vertex[j].y;
	return sqrt(xlen * xlen + ylen * ylen);
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		if(n == 0) break;
		int edgeNumber = n * (n - 1) / 2;
		for(int i=0; i<n; i++){
			scanf("%lf%lf", &vertex[i].x, &vertex[i].y);
		}
		int k = 0;
		for(int i=0; i<n; i++){
			for(int j=0; j<i; j++){
				edge[k].a = i; edge[k].b = j;
				edge[k].len = Distance(i, j);
				k++;
			}
		} 
		printf("%.2f\n", Kruskal(n, edgeNumber));
	}
	return 0;
}



习题11.5 Jungle Roads


提交网址
 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 26;
struct Edge{
	int a, b;
	int len;
	bool operator< (const Edge& e) const{
		return len < e.len;
	}
};
Edge edge[MAXN * MAXN / 2];
int father[MAXN], height[MAXN];

void Initial(int n){
	for(int i=1; i<=n; i++){
		father[i] = i;
	}
}

int Find(int x){
	if(father[x] != x){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(height[x] > height[y]){
			father[y] = x;
		}else if(height[x] < height[y]){
			father[x] = y;
		}else{
			father[x] = y;
			height[y]++;
		}
	}
}

int Kruskal(int n, int edgeNumber){
	Initial(n);
	sort(edge, edge + edgeNumber);
	double length = 0;
	for(int i=0; i<edgeNumber; i++){
		if(Find(edge[i].a) != Find(edge[i].b)){
			Union(edge[i].a, edge[i].b);
			length += edge[i].len;
		}
	}
	return length;
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		if(n == 0) break;
		int edgeNumber = n * (n - 1) / 2;
		char c1, c2;
		int num, k = 0;
		for(int i=0; i<n - 1; i++){
			cin >> c1 >> num;
			int distance;
			while(num--){
				cin >> c2 >> distance;
				edge[k].a = c1 - 'A'; edge[k].b = c2 - 'A';
				edge[k].len = distance;
				k++;
			}
		}
		printf("%d\n", Kruskal(n, edgeNumber));
	}
	return 0;
}



11.4 最短路径

经典算法：

Dijkstra算法

。

如果是用矩阵存储的话，处理起来就稍微简单一些。下面是数据结构noj做过的类似题目：


【数据结构实验】NOJ008 实验4.1 求赋权图中一个结点到所有结点的最短路径的长度



【数据结构实验】NOJ009 实验4.2 用迪杰斯特拉算法求赋权图中的最短路径


如果是求任意两点之间的最短路径，用Floyd算法更简单。


【数据结构实验】NOJ010 实验4.3 用弗洛伊德算法求赋权图的两点间的最短路径的长度



【数据结构】NOJ011 实验4.4 用弗洛伊德算法求赋权图中任意两点间的最短路径

下面的题目存储方式是三元组。按照书上的代码写的，用到了优先队列。



例题11.6 畅通工程续

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 20;
const int INF = INT_MAX;

struct Edge{
	int to;
	int length;
	Edge(int t, int l): to(t), length(l){}
};

struct Point{
	int number;
	int distance;
	Point(int n, int d): number(n), distance(d) {}
	bool operator< (const Point& p) const{
		return distance > p.distance;
	}
};

vector<Edge> graph[MAXN];
int dis[MAXN];

void Dijkstra(int s){
	priority_queue<Point> myPriorityQueue;
	dis[s] = 0;
	myPriorityQueue.push(Point(s, dis[s]));
	while(!myPriorityQueue.empty()){
		int u = myPriorityQueue.top().number;
		myPriorityQueue.pop();
		for(int i=0; i<graph[u].size(); i++){
			int v = graph[u][i].to;
			int d = graph[u][i].length;
			if(dis[v] > dis[u] + d){
				dis[v] = dis[u] + d;
				myPriorityQueue.push(Point(v, dis[v]));
			}
		}
	}
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(graph, 0, sizeof(graph));
		fill(dis, dis + n, INF);
		while(m--){
			int from, to, length;
			scanf("%d%d%d", &from, &to, &length);
			graph[from].push_back(Edge(to, length));
			graph[to].push_back(Edge(from, length));
		}
		int s, t;
		scanf("%d%d", &s, &t);
		Dijkstra(s);
		if(dis[t] == INF){
			dis[t] = -1;
		}
		printf("%d\n", dis[t]);
	}
	return 0;
}



例题11.7 最短路径问题


提交网址
 

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 1001;
const int INF = INT_MAX;

struct Edge{
	int to;
	int length;
	int price;
	Edge(int t, int l, int p): to(t), length(l), price(p) {}
};

struct Point{
	int number;
	int distance;
	Point(int n, int d): number(n), distance(d) {}
	bool operator< (const Point& p) const{
		return distance > p.distance;
	}
};

vector<Edge> graph[MAXN];
int dis[MAXN];
int cost[MAXN];

void Dijkstra(int s){
	priority_queue<Point> myPriorityQueue;
	dis[s] = 0; cost[s] = 0;
	myPriorityQueue.push(Point(s, dis[s]));
	while(!myPriorityQueue.empty()){
		int u = myPriorityQueue.top().number;
		myPriorityQueue.pop();
		for(int i=0; i<graph[u].size(); i++){
			int v = graph[u][i].to;
			int d = graph[u][i].length;
			int p = graph[u][i].price;
			if((dis[v] == dis[u] + d && cost[v] > cost[u] + p) || dis[v] > dis[u] + d){
				dis[v] = dis[u] + d;
				cost[v] = cost[u] + p;
				myPriorityQueue.push(Point(v, dis[v]));
			}
		}
	}
	return;
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		if(m == 0 && n == 0) break;
		memset(graph, 0, sizeof(graph));
		fill(dis, dis + n + 1, INF);
		fill(cost, cost + n + 1, INF);
		while(m--){
			int from, to, length, price;
			scanf("%d%d%d%d", &from, &to, &length, &price);
			graph[from].push_back(Edge(to, length, price));
			graph[to].push_back(Edge(from, length, price));
		}
		int s, t;
		scanf("%d%d", &s, &t);
		Dijkstra(s);
		printf("%d %d\n", dis[t], cost[t]);
	}
	return 0;
}



习题11.6 最短路径


提交网址
 

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;

// 1.定义数据结构
struct Edge{
    int to;
    int length;
    Edge(int a,int b): to(a),length(b){}
};

struct Point{
    int name;
    int distance;
    Point(int a, int b): name(a), distance(b){}
    bool operator< (const Point& p) const{
        return distance > p.distance;
    }
};

// 2.定义全局变量
const int MAXN = 101;
const int INF = INT_MAX;
vector<Edge> graph[MAXN];
int dis[MAXN];
int father[MAXN];

// 3.定义Dijsktra
void Dijsktra(){
    priority_queue<Point> myqueue;
    dis[0] = 0;
    myqueue.push(Point(0,dis[0]));
    while(!myqueue.empty()){
        int u = myqueue.top().name;
        myqueue.pop();
        for(int i=0;i<graph[u].size();i++){
            int point = graph[u][i].to;
            int length = graph[u][i].length;
            if(dis[point]>dis[u]+length){
                dis[point] = dis[u]+length;
                myqueue.push(Point(point,dis[point]));
            }
        }
    }
    return;
}

// 4.并查集相关
int Find(int a){
    while(father[a]!=a){
        a = father[a];
    }
    return a;
}

void Union(int a,int b){
    int root_a = Find(a);
    int root_b = Find(b);
    if(root_a!=root_b){
        father[root_b] = root_a;
    }
}

// 5.编写主函数
int main(){
    int n,m;
    while(cin>>n>>m){
        memset(graph,0,sizeof(graph));
        fill(dis, dis+n, INF);
        for(int i=0;i<n;i++){
            father[i] = i;
        }
        int length = 1;
        for(int i=0;i<m;i++){
            int from,to;
            cin>>from>>to;
            if(Find(from)!=Find(to)){
                Union(from,to);
                graph[from].push_back(Edge(to,length));
                graph[to].push_back(Edge(from,length));
            }
            length = length*2 % 100000;
        }
    }
    Dijsktra();
    for(int i=1;i<n;i++){
        if(dis[i]==INF){
            cout<<-1<<endl;
        }
        else{
            cout<<dis[i]%100000<<endl;
        }
    }
    return 0;
}



习题11.7 I Wanna Go Home


提交网址

有时间再写。



11.5 拓扑排序



例题11.8 Legal or Not

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN = 500;
vector<int> graph[MAXN];
int inDegree[MAXN];

bool TopologicalSort(int n){
	queue<int> node;
	for(int i=0; i<n; i++){
		if(inDegree[i] == 0){
			node.push(i);
		}
	}
	int number = 0;
	while(!node.empty()){
		int u = node.front();
		node.pop();
		number++;
		for(int i=0; i<graph[u].size(); i++){
			int v = graph[u][i];
			inDegree[v]--;
			if(inDegree[v] == 0){
				node.push(v);
			}
		}
	}
	return n == number;
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		if(n == 0 && m == 0){
			break;
		}
		memset(graph, 0, sizeof(graph));
		memset(inDegree, 0, sizeof(inDegree));
		while(m--){
			int from, to;
			scanf("%d%d", &from, &to);
			graph[from].push_back(to);
			inDegree[to]++;
		}
		if(TopologicalSort(n)){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
	return 0;
}



例题11.9 确定比赛名次

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 501;

vector<int> graph[MAXN];
int inDegree[MAXN];

void TopologicalSort(int n){
	priority_queue<int, vector<int>, greater<int>> q;
	for(int i=1; i<=n; i++){
		if(inDegree[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u = q.top();
		q.pop();
		printf("%d ", u);
		for(int i=0; i<graph[u].size(); i++){
			int v = graph[u][i];
			inDegree[v]--;
			if(inDegree[v] == 0){
				q.push(v);
			}
		}
	}
} 

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(graph, 0, sizeof(graph));
		memset(inDegree, 0, sizeof(inDegree));
		int from, to;
		while(m--){
			scanf("%d%d", &from, &to);
			graph[from].push_back(to);
			inDegree[to]++;
		}
		TopologicalSort(n);
		printf("\n");
	}
	return 0;
}



11.6 关键路径


AOE网

：在带权有向图中，若以顶点表示事件，以有向边表示活动，以边上的权值表示该活动持续的时间，则这样的图称为AOE网。


关键路径

：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。把关键路径上的活动称为关键活动。


关键活动

的

最早开始时间

和

最晚开始时间

相同。可根据这一点求出关键路径。

  1. 对于一个活动而言，其全部先序活动的最晚完成时间便是该活动的最早开始时间。
  2. 对于一个活动而言，其全部后序活动的最早开始时间减去该活动需要花费的时间，便是该活动的最晚开始时间。



例题11.10 Instructions Arrangement

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <climits>
using namespace std;

const int MAXN = 1001;
const int INF = INT_MAX; 

struct Edge{
	int to;
	int length;
	Edge(int t, int l): to(t), length(l) {}
};

vector<Edge> graph[MAXN];
int earliest[MAXN];
int latest[MAXN];
int inDegree[MAXN];

void CriticalPath(int n){
	vector<int> topology;
	queue<int> node;
	for(int i=0; i<n; i++){
		if(inDegree[i] == 0){
			node.push(i);
			earliest[i] = 1;
		}
	}
	while(!node.empty()){
		int u = node.front();
		topology.push_back(u);
		node.pop();
		for(int i=0; i<graph[u].size(); i++){
			int v = graph[u][i].to;
			int l = graph[u][i].length;
			earliest[v] = max(earliest[v], earliest[u] + l);
			inDegree[v]--;
			if(inDegree[v] == 0){
				node.push(v);
			} 
		}
	}
	for(int i=topology.size() - 1; i>=0; i--){
		int u = topology[i];
		if(graph[u].size() == 0){
			latest[u] = earliest[u];	//汇点的最晚开始时间初始化 
		}else{
			latest[u] = INF;			//非汇点的最晚开始时间初始化 
		}
		for(int j=0; j<graph[u].size(); j++){
			int v = graph[u][j].to;
			int l = graph[u][j].length;
			latest[u] = min(latest[u], latest[v] - l);
		}
	}
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(graph, 0, sizeof(graph));
		memset(earliest, 0, sizeof(earliest));
		memset(inDegree, 0, sizeof(inDegree));
		memset(latest, 0, sizeof(latest));
		while(m--){
			int from, to, length;
			scanf("%d%d%d", &from, &to, &length);
			graph[from].push_back(Edge(to, length));
			inDegree[to]++;
		}
		CriticalPath(n);
		int answer = 0;
		for(int i=0; i<n; i++){
			answer = max(answer, earliest[i]);
		}
		printf("%d\n", answer);
	}
	return 0;
}



例题11.11 p3

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <climits>
using namespace std;

const int MAXN = 1e5 + 7;
const int INF = INT_MAX; 
const int MOD = 1e9 + 7;

vector<int> graph[MAXN];
long long earliest[MAXN];
long long latest[MAXN];
long long time[MAXN];
int inDegree[MAXN];

long long CriticalPath(int n){
	vector<int> topology;
	queue<int> node;
	for(int i=1; i<=n; i++){
		if(inDegree[i] == 0){
			node.push(i);
		}
	}
	long long totalTime = 0;
	while(!node.empty()){
		int u = node.front();
		topology.push_back(u);
		node.pop();
		for(int i=0; i<graph[u].size(); i++){
			int v = graph[u][i];
			earliest[v] = max(earliest[v], earliest[u] + time[u]);
			inDegree[v]--;
			if(inDegree[v] == 0){
				node.push(v);
				totalTime = max(totalTime, earliest[v] + time[v]);
			} 
		}
	}
	for(int i=topology.size() - 1; i>=0; i--){
		int u = topology[i];
		if(graph[u].size() == 0){
			latest[u] = totalTime - time[u];	//汇点的最晚开始时间初始化 
		}else{
			latest[u] = INF;			//非汇点的最晚开始时间初始化 
		}
		for(int j=0; j<graph[u].size(); j++){
			int v = graph[u][j];
			latest[u] = min(latest[u], latest[v] - time[u]);
		}
	}
	return totalTime;
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(graph, 0, sizeof(graph));
		memset(earliest, 0, sizeof(earliest));
		memset(inDegree, 0, sizeof(inDegree));
		memset(latest, 0, sizeof(latest));
		memset(time, 0, sizeof(time));
		for(int i=1; i<=n; i++){
			scanf("%lld", &time[i]);
		}
		while(m--){
			int from, to;
			scanf("%d%d", &from, &to);
			graph[from].push_back(to);
			inDegree[to]++;
		}
		long long totalTime = CriticalPath(n);
		long long answer = 1;
		for(int i=0; i<n; i++){
			answer *= latest[i] - earliest[i] + 1;
			answer %= MOD;
		}
		printf("%lld\n%lld\n", totalTime, answer);
	}
	return 0;
}

果然不应该集中做完图这一章。。。从最开始的自己敲代码，到后来照着书上的代码敲。

这波啊，这波是再看到图就有点害怕了。


版权声明：本文为weixin_45932570原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。