7-1 列出连通集给定一个有 n 个顶点和 m 条边的无向图请用深度优先遍历DFS和广度优先遍历BFS分别列出其所有的连通集。假设顶点从 0 到 n−1 编号。进行搜索时假设我们总是从编号最小的顶点出发按编号递增的顺序访问邻接点。输入格式:输入第 1 行给出 2 个整数 n (0n≤10) 和 m分别是图的顶点数和边数。随后 m 行每行给出一条边的两个端点。每行中的数字之间用 1 空格分隔。输出格式:按照{ v1​ v2​ ... vk​ }的格式每行输出一个连通集。先输出 DFS 的结果再输出 BFS 的结果。输入样例:8 6 0 7 0 1 2 0 4 1 2 4 3 5输出样例:{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }实现代码#includebits/stdc.h using namespace std; int n,m; int g[11][11],vist[11]; void dfs(int x){ coutx ; vist[x]1; for(int i0;in;i){ if(vist[i]0g[x][i]) dfs(i); } } void bfs(int x){ coutx ; vist[x]1; queueint q; q.push(x); while(q.size()){ int tq.front(); q.pop(); for(int i0;in;i){ if(vist[i]0g[t][i]){ couti ; vist[i]1; q.push(i); } } } } int main(){ cinnm; while(m--){ int a,b; cinab; g[a][b]g[b][a]1; } for(int i0;in;i){ if(vist[i]0){ cout{ ; dfs(i); cout}endl; } } memset(vist,0,sizeof(vist)); for(int i0;in;i){ if(vist[i]0){ cout{ ; bfs(i); cout}endl; } } return 0; }7-2 哈利·波特的考试哈利·波特要考试了他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是 haha将老鼠变成鱼的魔咒是 hehe 等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念例如 ahah 可以将老鼠变成猫。另外如果想把猫变成鱼可以通过念一个直接魔咒 lalala也可以将猫变老鼠、老鼠变鱼的魔咒连起来念hahahehe。现在哈利·波特的手里有一本教材里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场要考察他把这只动物变成任意一只指定动物的本事。于是他来问你带什么动物去可以让最难变的那种动物即该动物变为哈利·波特自己带去的动物所需要的魔咒最长需要的魔咒最短例如如果只有猫、鼠、鱼则显然哈利·波特应该带鼠去因为鼠变成另外两种动物都只需要念 4 个字符而如果带猫去则至少需要念 6 个字符才能把猫变成鱼同理带鱼去也不是最好的选择。输入格式:输入说明输入第 1 行给出两个正整数 n (≤100)和 m其中 n 是考试涉及的动物总数m 是用于直接变形的魔咒条数。为简单起见我们将动物按 1~$$n编号。随后m行每行给出了3个正整数分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(\le 100$$)数字之间用空格分隔。输出格式:输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的则输出 0。如果有若干只动物都可以备选则输出编号最小的那只。输入样例:6 11 3 4 70 1 2 1 5 4 50 2 6 50 5 6 60 1 3 70 4 6 60 3 6 80 5 1 100 2 4 60 5 2 80输出样例:4 70实现代码#includebits/stdc.h using namespace std; const int NN0x3f3f3f3f; int g[111][111]; int n,m; void f(int n,int g[111][111]){ for(int k1;kn;k){ for(int i1;in;i){ for(int j1;jn;j){ g[i][j]min(g[i][j],g[i][k]g[k][j]); } } } } int maxdis(int n,int x,int g[111][111]){ int dis-1; for(int i1;in;i){ dismax(dis,g[x][i]); } return dis; } int main(){ cinnm; memset(g,NN,sizeof(g)); for(int i0;in;i){ for(int j0;jn;j){ if(ij) g[i][j]0; } } while(m--){ int x,y,z; cinxyz; g[x][y]g[y][x]z; } f(n,g); int mindisNN,mini1,dis; for(int i1;in;i){ dismaxdis(n,i,g); if(mindisdis){ mindisdis; minii; } } if(mindisNN){ cout0; } else coutmini mindis; }7-3 旅游规划有了一张自驾旅游路线图你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的那么需要输出最便宜的一条路径。输入格式:输入说明输入数据的第 1 行给出 4 个正整数 n、m、s、d其中 n2≤n≤500是城市的个数顺便假设城市的编号为 0~(n−1)m 是高速公路的条数s 是出发地的城市编号d 是目的地的城市编号。随后的 m 行中每行给出一条高速公路的信息分别是城市 1、城市 2、高速公路长度、收费额中间用空格分开数字均为整数且不超过 500。输入保证解的存在。输出格式:在一行里输出路径的长度和收费总额数字间以空格分隔输出结尾不能有多余空格。输入样例:4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20输出样例:3 40实现代码#includebits/stdc.h using namespace std; int n,m,s,d; const int N555,NN0x3f3f3f3f; int dl[N][N],dr[N][N]; int len[N],cost[N]; int vist[N]; void dj(int s){ memset(len,NN,sizeof(len)); memset(cost,NN,sizeof(cost)); len[s]0,cost[s]0; for(int i0;in;i){ int t-1; for(int j0;jn;j){ if(vist[j]0(t-1||len[j]len[t])) tj; } vist[t]1; for(int j0;jn;j){ if(len[j]len[i]dl[i][j]){ len[j]len[i]dl[i][j]; cost[j]cost[i]dr[i][j]; } else if(len[j]len[i]dl[i][j]){ cost[j]min(cost[j],cost[i]dr[i][j]); } } } } int main(){ memset(dl,NN,sizeof(dl)); memset(dr,NN,sizeof(dr)); cinnmsd; while(m--){ int a,b,x,y; cinabxy; dl[a][b]dl[b][a]x; dr[a][b]dr[b][a]y; } dj(s); coutlen[d] cost[d]; return 0; }7-4 家庭房产给定每个人的家庭成员和其自己名下的房产请你统计出每个家庭的人口数、人均房产面积及房产套数。输入格式输入第一行给出一个正整数N≤1000随后N行每行按下列格式给出一个人的房产编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积其中编号是每个人独有的一个4位数的编号父和母分别是该编号对应的这个人的父母的编号如果已经过世则显示-1k0≤k≤5是该人的子女的个数孩子i是其子女的编号。输出格式首先在第一行输出家庭个数所有有亲属关系的人都属于同一个家庭。随后按下列格式输出每个家庭的信息家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出若有并列则按成员编号的升序输出。输入样例10 6666 5551 5552 1 7777 1 100 1234 5678 9012 1 0002 2 300 8888 -1 -1 0 1 1000 2468 0001 0004 1 2222 1 500 7777 6666 -1 0 2 300 3721 -1 -1 1 2333 2 150 9012 -1 -1 3 1236 1235 1234 1 100 1235 5678 9012 0 1 50 2222 1236 2468 2 6661 6662 1 300 2333 -1 3721 3 6661 6662 6663 1 100输出样例3 8888 1 1.000 1000.000 0001 15 0.600 100.000 5551 4 0.750 100.000实现代码#includebits/stdc.h using namespace std; typedef long long ll; #define endl \n const ll N 2e57; ll n,m,k,sum; double tao,fang; string s; mapstring,setstring mp; mapstring,pairll,ll cc; mapstring,boolvis; setstringR; struct node{ string id; ll rk; double tao,mj; }v[N]; queuestringq; void bfs(){ ll lenq.size(); for(ll i 0 ; i len ; i ){ string nameq.front(); q.pop(); if(vis[name])continue; smin(s,name); vis[name]1; sum; taocc[name].first; fangcc[name].second; for(auto j : mp[name]){ if(vis[j])continue; q.push(j); } } if(!q.empty())bfs(); } bool cmp(node a,node b){ if(a.mj ! b.mj) return a.mj b.mj; return a.id b.id; } void solve(){ cin n; ll c0,x,y; while(n --){ string sx,sy,ss; cin s sx sy k; R.insert(s); if(sx ! -1)mp[s].insert(sx),mp[sx].insert(s); if(sy ! -1)mp[s].insert(sy),mp[sy].insert(s); for(ll i 0 ; i k ; i ) cin ss, mp[s].insert(ss),mp[ss].insert(s); cin x y,cc[s]{x,y}; } for(auto i : R){ if(vis[i])continue; q.push(i); si,tao0,sum0,fang0; bfs(); v[c].ids,v[c].rksum,v[c].taotao/sum,v[c].mjfang/sum; c; } cout c endl; sort(v,vc,cmp); for(ll i 0 ; i c ; i ) printf(%s %d %.3f %.3f\n,v[i].id.c_str(),v[i].rk,v[i].tao,v[i].mj); return ; } int main(){ ll t1;//cin t; while(t --)solve(); return 0; }7-5 森森美图森森最近想让自己的朋友圈熠熠生辉所以他决定自己写个美化照片的软件并起名为森森美图。众所周知在合照中美化自己的面部而不美化合照者的面部是让自己占据朋友圈高点的绝好方法因此森森美图里当然得有这个功能。 这个功能的第一步是将自己的面部选中。森森首先计算出了一个图像中所有像素点与周围点的相似程度的分数分数越低表示某个像素点越“像”一个轮廓边缘上的点。 森森认为任意连续像素点的得分之和越低表示它们组成的曲线和轮廓边缘的重合程度越高。为了选择出一个完整的面部森森决定让用户选择面部上的两个像素点A和B则连接这两个点的直线就将图像分为两部分然后在这两部分中分别寻找一条从A到B且与轮廓重合程度最高的曲线就可以拼出用户的面部了。 然而森森计算出来得分矩阵后突然发现自己不知道怎么找到这两条曲线了你能帮森森当上朋友圈的小王子吗为了解题方便我们做出以下补充说明图像的左上角是坐标原点(0,0)我们假设所有像素按矩阵格式排列其坐标均为非负整数即横轴向右为正纵轴向下为正。忽略正好位于连接A和B的直线注意不是线段上的像素点即不认为这部分像素点在任何一个划分部分上因此曲线也不能经过这部分像素点。曲线是八连通的即任一像素点可与其周围的8个像素连通但为了计算准确某像素连接对角相邻的斜向像素时得分额外增加两个像素分数和的2​倍减一。例如样例中经过坐标为(3,1)和(4,2)的两个像素点的曲线其得分应该是这两个像素点的分数和(22)再加上额外的(22)乘以(2​−1)即约为5.66。输入格式输入在第一行给出两个正整数N和M5≤N,M≤100表示像素得分矩阵的行数和列数。接下来N行每行M个不大于1000的非负整数即为像素点的分值。最后一行给出用户选择的起始和结束像素点的坐标(Xstart​,Ystart​)和(Xend​,Yend​)。4个整数用空格分隔。输出格式在一行中输出划分图片后找到的轮廓曲线的得分和保留小数点后两位。注意起点和终点的得分不要重复计算。输入样例6 6 9 0 1 9 9 9 9 9 1 2 2 9 9 9 2 0 2 9 9 9 1 1 2 9 9 9 3 3 1 1 9 9 9 9 9 9 2 1 5 4输出样例27.04实现代码#includebits/stdc.h using namespace std; const int N105; int n,m,vis[N][N],sx,sy,ex,ey; double s[N][N],d[N][N],mi; const double PIsqrt(2)-1; int dir[8][2] {1,0,-1,0,0,1,0,-1,1,1,-1,-1,1,-1,-1,1}; struct T { int x,y; } a,b,p; int cross(T a,T b,T p) { return (b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x); } void spfa() { memset(vis,0,sizeof vis),memset(d,0x7f,sizeof d); a{sx,sy},b{ex,ey}; d[sx][sy]s[sx][sy]; queueTQ; Q.push(a); while(!Q.empty()) { int xQ.front().x,yQ.front().y; Q.pop(); vis[x][y]0; for(int i0; i8; i) { double w0; p.xxdir[i][0],p.yydir[i][1]; if(p.x0||p.xn||p.y0||p.ym) continue; if(cross(a,b,p)0||p.xexp.yey) { ws[p.x][p.y]; if(i3) ww(s[x][y]s[p.x][p.y])*PI; if(d[p.x][p.y]d[x][y]w) { d[p.x][p.y]d[x][y]w; if(!vis[p.x][p.y])Q.push(p),vis[p.x][p.y]1; } } } } mid[ex][ey]; } int main() { scanf(%d%d,n,m); for(int i0; in; i) for(int j0; jm; j) cins[i][j]; scanf(%d%d%d%d,sy,sx,ey,ex); mi-s[ex][ey]-s[sx][sy]; spfa(); swap(ex,sx),swap(ey,sy); spfa(); printf(%.2f,mi); return 0; }7-6 邻接矩阵表示法创建无向图采用邻接矩阵表示法创建无向图G 依次输出各顶点的度。输入格式:输入第一行中给出2个整数i(0i≤10)j(j≥0)分别为图G的顶点数和边数。输入第二行为顶点的信息每个顶点只能用一个字符表示。依次输入j行每行输入一条边依附的顶点。输出格式:依次输出各顶点的度行末没有最后的空格。输入样例:5 7 ABCDE AB AD BC BE CD CE DE输出样例:2 3 3 3 3实现代码#includebits/stdc.h using namespace std; int n,m; int din[11]; int main(){ cinnm; string s; cins; while(m--){ char a,b; cinab; int xa-A; int yb-A; din[x]; din[y]; } for(int i0;in;i){ coutdin[i]; if(in-1) cout ; } return 0; }7-7 邻接表创建无向图采用邻接表创建无向图G 依次输出各顶点的度。输入格式:输入第一行中给出2个整数i(0i≤10)j(j≥0)分别为图G的顶点数和边数。输入第二行为顶点的信息每个顶点只能用一个字符表示。依次输入j行每行输入一条边依附的顶点。输出格式:依次输出各顶点的度行末没有最后的空格。输入样例:5 7 ABCDE AB AD BC BE CD CE DE输出样例:2 3 3 3 3实现代码#includebits/stdc.h using namespace std; int n,m; vectorvectorint v(11); int main(){ cinnm; string s; cins; while(m--){ char a,b; cinab; int xa-A; int yb-A; v[x].push_back(y); v[y].push_back(x); } for(int i0;in;i){ coutv[i].size(); if(in-1) cout ; } return 0; }7-8 单源最短路径请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点编号为0至n-1以顶点0作为源点。输入格式:输入第一行为两个正整数n和e分别表示图的顶点数和边数其中n不超过20000e不超过1000。接下来e行表示每条边的信息每行为3个非负整数a、b、c其中a和b表示该边的端点编号c表示权值。各边并非按端点编号顺序排列。输出格式:输出为一行整数为按顶点编号顺序排列的源点0到各顶点的最短路径长度不含源点到源点每个整数后一个空格。如源点到某顶点无最短路径则不输出该条路径长度。输入样例:4 4 0 1 1 0 3 1 1 3 1 2 0 1输出样例:1 1实现代码#includebits/stdc.h using namespace std; int n,m; const int N2e410,NN0x3f3f3f3f; int vist[N],dist[N]; typedef pairint,int pill; vectorpill v[N]; priority_queuepill,vectorpill,greaterpill q; void dj(){ memset(dist,NN,sizeof(dist)); dist[0]0; q.push({dist[0],0}); while(q.size()){ pill tq.top(); q.pop(); int at.first; int bt.second; if(vist[b]) continue; vist[b]1; for(int i0;iv[b].size();i){ pill tempv[b][i]; int ctemp.first; int dtemp.second; if(dist[c]ad){ dist[c]ad; } q.push({dist[c],c}); } } } int main(){ cinnm; while(m--){ int a,b,c; cinabc; v[a].push_back({b,c}); } dj(); for(int i1;in;i){ if(dist[i]NN) coutdist[i] ; } return 0; }7-9 图深度优先遍历编写程序对给定的有向图不一定连通进行深度优先遍历图中包含n个顶点编号为0至n-1。本题限定在深度优先遍历过程中如果同时出现多个待访问的顶点则优先选择编号最小的一个进行访问以顶点0为遍历起点。输入格式:输入第一行为两个整数n和e分别表示图的顶点数和边数其中n不超过20000e不超过50。接下来e行表示每条边的信息每行为两个整数a、b表示该边的端点编号但各边并非按端点编号顺序排列。输出格式:输出为一行整数每个整数后一个空格即该有向图的深度优先遍历结点序列。输入样例1:3 3 0 1 1 2 0 2输出样例1:0 1 2输入样例2:4 4 0 2 0 1 1 2 3 0输出样例2:0 1 2 3实现代码#includebits/stdc.h using namespace std; int n,m; const int N2e410; vectorvectorint v(N); int vist[N]; void dfs(int x){ coutx ; vist[x]1; for(int i0;iv[x].size();i){ if(vist[v[x][i]]0) dfs(v[x][i]); } } int main(){ cinnm; while(m--){ int a,b; cinab; v[a].push_back(b); } for(int i0;in;i){ sort(v[i].begin(),v[i].end()); } for(int i0;in;i){ if(vist[i]0){ dfs(i); } } return 0; }7-10 公路村村通现有村落间道路的统计数据表中列出了有可能建设成标准公路的若干条道路的成本求使每个村落都有公路连通所需要的最低成本。输入格式:输入数据包括城镇数目正整数 n≤1000和候选道路数目 m≤3n随后的 m 行对应 m 条道路每行给出 3 个正整数分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见城镇从 1 到 n 编号。输出格式:输出村村通需要的最低成本。如果输入数据不足以保证畅通则输出 −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输出样例:12实现代码#includebits/stdc.h using namespace std; int n,m; const int N1e310,NN0x3f3f3f3f; int g[N][N],dist[N],vist[N]; int dj(){ int sum0; memset(dist,NN,sizeof(dist)); dist[1]0; for(int i0;in;i){ int t-1; for(int j1;jn;j){ if(vist[j]0(t-1||dist[j]dist[t])) tj; } vist[t]1; if(i){ if(dist[t]NN) return NN; else sumdist[t]; } for(int j0;jn;j){ dist[j]min(dist[j],g[t][j]); } } return sum; } int main(){ memset(g,NN,sizeof(g)); cinnm; while(m--){ int a,b,c; cinabc; g[a][b]g[b][a]c; } int tdj(); if(tNN) cout-1; else coutt; return 0; }7-11 关键活动假定一个工程项目由一组子任务构成子任务之间有的可以并行执行有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程各门课程可以看成是子任务。有些课程可以同时开设比如英语和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 bits/stdc.h using namespace std; typedef struct{ int v1, v2; int w; int id; }bian; int cmp(bian a, bian b){ if (a.v1!b.v1)return a.v1 b.v1; return a.idb.id; } int main() { int v,e; scanf(%d%d,v,e); bian bian1[e];bian bian2[e]; int matrix[v1][v1],deg[v1]; memset(deg, 0, sizeof(deg)); memset(matrix, 0, sizeof(matrix)); for (int i0;ie;i){ scanf(%d%d%d,bian1[i].v1,bian1[i].v2,bian1[i].w); bian1[i].idi; matrix[bian1[i].v1][bian1[i].v2]bian1[i].w; deg[bian1[i].v2]; } stackint ver1; stackint ver2; for (int i 1; i v 1; i){ if (deg[i] 0){ ver1.push(i); } } int degin[v1],degout[v1],num0,sum0; memset(degin, 0, sizeof(degin)); while (!ver1.empty()) { int vvver1.top(); ver1.pop(); ver2.push(vv); num; for (int i1;iv;i){ if (matrix[vv][i]! 0){ deg[i]--; degin[i] max(matrix[vv][i] degin[vv], degin[i]); sum max(degin[i], sum); if (deg[i] 0){ ver1.push(i); } } } } if (num ! v)printf(0\n); else{ for(int i1;iv;i) degout[i]sum; while(!ver2.empty()){ int vvver2.top(); ver2.pop(); for(int i1;iv;i){ if (matrix[i][vv]!0) degout[i]min(degout[vv]-matrix[i][vv],degout[i]); } } printf(%d\n,sum); int sum10; for(int i0;ie;i) if (degin[bian1[i].v1]degout[bian1[i].v2]-matrix[bian1[i].v1][bian1[i].v2]) bian2[sum1] bian1[i]; sort(bian2, bian2sum1, cmp); for (int i0;isum1;i) printf(%d-%d\n,bian2[i].v1,bian2[i].v2); } return 0; }7-12 哥尼斯堡的“七桥问题”哥尼斯堡是位于普累格河上的一座城市它包含两个岛屿及连接它们的七座桥如下图所示。可否走过这样的七座桥而且每桥只走过一次瑞士数学家欧拉(Leonhard Euler1707—1783)最终解决了这个问题并由此创立了拓扑学。这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面可画过图中每条边仅一次且可以回到起点的一条回路。现给定一个无向图问是否存在欧拉回路输入格式:输入第一行给出两个正整数分别是节点数 n 1≤n≤1000和边数 m随后的 m 行对应 m 条边每行给出一对正整数分别是该条边直接连通的两个节点的编号节点从1到 n 编号。输出格式:若欧拉回路存在则输出 1否则输出 0。输入样例1:6 10 1 2 2 3 3 1 4 5 5 6 6 4 1 4 1 6 3 4 3 6输出样例1:1输入样例2:5 8 1 2 1 3 2 3 2 4 2 5 5 3 5 4 3 4输出样例2:0实现代码#includebits/stdc.h using namespace std; int n,m; const int N1e310; int g[N][N],din[N],vist[N]; void dfs(int x){ vist[x]1; for(int i1;in;i){ if(vist[i]0g[x][i]) dfs(i); } } int main(){ cinnm; while(m--){ int a,b; cinab; g[a][b]g[b][a]1; din[a],din[b]; } dfs(1); int sum0,cnt0; for(int i1;in;i){ if(vist[i]!1) sum; } if(sum0) cout0; else{ for(int i1;in;i){ if(din[i]%2!0) cnt; } if(cnt0) cout0; else cout1; } return 0; }7-13 任务调度的合理性假定一个工程项目由一组子任务构成子任务之间有的可以并行执行有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程各门课程可以看成是子任务。有些课程可以同时开设比如英语和 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实现代码#include bits/stdc.h using namespace std; const int N 200; vectorint v[N]; int n; int in_degree[N]; bool vis[N]; int main(){ cin n; for (int i 1; i n; i){ int k; cin k; for (int j 0; j k; j){ int a; cin a; v[a].push_back(i); in_degree[i]; } } int cnt 0; queueint q; for (int i 1; i n; i){ if (in_degree[i] 0){ q.push(i); cnt; } } while (!q.empty()){ int t q.front(); q.pop(); for (int i 0; i v[t].size(); i){ if (!vis[v[t][i]]){ in_degree[v[t][i]]--; if (in_degree[v[t][i]] 0){ cnt; q.push(v[t][i]); } } } } if (cnt n) cout 1; else cout 0; return 0; }7-14 最短工期一个项目由若干个任务组成任务之间有先后依赖顺序。项目经理需要设置一系列里程碑在每个里程碑节点处检查任务的完成情况并启动后续的任务。现给定一个项目中各个任务之间的关系请你计算出这个项目的最早完工时间。输入格式首先第一行给出两个正整数项目里程碑的数量 N≤100和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行每行给出一项任务的描述格式为“任务起始里程碑 任务结束里程碑 工作时长”三个数字均为非负整数以空格分隔。输出格式如果整个项目的安排是合理可行的在一行中输出最早完工时间否则输出Impossible。输入样例 19 12 0 1 6 0 2 4 0 3 5 1 4 1 2 4 1 3 5 2 5 4 0 4 6 9 4 7 7 5 7 4 6 8 2 7 8 4输出样例 118输入样例 24 5 0 1 1 0 2 2 2 1 3 1 3 4 3 2 5输出样例 2Impossible实现代码#includebits/stdc.h using namespace std; int n,m; const int NN0x3f3f3f3f; int din[111],g[111][111],dist[111]; int main(){ memset(g,NN,sizeof(g)); cinnm; while(m--){ int a,b,c; cinabc; g[a][b]c; din[b]; } int sum0; int ans0; while(1){ int fa0; for(int i0;in;i){ if(din[i]0){ din[i]--; sum; fa1; for(int j0;jn;j){ if(g[i][j]NN){ din[j]--; dist[j]max(dist[j],dist[i]g[i][j]); ansmax(ans,dist[j]); } } } } if(fa0) break; } if(sumn) coutans; else coutImpossible; return 0; }7-15 最短路径给定一个有N个顶点和E条边的无向图顶点从0到N−1编号。请判断给定的两个顶点之间是否有路径存在。如果存在给出最短路径长度。这里定义顶点到自身的最短路径长度为0。进行搜索时假设我们总是从编号最小的顶点出发按编号递增的顺序访问邻接点。输入格式:输入第1行给出2个整数N(0N≤10)和E分别是图的顶点数和边数。随后E行每行给出一条边的两个顶点。每行中的数字之间用1空格分隔。最后一行给出两个顶点编号ij0≤i,jN,i和j之间用空格分隔。输出格式:如果i和j之间存在路径则输出The length of the shortest path between i and j is X.X为最短路径长度否则输出There is no path between i and j.。输入样例1:7 6 0 1 2 3 1 4 0 2 1 3 5 6 0 3输出样例1:The length of the shortest path between 0 and 3 is 2.输入样例2:7 6 0 1 2 3 1 4 0 2 1 3 5 6 0 6输出样例2:There is no path between 0 and 6.实现代码#includebits/stdc.h using namespace std; int n,m; const int NN0x3f3f3f3f; int g[11][11]; int main(){ memset(g,NN,sizeof(g)); cinnm; while(m--){ int a,b; cinab; g[a][b]g[b][a]1; } for(int i0;in;i){ for(int j0;jn;j){ if(ij) g[i][j]0; } } for(int k0;kn;k){ for(int i0;in;i){ for(int j0;jn;j){ g[i][j]min(g[i][j],g[i][k]g[k][j]); } } } int a,b; cinab; if(g[a][b]NN) coutThere is no path between a and b.; else coutThe length of the shortest path between a and b is g[a][b].; return 0; }7-16 最短路径算法(Floyd-Warshall)在带权有向图G中求G中的任意一对顶点间的最短路径问题也是十分常见的一种问题。解决这个问题的一个方法是执行n次迪杰斯特拉算法这样就可以求出每一对顶点间的最短路径执行的时间复杂度为O(n3)。而另一种算法是由弗洛伊德提出的时间复杂度同样是O(n3)但算法的形式简单很多。在本题中读入一个有向图的带权邻接矩阵即数组表示建立有向图并使用Floyd算法求出每一对顶点间的最短路径长度。输入格式:输入的第一行包含1个正整数n表示图中共有n个顶点。其中n不超过50。以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数如果大于0则表示第i个顶点有指向第j个顶点的有向边且权值为对应的整数值如果这个整数为0则表示没有i指向j的有向边。当i和j相等的时候保证对应的整数为0。输出格式:共有n行每行有n个整数表示源点至每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径输出-1。对于某个顶点到其本身的最短路径长度输出0。请在每个整数后输出一个空格并请注意行尾输出换行。输入样例:4 0 3 0 1 0 0 4 0 2 0 0 0 0 0 1 0输出样例:0 3 2 1 6 0 4 7 2 5 0 3 3 6 1 0实现代码#includebits/stdc.h using namespace std; int n; const int NN0x3f3f3f3f; int g[55][55]; int main(){ cinn; memset(g,NN,sizeof(g)); for(int i0;in;i){ for(int j0;jn;j){ int a; cina; if(a0) g[i][j]a; if(ij) g[i][j]0; } } for(int k0;kn;k){ for(int i0;in;i){ for(int j0;jn;j){ g[i][j]min(g[i][j],g[i][k]g[k][j]); } } } for(int i0;in;i){ for(int j0;jn;j){ if(g[i][j]NN) coutg[i][j] ; else cout-1 ; } coutendl; } return 0; }