电商网站开发主要的三个软件,关键词搜索点击软件,北京到安阳大巴车几个小时,做网站开发的步骤在上一篇中我们进行了图的专项练习#xff0c;在这一篇中我们重点探讨图的编程专项习题。 目录 R7-1 城市间紧急救援R7-2 地铁一日游R7-3 最小生成树的唯一性R7-4 网红点打卡攻略R7-5 畅通工程之最低成本建设问题R7-6 寻宝图R7-7 逆散列问题R7-8 任务调度的合理性R7-9 关键活动… 在上一篇中我们进行了图的专项练习在这一篇中我们重点探讨图的编程专项习题。 目录 R7-1 城市间紧急救援R7-2 地铁一日游R7-3 最小生成树的唯一性R7-4 网红点打卡攻略R7-5 畅通工程之最低成本建设问题R7-6 寻宝图R7-7 逆散列问题R7-8 任务调度的合理性R7-9 关键活动 编程题
R7-1 城市间紧急救援
作为一个城市的应急救援队伍的负责人你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候你的任务是带领你的救援队尽快赶往事发地同时一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D其中N2≤N≤500是城市的个数顺便假设城市的编号为0 ~ (N−1)M是快速道路的条数S是出发地的城市编号D是目的地的城市编号。
第二行给出N个正整数其中第i个数是第i个城市的救援队的数目数字间以空格分隔。随后的M行中每行给出一条快速道路的信息分别是城市1、城市2、快速道路的长度中间用空格分开数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔输出结尾不能有多余空格。
输入样例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2输出样例:
2 60
0 1 3#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
#define inf 0x3f3f3f3f
int map[1010][1010],a[1010],b[1010]; // 定义邻接矩阵map、每个顶点的权值a、到每个顶点的最小权值和b
int dis[1010],vis[1010],l[1010],sum[1010]; // 定义源点到各顶点的距离dis标记数组vis前驱数组l到达某个顶点的最短路径条数sum
int n,m,d,s; // 定义顶点数n、边数m、起点s和终点dvoid dijstra(int x) // Dijkstra算法求解最短路径
{int i,j,k,minn;b[x]a[x]; // 初始化起点的最小权值和为a[s]for(i0;in;i){dis[i]map[x][i]; // 初始化源点到各顶点的距离为起点到i的边权值l[i]-1; // 初始化前驱数组l为-1表示没有前驱if(dis[i]inf) // 如果存在从起点s到顶点i的边{b[i]a[x]a[i]; // 更新到顶点i的最小权值和为a[s]a[i]sum[i]1; // 到达顶点i的最短路径条数初始化为1l[i]x; // 更新前驱为起点s}}l[x]-1; // 起点s没有前驱vis[x]1; // 标记起点s已经访问过for(i0;in;i){minninf;for(j0;jn;j){if(!vis[j]dis[j]minn) // 找到未访问过的距离源点最近的顶点{minndis[j];kj;}}vis[k]1; // 标记k顶点已经访问过for(j0;jn;j){if(!vis[j]dis[j]minnmap[k][j]) // 如果通过k顶点可以更新j顶点的最短路径{dis[j]minnmap[k][j]; // 更新源点到j顶点的距离b[j]b[k]a[j]; // 更新到j顶点的最小权值和l[j]k; // 更新j顶点的前驱为k顶点sum[j]sum[k]; // 更新到达j顶点的最短路径条数}else if(!vis[j]dis[j]minnmap[k][j]) // 如果通过k顶点可以到达j顶点的最短路径有多条{sum[j]sum[j]sum[k]; // 更新到达j顶点的最短路径条数if(b[j]b[k]a[j]) // 如果更新后到达j顶点的最小权值和更小则更新前驱为k顶点{b[j]b[k]a[j];l[j]k;}}}}
}void find(int x) // 递归输出路径上的所有顶点
{if(l[x]!-1){find(l[x]);printf(%d ,l[x]);}
}int main()
{memset(map,inf,sizeof(map));memset(vis,0,sizeof(vis));int i,j,x,y,t;scanf(%d%d%d%d,n,m,s,d);for(i0;in;i)scanf(%d,a[i]); // 输入每个顶点的权值for(i0;im;i){scanf(%d%d%d,x,y,t);map[x][y]map[y][x]t; // 输入每条边的起点、终点和边权构造邻接矩阵}dijstra(s); // 求解从起点s到各顶点的最短路径printf(%d %d\n,sum[d],b[d]); // 输出从起点s到终点d的最短路径条数和最小权值和find(d); // 输出从起点s到终点d的最短路径上的所有顶点printf(%d\n,d);return 0;
}
R7-2 地铁一日游
森森喜欢坐地铁。这个假期他终于来到了传说中的地铁之城——魔都打算好好过一把坐地铁的瘾
魔都地铁的计价规则是起步价 2 元出发站与到达站的最短距离即计费距离每 K 公里增加 1 元车费。
例如取 K 10动安寺站离魔都绿桥站为 40 公里则车费为 2 4 6 元。
为了获得最大的满足感森森决定用以下的方式坐地铁在某一站上车不妨设为地铁站 A则对于所有车费相同的到达站森森只会在计费距离最远的站或线路末端站点出站然后用森森美图 App 在站点外拍一张认证照再按同样的方式前往下一个站点。
坐着坐着森森突然好奇起来在给定出发站的情况下在出发时森森也会拍一张照他的整个旅程中能够留下哪些站点的认证照
地铁是铁路运输的一种形式指在地下运行为主的城市轨道交通系统。一般来说地铁由若干个站点组成并有多条不同的线路双向行驶可类比公交车当两条或更多条线路经过同一个站点时可进行换乘更换自己所乘坐的线路。举例来说魔都 1 号线和 2 号线都经过人民广场站则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站也拍不到认证照因此森森乘坐地铁时换乘不受限制。
输入格式:
输入第一行是三个正整数 N、M 和 K表示魔都地铁有 N 个车站 (1 ≤ N ≤ 200)M 条线路 (1 ≤ M ≤ 1500)最短距离每超过 K 公里 (1 ≤ K ≤ 106)加 1 元车费。
接下来 M 行每行由以下格式组成
站点1空格距离空格站点2空格距离空格站点3 … 站点X-1空格距离空格站点X
其中站点是一个 1 到 N 的编号两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 106 的正整数。一条线路上的站点互不相同。
注意两个站之间可能有多条直接连接的线路且距离不一定相等。
再接下来有一个正整数 Q (1 ≤ Q ≤ 200)表示森森尝试从 Q 个站点出发。
最后有 Q 行每行一个正整数 Xi表示森森尝试从编号为 Xi 的站点出发。
输出格式:
对于森森每个尝试的站点输出一行若干个整数表示能够到达的站点编号。站点编号从小到大排序。
输入样例:
6 2 6
1 6 2 4 3 1 4
5 6 2 6 6
4
2
3
4
5输出样例:
1 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 6#include iostream
#include cstdio
#include algorithm
#include cstring
#include cmath
#include string
#include map
#include vector
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;int n, m, k, dp[205][205]; // 定义顶点数n边数m每条边的费用k和表示最短路径的二维数组dp
vectorint g[205]; // 保存最终关系网
bool vis[205]; // 标记数组用于DFS访问
vectorint res; // 最终能经过的点
bool flag[205]; // 记录是否为末端站点void dfs(int now){ // 深度优先搜索遍历图for(int i 0; i g[now].size(); i){int to g[now][i];if(!vis[to]){vis[to] true;res.push_back(to);dfs(to);}}
}signed main()
{cin n m k; // 输入顶点数、边数和费用memset(dp, 0x3f, sizeof dp); // 初始化最短路径数组为无穷大for(int i 1; i m; i){int u, v, w;scanf(%lld, u);flag[u] true; while(true){scanf(%lld%lld, w, v);dp[u][v] dp[v][u] min(dp[u][v], w); // 更新边的费用u v;char ch getchar();if(ch \n)break;}flag[u] true;}for(int i 1; i n; i)dp[i][i] 0; // 自身到自身的路径长度为0for(int k 1; k n; k)for(int i 1; i n; i)for(int j 1; j n; j)dp[i][j] min(dp[i][j], dp[i][k]dp[k][j]); // 动态规划求解最短路径for(int i 1; i n; i){mapint, vectorint ans; // 使用map来保存每个价格对应的站点集合for(int j 1; j n; j){if(i j || dp[i][j] inf) continue;int price dp[i][j]/k; // 计算价格if(!ans[price].size())ans[price].push_back(j);else if(dp[i][ans[price][0]] dp[i][j]){ans[price].clear();ans[price].push_back(j); }else if(dp[i][ans[price][0]] dp[i][j])ans[price].push_back(j);}for(int j 1; j n; j) // 将末端站点加入{if(dp[i][j] ! inf flag[j]){int price dp[i][j]/k;ans[price].push_back(j);}}vectorint temp;for(mapint, vectorint::iterator it ans.begin(); it ! ans.end(); it){for(int j 0; j (it-second).size(); j)temp.push_back((it-second)[j]);}for(int j 0; j temp.size(); j)g[i].push_back(temp[j]); // 更新最终关系网}int q;cin q; // 输入查询次数while(q--){int t;scanf(%lld, t);res.clear();memset(vis, false, sizeof vis);vis[t] true;res.push_back(t); dfs(t); // 深度优先搜索遍历从起点到终点的路径sort(res.begin(), res.end()); // 对结果进行排序printf(%lld, res[0]);for(int i 1; i res.size(); i)printf( %lld, res[i]); // 输出最短路径上经过的点puts();}return 0;
}
R7-3 最小生成树的唯一性
给定一个带权无向图如果是连通图则至少存在一棵最小生成树有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重并且判断其是否唯一。
输入格式
首先第一行给出两个整数无向图中顶点数 N≤500和边数 M。随后 M 行每行给出一条边的两个端点和权重格式为“顶点1 顶点2 权重”其中顶点从 1 到N 编号权重为正整数。题目保证最小生成树的总权重不会超过 230。
输出格式
如果存在最小生成树首先在第一行输出其总权重第二行输出“Yes”如果此树唯一否则输出“No”。如果树不存在则首先在第一行输出“No MST”第二行输出图的连通集个数。
输入样例 1
5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5输出样例 1
11
Yes输入样例 2
4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3输出样例 2
4
No输入样例 3
5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3输出样例 3
No MST
2#includeiostream
#includealgorithm
#includesetusing namespace std;const int N 200010;int n,m;
int p[N];
int f 0;//并查集
int find(int x){if(p[x] ! x) p[x] find(p[x]);return p[x];
}//结构体存边
struct Edge{int a,b,w;bool operator (const Edge x) const{return w x.w;}
} es[N];int main(){cin n m; // 输入顶点数和边数for(int i 0;i m;i ){int a,b,c;cin a b c; // 输入边的起点、终点和权重es[i] {a,b,c}; // 存储边的信息到结构体数组}int cnt 0,res 0; // cnt表示当前生成树边的数量res表示当前生成树的总权重for(int i 1;i n;i ) p[i] i; // 初始化并查集每个节点的父节点初始化为自身sort(es,es m); // 对边按权重进行排序for(int i 0;i m;i ){int a es[i].a,b es[i].b,w es[i].w; // 获取当前边的起点、终点和权重a find(a),b find(b); // 查找起点和终点的根节点if(a ! b){ // 如果起点和终点不在同一个连通块中for(int j i 1;j m w es[j].w;j ){ // 在相同权重的边中查找是否存在形成环路的边int pa find(es[j].a),pb find(es[j].b);if((pa a pb b) || (pa b pb a)) f 1; // 如果存在形成环路的边将标志位f设为1}p[a] b; // 将起点的根节点设置为终点的根节点合并两个连通块res w; // 更新生成树的总权重cnt ; // 边数加1}if(cnt n - 1) break; // 如果生成树边的数量达到n-1即所有顶点都被连接则结束循环} setint alls; // 使用set保存所有顶点所属的连通块的根节点for(int i 1;i n;i ) alls.insert(find(i)); // 遍历所有顶点插入其根节点到set中if(alls.size() 1){ // 如果只有一个连通块cout res endl; // 输出生成树的总权重if(f) cout No; // 如果存在形成环路的边输出Noelse cout Yes; // 否则输出Yes}else{cout No MST endl; // 输出没有最小生成树cout alls.size(); // 输出连通块的数量}
}
R7-4 网红点打卡攻略
一个旅游景点如果被带火了的话就被称为“网红点”。大家来网红点游玩俗称“打卡”。在各个网红点打卡的快省乐钱方法称为“攻略”。你的任务就是从一大堆攻略中找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。
输入格式
首先第一行给出两个正整数网红点的个数 N1N≤200和网红点之间通路的条数 M。随后 M 行每行给出有通路的两个网红点、以及这条路上的旅行花费为正整数格式为“网红点1 网红点2 费用”其中网红点从 1 到 N 编号同时也给出你家到某些网红点的花费格式相同其中你家的编号固定为 0。
再下一行给出一个正整数 K是待检验的攻略的数量。随后 K 行每行给出一条待检攻略格式为
n V1 V2 ⋯ Vn
其中 n(≤200) 是攻略中的网红点数Vi 是路径上的网红点编号。这里假设你从家里出发从 V1 开始打卡最后从 Vn 回家。
输出格式
在第一行输出满足要求的攻略的个数。
在第二行中首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号从 1 开始然后输出这个攻略的总路费其间以一个空格分隔。如果这样的攻略不唯一则输出序号最小的那个。
题目保证至少存在一个有效攻略并且总路费不超过 109。
输入样例
6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6输出样例
3
5 11样例说明
第 2、3、4、6 条都不满足攻略的基本要求即不能做到从家里出发在每个网红点打卡仅一次且能回到家里。所以满足条件的攻略有 3 条。
第 1 条攻略的总路费是(0-5) 2 (5-1) 2 (1-4) 2 (4-3) 2 (3-6) 2 (6-2) 2 (2-0) 2 14
第 5 条攻略的总路费同理可算得1 1 1 2 3 1 2 11是一条更省钱的攻略
第 7 条攻略的总路费同理可算得2 1 1 2 2 2 1 11与第 5 条花费相同但序号较大所以不输出。
#include iostreamusing namespace std;int main()
{int n, m; //网红点的个数 N1N≤200和网红点之间通路的条数 Mcin n m;int a[201][201]; //邻接矩阵a存储网红点之间的距离int x, y, s; //两个网红点xy和路费sfor(int i 0; i m; i){cin x y s;a[x][y] s;a[y][x] s;}int num; //攻略数量cin num;int cost; // 更新符合条件的攻略的费用int mincost 0x3f3f3f3f; //更新符合条件的攻略的最小费用int sn; //更新符合条件的攻略的序号int glnum 0; //更新符合条件的攻略的数量for(int i 0; i num; i) //第i条攻略{int p; //第i条攻略经过p个网红点cin p;cost 0;int cur 0; //记录当前位置int arr[201] {0}; //记录已经到过的网红点//fill(arr, arr 201, 0); //全部赋为0符合!arr[] //不用STLint flag 0; //标记该攻略是否符合要求int k;for(int j 0; j p; j){cin k; //依次读入这p个网红点if(a[cur][k] !arr[k]) //如果两网红点可直达且下一网红点没有到达过否则该路径不符合要求{cost a[cur][k];arr[k] 1;cur k;}else{flag 1;}}cost a[k][0];if(p n a[k][0] !flag){if(cost mincost){mincost cost;sn i 1;}glnum;}}cout glnum endl sn mincost;return 0;
}R7-5 畅通工程之最低成本建设问题
某地区经过对城镇交通状况的调查得到现有城镇间快速道路的统计数据并提出“畅通工程”的目标使整个地区任何两个城镇间都可以实现快速交通但不一定有直接的快速道路相连只要互相间接通过快速路可达即可。现得到城镇道路统计表表中列出了有可能建设成快速路的若干条道路的成本求畅通工程需要的最低成本。
输入格式:
输入的第一行给出城镇数目N (1N≤1000)和候选道路数目M≤3N随后的M行每行给出3个正整数分别是该条道路直接连通的两个城镇的编号从1编号到N以及该道路改建的预算成本。
输出格式:
输出畅通工程需要的最低成本。如果输入数据不足以保证畅通则输出“Impossible”。
输入样例1:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3输出样例1:
12输入样例2:
5 4
1 2 1
2 3 2
3 1 3
4 5 4输出样例2:
Impossible#includestdio.h
#includestdlib.h
#define MAXV 1010
#define INF 9999
typedef struct Gnode{int E[MAXV][MAXV];int n,e;
}GNode;GNode *Create()
{GNode *G;G(GNode*)malloc(sizeof(GNode));if(GNULL)return NULL;int num1,num2,cost;int i,j;scanf(%d %d,(G-n),(G-e));for(i1;iG-n;i){for(j1;jG-n;j){G-E[i][j]INF;}}for(i0;iG-e;i){scanf(%d %d %d,num1,num2,cost);G-E[num1][num2]cost;G-E[num2][num1]cost;}return G;
}void Prim(GNode *G)
{int lowcost[MAXV];int count0,sum0;int min,minId;int i,j;// 初始化lowcost数组表示顶点到生成树的最短边的权重for(i1;iG-n;i){lowcost[i]G-E[1][i];}count;lowcost[1]0; // 将起点加入生成树中并将其lowcost设置为0while(countG-n){minINF;minId1;// 在lowcost数组中找到最小的权重和对应的顶点for(i1;iG-n;i){if(lowcost[i]min lowcost[i]!0){minlowcost[i];minIdi;}}sum min;count;lowcost[minId]0; // 将权重加入生成树的总权重中将顶点加入生成树并将其lowcost设置为0// 更新lowcost数组for(i1;iG-n;i){if(G-E[minId][i]lowcost[i]){lowcost[i]G-E[minId][i];}}}if(sumINF)printf(Impossible\n); // 如果生成树的总权重大于INF输出Impossibleelse printf(%d,sum); // 输出生成树的总权重}int main()
{GNode *G;GCreate(); // 创建图Prim(G); // 执行Prim算法return 0;
}
R7-6 寻宝图
给定一幅地图其中有水域有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏这些有宝藏的点也被标记出来了。本题就请你统计一下给定的地图上一共有多少岛屿其中有多少是有宝藏的岛屿。
输入格式
输入第一行给出 2 个正整数 N 和 M1N×M≤105是地图的尺寸表示地图由 N 行 M 列格子构成。随后 N 行每行给出 M 位个位数其中 0 表示水域1 表示陆地2-9 表示宝藏。 注意两个格子共享一条边时才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。
输出格式
在一行中输出 2 个整数分别是岛屿的总数量和有宝藏的岛屿的数量。
输入样例
10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001输出样例
7 2#include bits/stdc.h
using namespace std;int n, m;
typedef pairint, int PII;
mapPII, bool vis;
vectorstring mp;//判断坐标位置是否是岛屿且未被访问
bool judge(int x, int y)
{if((x0xn) (y0ym) mp[x][y]-0 !vis[{x, y}])return true;return false;
}int dx[] {0, 1, -1, 0};
int dy[] {1, 0, 0, -1};
int bfs(int a, int b)
{queuePII q;q.push({a, b});vis[{a, b}] true;bool havefalse;while(q.size()){int x q.front().first;int y q.front().second;q.pop();//判断当前岛屿坐标是否为宝藏if(mp[x][y]2 mp[x][y]9) have true;for(int i0; i4; i){int nx xdx[i];int ny ydy[i];if(judge(nx, ny)){vis[{nx, ny}] true;q.push({nx, ny});}}}if(have) return 1;return 0;
}int main()
{cinnm;getchar();for(int i0; in; i){string s;getline(cin, s);mp.push_back(s);}int cnt 0, val 0;for(int i0; in; i){for(int j0; jm; j){//找未被访问的岛屿坐标if(!(mp[i][j]-0) || vis[{i, j}]) continue;val bfs(i, j);cnt;}}coutcnt val;return 0;
}R7-7 逆散列问题
给定长度为 N 的散列表处理整数最常用的散列映射是 H(x)x%N。如果我们决定用线性探测解决冲突问题则给定一个顺序输入的整数序列后我们可以很容易得到这些整数在散列表中的分布。例如我们将 1、2、3 顺序插入长度为 3 的散列表HT[]后将得到HT[0]3HT[1]1HT[2]2的结果。
但是现在要求解决的是“逆散列问题”即给定整数在散列表中的分布问这些整数是按什么顺序插入的
输入格式
输入的第一行是正整数 N≤1000为散列表的长度。第二行给出了 N 个整数其间用空格分隔每个整数在序列中的位置第一个数位置为0即是其在散列表中的位置其中负数表示表中该位置没有元素。题目保证表中的非负整数是各不相同的。
输出格式
按照插入的顺序输出这些整数其间用空格分隔行首尾不能有多余的空格。注意对应同一种分布结果插入顺序有可能不唯一。例如按照顺序 3、2、1 插入长度为 3 的散列表我们会得到跟 1、2、3 顺序插入一样的结果。在此规定当前的插入有多种选择时必须选择最小的数字这样就保证了最终输出结果的唯一性。
输入样例
11
33 1 13 12 34 38 27 22 32 -1 21输出样例
1 13 12 21 33 34 38 27 22 32#define _CRT_SECURE_NO_WARNINGS
#includeostream
using namespace std;
#includealgorithm
const int maxn 10001;
int a[maxn], b[maxn], v1[maxn],//a是原数列b是有效值
v2[maxn], ans[maxn];//v1代表有效值是否存入v2代表取余的位置是否有存了数ans表示答案数列
int main() {int i, j, k, m0,n;scanf(%d, n);for (i 0; i n; i) {scanf(%d, a[i]);if (a[i] 0)b[m] a[i];//只存入有效数列}sort(b, b m);//保证答案数列按最小数排列for(i0;im;i)//每次循环放入ans数组一个元素for (j 0; j m; j) {//找的满足条件的元素if (v1[j])continue;int flag 0;for (k b[j] % n;;) {//k是当前这个数该存入的位置if (v2[k] 0 b[j] a[k]) {//如果条件满足当前这个数一定是最小的因为上面sort排了序v1[j] 1;v2[k] 1;ans[i] b[j];flag 1;break;}if (v2[k] 0)break;//如果发现b[j]!a[k],且v2[k]0,这说明此元素需线性探索放入//而目前未满足线性探索的条件(v2[k]!0b[j]!a[k])//后面一定还有直接放入求余位置k而//和满足线性探索条件的元素,所以跳出循环继续往下找k;//线性探索往下移动if (k n)//如果移动到n重新开始k 0;}if (flag)break;}for (i 0; i m; i) {if (i ! 0)printf( );printf(%d, ans[i]);}system(pause);return 0;
}R7-8 任务调度的合理性
假定一个工程项目由一组子任务构成子任务之间有的可以并行执行有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程各门课程可以看成是子任务。有些课程可以同时开设比如英语和C程序设计它们没有必须先修哪门的约束有些课程则不可以同时开设因为它们有先后的依赖关系比如C程序设计和数据结构两门课必须先学习前者。
但是需要注意的是对一组子任务并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B子任务B依赖于子任务C子任务C又依赖于子任务A”那么这三个任务哪个都不能先执行这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。
输入格式:
输入说明输入第一行给出子任务数N≤100子任务按1~N编号。随后N行每行给出一个子任务的依赖集合首先给出依赖集合中的子任务数K随后给出K个子任务编号整数之间都用空格分隔。
输出格式:
如果方案可行则输出1否则输出0。
输入样例1:
12
0
0
2 1 2
0
1 4
1 5
2 3 6
1 3
2 7 8
1 7
1 10
1 7输出样例1:
1输入样例2:
5
1 4
2 1 4
2 2 5
1 3
0输出样例2:
0#includebits/stdc.h
using namespace std;
vectorintv[101]; // 存储图的邻接表
int vis[101]; // 记录节点访问状态
int flag0; // 标记是否存在环路
int n; // 图中节点的数量// 深度优先搜索函数
int dfs(int x)
{for(int i0; iv[x].size(); i){if(vis[v[x][i]]0){vis[v[x][i]]1;return dfs(v[x][i]);}else{flag1; // 如果访问过的节点再次被访问说明存在环路将flag标记为1}}return 0;
}int main()
{cinn; // 输入节点的数量for(int i1; in; i){int k;cink;while(k--){int x;cinx;v[i].push_back(x); // 输入图的邻接表表示}}for(int i0; in; i){memset(vis,0,sizeof(vis)); // 初始化节点访问状态dfs(i); // 对每个节点进行深度优先搜索if(flag1)break; // 如果存在环路结束搜索}if(flag)cout0endl; // 存在环路输出0elsecout1endl; // 不存在环路输出1return 0;
}
R7-9 关键活动
假定一个工程项目由一组子任务构成子任务之间有的可以并行执行有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程各门课程可以看成是子任务。有些课程可以同时开设比如英语和C程序设计它们没有必须先修哪门的约束有些课程则不可以同时开设因为它们有先后的依赖关系比如C程序设计和数据结构两门课必须先学习前者。
但是需要注意的是对一组子任务并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B子任务B依赖于子任务C子任务C又依赖于子任务A”那么这三个任务哪个都不能先执行这就是一个不可行的方案。
任务调度问题中如果还给出了完成每个子任务需要的时间则我们可以算出完成整个工程需要的最短时间。在这些子任务中有些任务即使推迟几天完成也不会影响全局的工期但是有些任务必须准时完成否则整个项目的工期就要因此延误这种任务就叫“关键活动”。
请编写程序判定一个给定的工程项目的任务调度是否可行如果该调度方案可行则计算完成整个工程项目需要的最短时间并输出所有的关键活动。
输入格式:
输入第1行给出两个正整数N(≤100)和M其中N是任务交接点即衔接相互依赖的两个子任务的节点例如若任务2要在任务1完成后才开始则两任务之间必有一个交接点的数量。交接点按1N编号M是子任务的数量依次编号为1M。随后M行每行给出了3个正整数分别是该任务开始和完成涉及的交接点编号以及该任务所需的时间整数间用空格分隔。
输出格式:
如果任务调度不可行则输出0否则第1行输出完成整个工程项目需要的时间第2行开始输出所有关键活动每个关键活动占一行按格式“V-W”输出其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是任务开始的交接点编号小者优先起点编号相同时与输入时任务的顺序相反。
输入样例:
7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2输出样例:
17
1-2
2-4
4-6
6-7#include iostream
#include queue
#include algorithm
#define N 103
using namespace std;int indegree[N] {0}, outdegree[N] {0};
int e[N] {0}, l[N] {0};
int mp[N][N];
int maxx;// 拓扑排序并计算最早开始时间
int TopologyAndGete(int n)
{int m, cnt 0;queueint q;for (int i 1; i n; i)if (indegree[i] 0)q.push(i);while (q.size() ! 0){m q.front(); // 将入度为0的节点出队q.pop();cnt;maxx max(maxx, e[m]); // 更新最大的最早开始时间for (int i 1; i n; i){if (mp[m][i] ! 0) // 节点m到节点i有边{e[i] max(e[i], mp[m][i] e[m]); // 更新节点i的最早开始时间indegree[i]--; // 减少节点i的入度if (indegree[i] 0)q.push(i); // 如果节点i的入度为0则入队}}}return cnt n; // 返回是否所有节点都能被处理
}// 计算最晚开始时间
void Getl(int n)
{int m, cnt 0;queueint q;for (int i 1; i n; i){if (outdegree[i] 0)q.push(i); // 将出度为0的节点入队l[i] maxx; // 初始化最晚开始时间为最大的最早开始时间}while (q.size() ! 0){m q.front(); // 将出队的节点q.pop();cnt;for (int i 1; i n; i){if (mp[i][m] ! 0) // 节点i到节点m有边{l[i] min(l[i], l[m] - mp[i][m]); // 更新节点i的最晚开始时间outdegree[i]--; // 减少节点i的出度if (outdegree[i] 0)q.push(i); // 如果节点i的出度为0则入队}}}
}int main()
{int n, m;int x, y, t;cin n m;for (int i 1; i m; i){cin x y t;mp[x][y] t; // 记录有向图的边和权值outdegree[x]; // 节点x的出度加1indegree[y]; // 节点y的入度加1}if (TopologyAndGete(n)) // 进行拓扑排序并计算最早开始时间{cout maxx endl; // 输出最大的最早开始时间Getl(n); // 计算最晚开始时间for (int i 1; i n; i){if (e[i] ! l[i]) // 找出最早开始时间等于最晚开始时间的节点对continue;for (int j n; j 1; j--){if (mp[i][j] e[j] l[j] l[j] e[i] mp[i][j])printf(%d-%d\n, i, j); // 输出关键路径上的节点对}}}elsecout 0; // 如果拓扑排序不成功则输出0
}至此图的专项练习就完成了。
