2816 - 关键路径
时间限制 : 1 秒
内存限制 : 128 MB
描述：
图的连接边上的数据表示其权值，带权值的图称作网。
<br />
<span style="font-size:10.5000pt;font-family:'宋体';">上图可描述为顶点集为</span><span style="font-size:10.5000pt;font-family:'Arial';">（<span>a,b,c,d,e)</span></span><span style="font-size:10.5000pt;font-family:'Arial';"></span>
<span style="font-size:10.5000pt;font-family:'宋体';">边集及其权值为(始点，终点 权值）：</span><span style="font-size:10.5000pt;font-family:'Arial';">a b 3</span><span style="font-size:10.5000pt;font-family:'Arial';"></span>
<span style="font-size:10.5000pt;font-family:'Arial';"> a c 2 </span><span style="font-size:10.5000pt;font-family:'Arial';"></span>
<span style="font-size:10.5000pt;font-family:'Arial';"> b d 5</span><span style="font-size:10.5000pt;font-family:'Arial';"></span>
<span style="font-size:10.5000pt;font-family:'Arial';"> c d 7</span><span style="font-size:10.5000pt;font-family:'Arial';"></span>
<span style="font-size:10.5000pt;font-family:'Arial';"> c e 4</span><span style="font-size:10.5000pt;font-family:'Arial';"></span>
<span style="font-size:10.5000pt;font-family:'Arial';"> d e 6</span><span style="font-size:10.5000pt;font-family:'Arial';"> </span><span style="font-size:10.5000pt;font-family:'Arial';"> </span><span style="font-size:10.5000pt;font-family:'宋体';"> </span><span style="font-size:10.5000pt;font-family:'宋体';"></span>
<span style="font-size:10.5000pt;font-family:'宋体';"> </span><span style="font-size:10.5000pt;font-family:'宋体';">网的源点是入度为0的顶点，汇点是出度为0的顶点。网的关键路径是指</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'Arial';background:#FFFFFF;">从源点到汇点的所有路径中，具有最大路径长度的路径</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">。上图中的关键路径为</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">a->c->d->e<span>，其权值之和为关键路径的长度为</span><span>15</span><span>。</span></span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span>
<span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"> 本题的要求是根据给出的网的邻接矩阵求该网的关键路径及其长度。</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span>
<br />
题目输入
第一行输入一个正整数n（1<=n<=5)，其代表测试数据数目，即图的数目
第二行输入x(1<=x<=15)代表顶点个数，y(1<=y<=19)代表边的条数
第三行给出图中的顶点集，共x个小写字母表示顶点
接下来每行给出一条边的始点和终点及其权值，用空格相隔，每行代表一条边。
题目输出
第一个输出是图的关键路径（用给出的字母表示顶点， 用括号将边括起来，顶点逗号相隔）
第二个输出是关键路径的长度
每个矩阵对应上面两个输出，两个输出在同一行用空格间隔，每个矩阵的输出占一行。
输入/输出样例
输入格式
2 5 6 abcde a b 3 a c 2 b d 5 c d 7 c e 4 d e 6 4 5 abcd a b 2 a c 3 a d 4 b d 1 c d 3
输出格式
(a,c) (c,d) (d,e) 15 (a,c) (c,d) 6
C语言解答
#include <stdio.h> #include <stdlib.h> #include <string.h> #define INF 1000000000 #define maxn 30 int G[maxn][maxn]; int dp[maxn]; char choice[maxn]; int N; int DP(int i) { if(dp[i] > 0) return dp[i]; for(int j = 0;j < N; j++) { if(G[i][j] != INF) { int s = DP(j) + G[i][j]; if(s > dp[i]) { dp[i] = s; choice[i]=j; } } } return dp[i]; } void print(int i) { int flag=0; while(choice[i] != -1) { printf("(%c,%c) ",i+'a',choice[i]+'a'); i = choice[i]; } } int main() { int n; while(scanf("%d",&n) != EOF) { while(n--) { int x, y; scanf("%d%d",&x,&y); N = x; for(int i = 0;i < maxn; i++) { for(int j = 0;j < maxn; j++)G[i][j]=INF; } char temp[maxn]; scanf("%s",temp); for(int i = 0;i < y; i++) { char temp1, temp2; int temp3; getchar(); scanf("%c",&temp1); getchar(); scanf("%c",&temp2); getchar(); scanf("%d",&temp3); G[temp1-'a'][temp2-'a']=temp3; } memset(dp,0,sizeof(dp)); memset(choice,-1,sizeof(choice)); int len = DP(0); print(0); printf("%d\n",len); } } return 0; }
C++解答
#include <stdio.h> #include <stdlib.h> #include <stack> using namespace std; #define INFINITY INT_MAX #define MAX_VERTEX_NUM 15 /**** 图的邻接表存储表示 ****/ typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 int w;//权值 }ArcNode; typedef struct VNode { char data; //顶点信息 ArcNode *firstarc; //指向第一条依附该点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; //图的当前顶点数和弧数 }ALGraph; int LocateVex_biao(ALGraph G, char v) { for (int i = 0; i < G.vexnum; i++) { if (G.vertices[i].data == v) return i; } } int CreateDN_biao(ALGraph &G) { //采用数组（邻接表）表示法，构造有向网G char v1, v2;//一条边所依附的两个顶点 int w;//边的权值 int i, j; scanf("%d%d", &G.vexnum, &G.arcnum); getchar(); for (i = 0; i < G.vexnum; i++) { scanf("%c", &G.vertices[i].data);//构造顶点向量 G.vertices[i].firstarc = NULL; } for (int k = 0; k < G.arcnum; k++) { getchar(); scanf("%c", &v1); getchar(); scanf("%c", &v2); getchar(); scanf("%d", &w); i = LocateVex_biao(G, v1); j = LocateVex_biao(G, v2); if (G.vertices[i].firstarc == NULL) { G.vertices[i].firstarc = (ArcNode*)malloc(sizeof(ArcNode)); G.vertices[i].firstarc->adjvex = j; G.vertices[i].firstarc->nextarc = NULL; G.vertices[i].firstarc->w = w; } else { ArcNode* p = G.vertices[i].firstarc; ArcNode* q; while (p->nextarc != NULL) p = p->nextarc; q = (ArcNode*)malloc(sizeof(ArcNode)); q->adjvex = j; q->nextarc = NULL; q->w = w; p->nextarc = q; } } return 1; } /******** 关键路径 *******/ int vl[MAX_VERTEX_NUM]; int ve[MAX_VERTEX_NUM]; void FindInDegree(ALGraph G, int *indegree) { for (int j = 0; j < G.vexnum; j++) { indegree[j] = 0;//初始化 } for (int i = 0; i < G.vexnum; i++) { ArcNode* p = G.vertices[i].firstarc; while (p != NULL) { indegree[p->adjvex]++; p = p->nextarc; } } } int TopologicalOrder(ALGraph G, stack<int> &T) { int indegree[MAX_VERTEX_NUM]; int i, j, k; stack<int> S; ArcNode* p; FindInDegree(G, indegree); //对个顶点求入度 for (i = 0; i < G.vexnum; i++) { if (indegree[i] == 0) S.push(i);//将入度为0的顶点入S栈 } int count = 0; for (i = 0; i < G.vexnum; i++) ve[i] = 0; while (!S.empty()) { j = S.top(); S.pop(); T.push(j); ++count;//j号顶点出S栈，入T栈，并计数 for (p = G.vertices[j].firstarc; p; p = p->nextarc) { k = p->adjvex; //对j号顶点的每个邻接点的入度减1 if (--indegree[k] == 0) S.push(k);//若入度为0，则入S栈 if ((ve[j] + p->w) > ve[k]) ve[k] = ve[j] + p->w; }//for }//while if (count < G.vexnum) return 0; else return 1; } int CriticalPath(ALGraph G) { stack<int> T; int i, j, k, dut; ArcNode *p,*q; int ee, el; char tag; if (!TopologicalOrder(G, T)) return 0; for (i = 0; i < G.vexnum; i++) vl[i] = ve[G.vexnum-1]; while (!T.empty()) { for (j = T.top(), T.pop(), p = G.vertices[j].firstarc; p; p = p->nextarc) { k = p->adjvex; dut = p->w; if (vl[k] - dut < vl[j]) vl[j] = vl[k] - dut; }//for }//while k = 0; for (q = G.vertices[0].firstarc; q; ) { int temp = k; for (p = q; p; p = p->nextarc) { k = p->adjvex; dut = p->w; ee = ve[temp]; el = vl[k] - dut; tag = (ee == el) ? '*' : ' '; if (tag == '*') { printf("(%c,%c) ", G.vertices[temp].data, G.vertices[k].data); q = G.vertices[k].firstarc; break; } }//for }//for printf("%d\n", ve[G.vexnum - 1]); }//CriticalPath int main() { int n; ALGraph G1; scanf("%d", &n); while (n--) { CreateDN_biao(G1); CriticalPath(G1); } return 0; }
Java解答
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; public class Main { static class R{ int vertax; int dis; int front; public R(int vertax) { this.vertax=vertax; this.dis=Integer.MAX_VALUE; this.front=-1; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; R other = (R) obj; if (vertax != other.vertax) return false; return true; } } static final int Max=Integer.MAX_VALUE; static Scanner scn=new Scanner(System.in); static int n,vertax,edge,G[][],start,end; static String vString; static Queue<R> que; static R[] form; static boolean[] inside; static List<Character> routeList; public static void main(String[] args) { n=scn.nextInt(); while(n>0) { vertax=scn.nextInt();edge=scn.nextInt(); G=new int[vertax][vertax]; que=new LinkedList<>(); inside=new boolean[vertax]; form=new R[vertax]; routeList=new ArrayList<>(); for(int i=0;i<vertax;i++) { form[i]=new R(i); } vString=scn.next();//'a'是97 int start=vString.charAt(0)-97; int end=vString.charAt(vString.length()-1)-97; for(int i=0;i<edge;i++) { int v=scn.next().charAt(0)-97; int v2=scn.next().charAt(0)-97; int w=scn.nextInt(); G[v][v2]=-w;//有向图 } sqfa(start); dfs_findroot(start, end); for(int i=0,j=1;i<routeList.size()-1;i++,j++) { char v=routeList.get(i),v2=routeList.get(j); System.out.printf("(%c,%c) ",v,v2); } System.out.println(-form[end].dis); n--; } } static void sqfa(int start) { form[start].dis=0; que.offer(form[start]); inside[start]=true; while(!que.isEmpty()) { int u=que.poll().vertax; inside[start]=false; for(int i=0;i<vertax;i++) { int v=i; if(G[u][v]!=0 && form[u].dis+G[u][v]<form[v].dis) { form[v].dis=form[u].dis+G[u][v]; form[v].front=u; while(que.remove(form[v])); que.offer(form[v]); // if(!inside[v]) { // // inside[v]=true; // } } } } } static void dfs_findroot(int start,int end) { if(end==start) { routeList.add((char) (end+'a')); return; } dfs_findroot(start, form[end].front); routeList.add((char) (end+'a')); } }