n个城市由k条公路网连接（一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市)，证

n个城市间有k条相互连接的直达公路.证明:当k＞时

过这些公路在任何两个城市间旅行.

A.5, 4, 3, 3, 2, 2

B.5.,5, 4, 3, 2. I

C.5, 4. 4, 3, 1, 1

D.5, 4. 4, 3, 2. 2

A.南北

B.东西

C.西北

D.西南

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。

【说明】设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。本程序，输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站0出发乘公交车至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G(用邻接矩阵g表示)，有向图的顶点是车站，若有某条公交线路经i站到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j＞。如果这样，从站点x至站点y的最少上车次数便对应图G中从点x到点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

include ＜stdio.h＞

define M 20

define N 50

int a[N+1]； /*用于存放一条线路上的各站编号*/

int g[N][N]； /*严存储对应的邻接矩阵*/

int dist[N]； /*严存储站0到各站的最短路径*/

int m, n；

void buildG()

{ int i, j, k, sc, dd

printf(“输入公交线路数，公交站数\n”)；

scanf("%d%d"，&m，＆n)；

for (i=0；i＜n；i++) /*邻接矩阵清0*/

for(j=0；j＜n；j++)

g[i][j]=0；

for(i=0；i＜m；i++)

{ printf("沿第%d条公交线路的各站编号(0＜=编号＜=%d，-1结束)：\n)"，i+1，n-1)；

sc=0； /* 当前线路站计数器*/

while(1)

{ scanf("%d"，&dd)；

if(dd＝-1)break；

if(dd＞=0 && dd＜n) (1)；

}

a[sc]=-1；

for(k=1；a[k]＞=0；k++) /*处理第i+1条公交线路*/

for(j=0；j＜k；j++)

g (2)=1；

}

}

int minLen()

{ int j，k；

for(j=0；j＜n；j++)

dist[j]=g[0][j]；

dist[0]=1；

do{

for(k=-1，j=0；j＜n；j++) /*找下一个最少上车次数的站*/

if(dist[j]＞0 &&(k==-1｜｜dist[j]＜dist[k]))

k=j；

if(k＜0｜｜k＝=n-1)

break；

dist[k]=-dist[k]； /*设置k站已求得上车次数的标记*/

for (j=1；j＜n；j++) /*调整经过k站能到达的其余各站的上车次数*/

if((3)&& (dist[j]＝0｜｜-dist[k]+1＜dist[j]))

dist[j]=(4)；

}while(1)；

j=dist[n-1]；

return (5)；

}

void main()

{ int t；

buildG()；

if((t=minLen())＜0)

printf("无解!\n")；

else

printf(“从0号站到%d站需换车%d次\n”，n-1，t)；

}

阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站0出发乘公交车至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G(用邻接矩阵g表示)，有向图的顶点是车站，若有某条公交线路经i站能到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j＞。如是这样，从站点x至站点y的最少上车次数便对应图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

【函数5-9】

include ＜stdio.h＞

define M 20

define N 50

int a[N+1]; /*用于存放一条线路上的各站编号*/

iht g[N][N]; /*存储对应的邻接矩阵*/

int dist[N]; /*存储站0到各站的最短路径*/

int m,n;

void buildG()

{

int i,j,k,sc,dd;

printf ("输入公交线路数，公交站数\n");

scanf("%d%d", &m, &n);

for(i=0; i＜n; i++) /*邻接矩阵清0*/

for(j = 0; j ＜ n; j++)g[i][j] = 0;

for(i=0; i＜m; i++){

printf("沿第%d条公交车线路前进方向的各站编号(O＜=编号＜=%d,-1结束):\n",

i+1, n-1);

sc=0;/* 当前线路站计数器 */

while(1){

scanf("%d",&dd);

if(dd==-1)break;

if(dd＞=0 && dd＜n) (1);

}

a[sc]=-1;

for(k=1;a[k]＞=0; k++) /* 处理第i+1条公交线路 */

for(j=0; j＜k; j++)

g(2)=1;

}

}

int minLen()

{

int j, k;

for(j=0;j＜n;j++)dist[j]=g[0][j];

dist[0]=1;

do{

for(k=-1,j=0;j＜n;j++) /* 找下一个最少上车次数的站*/

if(dist[j]＞0&&(k==-1 || dist[j]＜dist[k]))k=j;

if (k＜0 || k==n-1) break;

dist[k]=-dist[k]; /* 设置k站已求得上车次数的标记 */

for(j=1;j＜n;j++) /* 调整经过k站能到达的其余各站的上车次数 */

if ((3) && (dist[j]==0 || -dist[k]+1＜dist[j]))

dist[j]=(4);

}while(1);

j=dist[n-1];

return (5);

}

void main()

{

int t；

buildG();

if((t=minLen()＜0)printf("无解!\n");

else pdnff("从0号站到%d站需换车%d次\n”，n-1，t)；

}

A.92

B.82

C.81

D.73

问题描述:给定一条直线L上的n个点,每个点x_i,都有权值w(i)≥0,以及在该点设置服务机构的费用c(i)≥0.每个服务机构的覆盖半径为r.直线k覆盖问题是要求找出的一个子集在点集S处设置服务机构,使总覆盖费用达到最小.

每个点x_i都是一个客户.每个点x_i到服务机构S的距离定义为.如果客户x_i在S的服务覆盖范围内,即,则其服务费用为0,否则其服务费用为w(i).

服务机构S的总覆盖费用为

式中,I(j,S)的定义为

算法设计:对于给定直线L上的n个点,计算在直线L上最多设置k处服务机构的最小覆盖费用.

数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、k和r.n表示直线L上有n个点;k是服务机构总数的上限;r是服务机构的覆盖半径.接下来的n行中,每行有3个整数.第i+1行的3个整数x_i、w_i、c_i分别表示x(i)、w(i)和c(i).

结果输出:将计算的最小覆盖费用输出到文件output.txt.