单位网站建设的意义,微信官网下载安装微信,网站登记表,哈尔滨ui设计培训学校题目描述 一个无环的有向图称为无环图#xff08;Directed Acyclic Graph#xff09;#xff0c;简称DAG图。 AOE(Activity On Edge)网#xff1a;顾名思义#xff0c;用边表示活动的网#xff0c;当然它也是DAG。与AOV不同#xff0c;活动都表示在了边上#xff… 题目描述 一个无环的有向图称为无环图Directed Acyclic Graph简称DAG图。 AOE(Activity On Edge)网顾名思义用边表示活动的网当然它也是DAG。与AOV不同活动都表示在了边上如下图所示 如上所示共有11项活动11条边9个事件9个顶点。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点源点和只有一个出度为零的点汇点。 关键路径是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示1 到2 到 5到7到9是关键路径关键路径不止一条请输出字典序最小的权值的和为18。 输入 这里有多组数据保证不超过10组保证只有一个源点和汇点。输入一个顶点数n(2n10000),边数m(1m 50000),接下来m行输入起点sv终点ev,权值w1sv,evn,sv ! ev,1w 20)。数据保证图连通。输出 关键路径的权值和并且从源点输出关键路径上的路径如果有多条请输出字典序最小的。示例输入 9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
8 9 4
7 9 2 示例输出 18
1 2
2 5
5 7
7 9 提示 #includestdio.h #includestdlib.h #includestack #includestring.h using namespace std; typedef struct arcnode//表结点 { int adj;//存储结点 arcnode *next; int info;//存储权值 }arcnode; typedef struct vnode//头结点 { int data; arcnode *first; }adjlist[10001]; typedef struct//图的结构 { adjlist a; int vn,an; }ALG; int n,m,i,j; int indegree[10001];//记录每个点的入度 int ve[10001];//最早开始时间 int vl[10001];//最迟开始时间 void create(ALG g)//建立有向图邻接表 { int v1,v2,w; arcnode *p; g.vnn;g.anm; for(i1;ig.vn;i) g.a[i].firstNULL;//头结点清空 for(i1;ig.an;i) { scanf(%d%d%d,v1,v2,w); pnew arcnode; p-adjv2; p-infow; indegree[v2]; p-nextg.a[v1].first; g.a[v1].firstp; } } stackints;//用于逆拓扑有序时求vl int topo1(ALG g)//求ve最早开始时间即最大路径长度 { int k; arcnode *p; stackintt; for(i1;in;i) if(!indegree[i])//入度为零的结点入栈 t.push(i); memset(ve,0,sizeof(ve));//初始化最早开始时间 int count0;//记录出栈元素个数判定拓扑排序是否有序 while(!t.empty()) { jt.top(); t.pop(); s.push(j); count; for(pg.a[j].first;p;pp-next) { kp-adj; if(!(--indegree[k]))//将新入度为零的节点进栈 t.push(k); if(ve[j]p-infove[k])//更新最大路径长度 ve[k]ve[j]p-info; } } if(countn)//拓扑不是有序的即有环 return 0; return 1; } int topo2(ALG g)//求vL既不影响施工进度的情况下最晚的开始时间 { int k; arcnode *p; if(!topo1(g)) return 0;//拓扑无序则结束 printf(%d\n,ve[n]);//关键路径的权值和 for(i1;in;i)//初始化最迟开始时间 vl[i]ve[n]; while(!s.empty())//按拓扑逆序求vl { js.top(); s.pop(); for(pg.a[j].first;p;pp-next) { kp-adj; if(vl[k]-p-infovl[j])//更新最晚开始时间 vl[j]vl[k]-p-info; } } int flag0,a,b; for(j1;jn;j)//求关键活动 for(pg.a[j].first;p;pp-next) { kp-adj; int eve[j]; int lvl[k]-p-info; if(el)//关键路径要求最早开始时间和最晚开始时间相同没有空余时间 { if(flag0)//对输出的特殊处理要求字典序最小 { aj;bk; flag1; } else if(ajbk) bk; else if(bj)//结束活动的分支时b作为活动的开始时。 { printf(%d %d\n,a,b); aj; bk; } } } printf(%d %d\n,a,b); return 1; } int main() { ALG g; while(~scanf(%d%d,n,m)) { memset(indegree,0,sizeof(indegree)); create(g); topo2(g); } return 0; } #include bits/stdc.h using namespace std; struct edge{//存储边的结构体 int v,w,pre; }p[50086]; int n,m,next[10086],head[50086],cnt,vis[10086],dis[10086],i,u,v,w; int main(){ while(~scanf(%d %d,n,m)){ memset(head,-1,sizeof(head)); memset(next,0,sizeof(next));//节点i的后继为next[i] memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis));//节点i到起点n的最长路径长度为dis[i] cnt0,vis[n]1; for(i0;im;i){ scanf(%d %d %d,v,u,w); p[cnt].vv,p[cnt].ww,p[cnt].prehead[u],head[u]cnt;//逆序添加有向边 } queueintq; q.push(n); while(!q.empty()){//SPFA算法求最长路径 uq.front(); q.pop(); vis[u]0; for(ihead[u];~i;ip[i].pre)//检查并更新节点u的所有前驱节点 if(dis[p[i].v]dis[u]p[i].w||(dis[p[i].v]dis[u]p[i].wnext[p[i].v]u)){ dis[p[i].v]dis[u]p[i].w,next[p[i].v]u;//设置节点v的后继为节点u if(!vis[p[i].v]){ q.push(p[i].v); vis[p[i].v]1; } } } printf(%d\n,dis[1]);//输出最长路径的长度 for(i1;next[i];inext[i])//输出1-n的最长路径 printf(%d %d\n,i,next[i]); } return 0; }
