PTA 174-177

7-174 六度空间

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。

“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤103，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。

输出格式:

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

输入样例:

输出样例:

1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

代码长度限制

16 KB

时间限制

2500 ms

内存限制

64 MB

#include <bits/stdc++.h>
using namespace std;
struct node{int bh;//编号int deep;//深度
};
bool g[1001][1001],book[1001];
int bfs(int index,int n){queue<node>p;p.push({index,1});int count=1;book[index]=1;    while(!p.empty()){int i;for(i=0;i<n;i++){//每一次都是由表头拓展出来的所以就是表头的深度加1if(p.front().deep>6)break;if(g[p.front().bh][i]==1&&book[i]==0){p.push({i,p.front().deep+1});book[i]=1;count++;//被拓展出来的结点有几个那么就count就加几}}p.pop();//弹出队列首个元素}return count;
}
int main(){int n,m;scanf("%d%d",&n,&m);int i;memset(g,0,sizeof(0));int b,c;for(i=0;i<m;i++){scanf("%d%d",&b,&c);g[b-1][c-1]=1;g[c-1][b-1]=1;}for(i=0;i<n;i++){memset(book,0,sizeof(book));//对标记元素进行清空操作。int count=bfs(i,n);double k;k=(double)count/n*100;printf("%d: %.2lf%%\n",i+1,k);}system("pause");
}

7-175 城市间紧急救援

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include <stdio.h>
#include <stdlib.h>#define INFINITY 1000000
#define MaxVertexNum 500  /* maximum number of vertices */
typedef int Vertex;      /* vertices are numbered from 0 to MaxVertexNum-1 */
typedef int WeightType;typedef struct GNode *PtrToGNode;
struct GNode{int Nv;int Ne;WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;MGraph ReadG(int N,int M)
{MGraph G=(MGraph)malloc(sizeof(struct GNode));G->Nv=N;G->Ne=M;int i,j;for(i=0;i<G->Nv;i++){for(j=0;j<G->Nv;j++){G->G[i][j]=INFINITY;if(i==j)G->G[i][j]=0;}}for(i=0;i<G->Ne;i++){int a,b,x;scanf("%d%d%d",&a,&b,&x);G->G[a][b]=x;G->G[b][a]=x;}return G;
}
void ShortestDist( MGraph Graph, int dist[], int count[], Vertex S ,int path[],int *team,const int *oldteam)
{int i,j;int ask[MaxVertexNum];for(i=0;i<MaxVertexNum;i++)ask[i]=0;while(1){int min=INFINITY;int minindex=0;int flag=1;for(i=0;i<Graph->Nv;i++){if(!ask[i]){flag=0;if(dist[i]<=min){minindex=i;min=dist[i];}}}if(flag)break;ask[minindex]=1;for(i=0;i<Graph->Nv;i++){if(Graph->G[minindex][i]!=INFINITY&&i!=minindex){if((dist[minindex]+Graph->G[minindex][i])<dist[i]){if(!ask[i]){//dist更新，同时path,team更新dist[i]=dist[minindex]+Graph->G[minindex][i];count[i]=count[minindex];path[i]=minindex;team[i]=oldteam[i]+team[minindex];}}else if((dist[minindex]+Graph->G[minindex][i])==dist[i]){//dist相等时，比较team，team大的那个是新的pathcount[i]+=count[minindex];if(team[i]<oldteam[i]+team[minindex]) {team[i] = oldteam[i] + team[minindex];path[i] = minindex;}}}}}for(i=0;i<Graph->Nv;i++){if(dist[i]==INFINITY){dist[i]=-1;count[i]=0;}}
}
int main()
{int N,M,S,D;scanf("%d%d%d%d",&N,&M,&S,&D);int team[N];//team动态存储当前路径下的救援队总数int oldteam[N];//oldteam为固定的每个城市的救援队数目int path[N];//最优路径存储int count[N];//最短路径条数int dist[N];//最短路径长度int i;for(i=0;i<N;i++){scanf("%d",&team[i]);oldteam[i]=team[i];count[i]=0;path[i]=-1;dist[i]=INFINITY;if(i==S)count[i]=(dist[i]=0)+1;}MGraph G=ReadG(N,M);ShortestDist( G,dist, count,S,path,team,oldteam);
printf("%d %d\n",count[D],team[D]);
//路径逆序输出
int stack[MaxVertexNum+1];
i=D;
int top=-1;
stack[++top]=i;
while(path[i]!=-1)
{stack[++top]=path[i];i=path[i];
}int first=1;
while(top!=-1)
{if(first==1){printf("%d",stack[top--]);first++;}elseprintf(" %d",stack[top--]);
}
printf("\n");return 0;
}

7-176 选取医院建立的位置

设a、b、c、d、e、f表示一个乡的6个村庄,弧上的权值表示两村之间的距离。现要在这6个村庄中选择一个村庄建一所医院,问医院建在哪个村庄才能使离医院最远的村庄到医院的距离最短?

输入格式:

输入的第一行为村庄个数
输入的其他是多个存在组成网络的邻接矩阵表示

输出格式:

输出医院建立的位置

输入样例:

在这里给出一组输入。例如：

6
0 12 3 65535 9 10
12 0 65535 2 6 65535
3 65535 0 2 65535 6
65535 2 2 0 4 7
9 6 65535 4 0 4
10 65535 6 7 4 0

输出样例:

在这里给出相应的输出。例如：

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include <stdio.h>
#include <stdlib.h>
#define MAX 65535
int a[10010][10010], vis[10010], rem[10010], n;///存放数据数组，标记访问数组，保存最小距离数组，记录点总的个数
void dijkstra(int start)
{memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)rem[i]=MAX;rem[start]=0;for(int k=1;k<=n;k++){int s=-1;for(int i=1;i<=n;i++)if(vis[i]==0&&(s==-1||rem[i]<rem[s])) ///s=-1 为第一次，rem[i]<rem[s] 找到所有距离中最小距离，因为要找多次，所以不用break，并且找到之后才标记访问s=i;vis[s]=1;for(int j=1;j<=n;j++)if(rem[s]+a[s][j]<=rem[j])rem[j]=rem[s]+a[s][j];}
}int findLocation()
{int minnumber=1,minsum=MAX,tempsum=-MAX;for(int i=1;i<=n;i++) ///找到每次dijkstra中的最远 距离 ，并找到这些最远距离中的最小距离即可{tempsum=-MAX;dijkstra(i);for(int j=1;j<=n;j++)if(rem[j]>tempsum)tempsum=rem[j];if(tempsum<minsum){minsum=tempsum;minnumber=i;}}return minnumber;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);int location=findLocation();printf("%c",'a'+location-1);return 0;
}

7-177 喊山

喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。（图文摘自：http://news.xrxxw.com/newsshow-8018.html）

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：

输入第一行给出3个正整数n、m和k，其中n（≤10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（≤10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：

依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：

输出样例：

代码长度限制

16 KB

时间限制

150 ms

内存限制

64 MB

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,k;
int vis[10005],dis[10005];
struct node
{int v;struct node*next;
}head[10005];void add(int u,int v)
{struct node*p=new node;p->v=v;p->next=head[u].next;head[u].next=p;
}void dfs(int st,int sum)
{struct node *p=head[st].next;for(;p!=NULL;p=p->next){int v=p->v;if(!vis[v]){vis[v]=1;dfs(v,sum+1);vis[v]=0;}}dis[st]=min(dis[st],sum);
}void print()
{int Max=0;int i;int ans=0;
//    for(i=1;i<=n;++i)
//    {
//       printf("%d ",dis[i]);
//    }
//   printf("\n");for(i=1;i<=n;++i){if(dis[i]>Max&&dis[i]!=inf){Max=dis[i];ans=i;}if(dis[i]==Max&&i<ans){ans=i;}}printf("%d\n",ans);
}
int main()
{scanf("%d%d%d",&n,&m,&k);int i;int u,v;for(i=1;i<=n;++i){head[i].next=NULL;}for(i=0;i<m;++i){scanf("%d%d",&u,&v);add(u,v);add(v,u);}int st;while(k--){scanf("%d",&st);for(i=1;i<=n;++i){vis[i]=0;dis[i]=inf;}dis[st]=0;vis[st]=1;dfs(st,0);print();}return 0;
}