2013级DS作业和实验参考答案总汇(1)(7)

}

if(lowcost[k]==10000 || k==0) break; count_cc++;

length=length+lowcost[k];

lowcost[k]=0; //将顶点k加入集合U中 for (j=2; j<=n; j++) //调整lowcost和adjvex if (arc[k][j]

void main() { int m,i,j,k,w;; while(cin>>n>>m) { if(n==0) return; for (i=1; i<=n; i++) {for (j=1; j<=n; j++){arc[i][j]=10000;}} for (i=1; i<=n; i++)arc[i][i]=0;

}

for (k=0; k>i>>j>>w; //边依附的两个顶点的序号 arc[i][j]=w; //置有边标志 arc[j][i]=w; } Prim();

第十二次作业：图的最短路径9092，9091，9085

9092:最短路

Problem Description

“水上之都”威尼斯水城是个美丽的地方，ax幻想着某天能够去那里旅游！

一天，ax想到一个问题：

威尼斯由许多n个小岛（由0到n-1编号）以及m座桥梁连成一体！假设ax在s号小岛上，要去t号小岛游玩！那么s到t的最短距离是多少！ Input

本题目包含多组数据，每组数据第一行包含两个正整数n和m(0

再接下一行有两个整数s,t(0<=s,t

}

Output

对于每组数据，请在一行里输出最短距离，如果不存在s到t的路径则输出\。 Sample Input 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2

Sample Output

2

not found!

//9092ANSWER CODE1 #include using namespace std; int n,arc[200][200];

void Dijk(int v, int v_end)//v源点，v_end终点 { int dist[200],S[200],i,k,num,min; for (i=0; i

while (num

min=10000;k=v;//min为dist[]最小值的下标k

for (i=0; i

for (i=0; idist[k]+arc[k][i]) { dist[i]=dist[k]+arc[k][i]; } } S[num++]= k; //将k加入集合S if(k==v_end && dist[v_end]<10000) {cout<

dist[k]=0; //置k为已生成终点 } cout<<\}

void main()

{ int m,s,t,i,j,k,w; while(cin>>n>>m) { for (i=0; i>i>>j>>w;arc[i][j]=w;} cin>>s>>t; Dijk(s,t); }

}

9091:名次排序

Problem Description

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。 Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500）和M，其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1和P2，表示P1队赢了P2队。 Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。 Sample Input 4 3 1 2 2 3 4 3

Sample Output

1 2 4 3

//9091ANSWER CODE1 #include using namespace std; int n,arc[500][500]; void main()

{ int m,i,j,k,f,num,indg[500],visit[500]; while(cin>>n>>m) { for (i=1; i<=n; i++){for (j=1; j<=n; j++)arc[i][j]=0;} for(k=0;k>i>>j;arc[i][j]=1;} for (i=1; i<=n; i++){indg[i]=0;visit[i]=0;}

}

for (j=1; j<=n; j++)

{for (i=1; i<=n; i++){indg[j]+=arc[i][j];}} f=0;num=0; while(num

cout<

}

//9091ANSWER CODE2 #include using namespace std;

struct arcNode{int adjvex;arcNode *next;};

struct vertexNode{int in;int vertex;arcNode *firstedge;}; int n;vertexNode adjlist[500]; void main()

{ int m,i,j,k;arcNode *s,*p; while(cin>>n>>m) { for (i=1; i<=n; i++) { adjlist[i].in=0; adjlist[i].vertex=i; adjlist[i].firstedge=NULL; } for (k=0; k>i>>j; s=new arcNode; s->adjvex=j; s->next=adjlist[i].firstedge; adjlist[i].firstedge=s; } for(i=1; i<=n; i++) { p=adjlist[i].firstedge ; while(p){adjlist[p->adjvex].in++ ;p=p->next ;} } int S[500],top=-1,count=0,f=0; for (i=n; i>=1; i--){if (adjlist[i].in==0) S[++top]=i;}

while(top!= -1 ) //当图有入度为0的顶点时循环

}

}

{

j=S[top--]; //从栈中取出一个入度为0的顶点 if(f==0){cout<

p=adjlist[j].firstedge;//扫描顶点表，找出顶点j的所有出边 while(p) {

adjlist[p->adjvex].in--;//将入度减1，=0顶点入栈

if (adjlist[p->adjvex].in==0) S[++top]=p->adjvex; p=p->next;

} }

cout<

9085:逆邻接表

Problem Description

对每个顶点vi将所有以顶点vi为弧头的弧链接起来，形成入边表，可以建立有向图的逆邻接表，从而便于求顶点的入度。设有一有向图G，其顶点值为字符型并假设各值互不相等，要求采用逆邻接表表示法存储。设计一个算法，存储该有向图并输出各顶点的入边信息。 Input

有多组测试数据，每组数据的第一行为两个整数n和e，表示n个顶点和e条边（0

输出该有向图中所有顶点的入边信息（空表不输出任何信息），每行最后均无空格，每两组数据之间有一空行，具体格式见样例。 Sample Input 4 4 ABCD 0 1 0 3 1 2 1 3 4 4 ABCD 0 1 0 2 2 3 3 0

Sample Output 1->0 2->1