第十一章 图论

/*
* 题目名称：连通图
* 题目来源：吉林大学复试上机题
* 题目链接：http://t.cn/AiO77VoA
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>using namespace std;const int MAXN = 1000 + 10;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%d", &n, &m) != EOF) {if (n == 0 && m == 0) {break;}Initial(n);                             //初始化while (m--) {int x, y;scanf("%d", &x);scanf("%d", &y);Union(x, y);                        //合并集合}int component = 0;                      //连通分量for (int i = 1; i <= n; i++) {if (Find(i) == i) {                 //集合数目component++;}}if (component == 1) {printf("YES\n");} else {printf("NO\n");}}return 0;
}

 

/*
* 题目名称：还是畅通工程
* 题目来源：浙江大学复试上机题
* 题目链接：http://t.cn/AiWud0C6
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;const int MAXN = 100 + 10;struct Edge {int from;                           //边的起点int to;                             //边的终点int length;                         //边的长度bool operator< (const Edge& e) const {return length < e.length;}
};Edge edge[MAXN * MAXN];                 //边集
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 Kruskal(int n, int edgeNumber) {Initial(n);sort(edge, edge + edgeNumber);      //按权值排序int sum = 0;for (int i = 0; i < edgeNumber; ++i) {Edge current = edge[i];if (Find(current.from) != Find(current.to)) {Union(current.from, current.to);sum += current.length;}}return sum;
}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].from, &edge[i].to, &edge[i].length);}int answer = Kruskal(n, edgeNumber);printf("%d\n", answer);}return 0;
}

 

/*
* 题目名称：畅通工程续
* 题目来源：HDU 1874
* 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1874
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <climits>using namespace std;const int MAXN = 200 + 10;
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 minDistance[MAXN];                          //源点到各点最短距离void Dijkstra(int start) {minDistance[start] = 0;priority_queue<Point> myPriorityQueue;myPriorityQueue.push(Point(start, minDistance[start]));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 l = graph[u][i].length;if (minDistance[v] > minDistance[u] + l) {minDistance[v] = minDistance[u] + l;myPriorityQueue.push(Point(v, minDistance[v]));}}}return ;
}int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {memset(graph, 0, sizeof(graph));            //图初始化fill(minDistance, minDistance + 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 start, terminal;                        //起点与终点scanf("%d%d", &start, &terminal);Dijkstra(start);if (minDistance[terminal] == INF) {         //终点不可达minDistance[terminal] = -1;}printf("%d\n", minDistance[terminal]);}return 0;
}

 

/*
* 题目名称：确定比赛名次
* 题目来源：HDU 1285
* 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1285
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <functional>using namespace std;const int MAXN = 500 + 10;vector<int> graph[MAXN];
int inDegree[MAXN];                         //入度vector<int> TopologicalSort(int n) {vector<int> topology;                   //拓扑序列priority_queue<int, vector<int>, greater<int> > node;for (int i = 1; i <= n; ++i) {if (inDegree[i] == 0) {node.push(i);}}while (!node.empty()) {int u = node.top();node.pop();topology.push_back(u);              //加入拓扑序列for (int i = 0; i < graph[u].size(); ++i) {int v = graph[u][i];inDegree[v]--;                  //后继结点入度减一if (inDegree[v] == 0) {node.push(v);}}}return topology;
}int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {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]++;}vector<int> answer = TopologicalSort(n);for (int i = 0; i < answer.size(); ++i) {if (i == 0) {printf("%d", answer[i]);} else {printf(" %d", answer[i]);}}printf("\n");}return 0;
}

题目描述：

阿里这学期修了计算机组织和架构课程。他了解到指令之间可能存在依赖关系，比如WAR（读后写）、WAW、RAW。
如果两个指令之间的距离小于安全距离，则会导致危险，从而可能导致错误的结果。因此，我们需要设计特殊的电路来消除危险。
然而，解决这个问题最简单的方法是添加气泡（无用操作），这意味着浪费时间来确保两条指令之间的距离不小于安全距离。两条指令之间的距离的定义是它们开始时间之间的差异。

现在我们有很多指令，我们知道指令之间的依赖关系和安全距离。我们还有一个非常强大的CPU，具有无限数量的内核，因此您可以同时运行任意数量的指令，而且CPU速度非常快，完成任何指令只需花费1ns。
你的工作是重新排列指令，这样CPU就可以在最短的时间内完成所有指令。

输入：

输入由几个测试用例组成。
第一行有两个整数N，M（N<=1000，M<=10000），表示有N个指令和M个依赖关系。
以下M行，每行包含三个整数X、Y、Z，表示X和Y之间的安全距离为Z，Y应在X之后运行。指令的编号从0到N-1。

输出： 

打印一个整数，即CPU运行所需的最短时间。

/*
* 题目名称：Instrction Arrangement
* 题目来源：HDU 4109
* 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4109
* 代码作者：杨泽邦(炉灰)
*/#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <climits>using namespace std;const int MAXN = 1000 + 10;
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];                             //入度int 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;                    //初始化为1}}int 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].to;int l = graph[u][i].length;earliest[v] = max(earliest[v], earliest[u] + l);inDegree[v]--;if (inDegree[v] == 0) {node.push(v);totalTime = max(totalTime, earliest[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);}}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(latest, 0, sizeof(latest));memset(inDegree, 0, sizeof(inDegree));while (m--) {int from, to, length;scanf("%d%d%d", &from, &to, &length);graph[from].push_back(Edge(to, length));inDegree[to]++;}int answer = CriticalPath(n);printf("%d\n", answer);}return 0;
}