当前位置： 首页 > article >正文

第十一章 图论

article 2025/1/7 15:18:42 

/*
* 题目名称：连通图
* 题目来源：吉林大学复试上机题
* 题目链接：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;
}

 


http://www.kler.cn/a/468154.html

相关文章：

  • 软件项目体系建设文档，项目开发实施运维，审计，安全体系建设，验收交付，售前资料（word原件）
  • pdf预览兼容问题- chrome浏览器105及一下预览不了
  • GPT分区 使用parted标准分区划分，以及相邻分区扩容
  • java中类的加载过程及各个阶段与运行时数据区中堆和方法区存储内容
  • Spark是什么？Flink和Spark区别
  • 后台管理系统动态面包屑Ｂreadcrumb组件的实现
  • SSH相关
  • Jmeter进阶篇（32）Jmeter 在 MySQL 数据库压测中的应用
  • Electron不支持 jquery ,angularjs解决办法
  • 游戏引擎学习第73天
  • 在AWS Lambda上部署Python应用：从入门到实战
  • 51单片机——共阴数码管实验
  • 将 Docker 数据迁移到新磁盘：详细操作指南
  • Jenkins 环境安装与配置
  • Linux硬盘分区 --- 挂载分区mount、卸载分区umount、永久挂载
  • 每日一学——自动化工具（Jenkins）
  • 【机器学习实战】kaggle playground最新竞赛，预测贴纸数量--python源码+解析
  • Qt C++ 软件调试内存分析工具Heob(推荐三颗星)
  • 用matlab调用realterm一次性发送16进制数
  • python-leetcode-跳跃游戏
  • python学opencv|读取图像（二十四）使用cv2.putText()绘制文字进阶-倾斜文字
  • Spring MVC 介绍与实践
  • 2025年AI和AR谁才是智能眼镜的未来
  • Java中String对象创建的方式
  • 【SQL serve】教材数据库（6）
  • 外观模式——C++实现