PTA 7-10公路村村通、7-9旅游规划、7-8哈利波特的考试
图论的几道板子题(PTA数据结构与算法题目集)
PTA 7-10 公路村村通
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。
求出图的最小生成树即可，代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = 3*N,inf = 0x3f3f3f3f;
struct Edge{
int a,b,w;
bool operator<(const Edge& W)const
{
return w<W.w;
}
}edge[M];
int n,m;
int p[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int Kruskal()
{
sort(edge,edge+m);
for(int i = 1 ;i<=n ;i++) p[i] = i;
int cnt = 0,ans = 0;
for(int i = 0 ; i<m ; i++)
{
int a = edge[i].a, b = edge[i].b, c = edge[i].w;
a = find(a);
b = find(b);
if(a != b)
{
p[a] = b;
ans += c;
cnt++;
}
}
if(cnt != n-1)
return inf;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i = 0; i<m; i++)
{
int a,b,c;
cin>>a>>b>>c;
edge[i] = {a,b,c};
}
int ans = Kruskal();
if(ans == inf)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
PTA 7-9 旅游计划
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
单源最短路固定起点终点求最短距离，另开一个cost数组维护两地间的花费，注意数组要开的大小，有一个样例是N最大M最大的完全图，代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 510, M = N*N;
int n,m,s,d;
int dist[N],cost[N];
int e[M],h[M],ne[M],w[M],L[M],idx;
bool st[N];
queue<int> q;
int ans;
void add(int a,int b,int l,int c)
{
e[idx] = b,w[idx] = c,L[idx] = l,ne[idx] = h[a],h[a] = idx++;
}
void spfa(int u)
{
memset(dist,0x3f,sizeof dist);
memset(cost,0x3f,sizeof cost);
cost[u] = 0;
dist[u] = 0;
q.push(u);
st[u] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j]>dist[t]+L[i])
{
cost[j] = cost[t] + w[i];
dist[j] = dist[t] + L[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>s>>d;
memset(h,-1,sizeof h);
while(m --)
{
int a,b,c,L;
cin>>a>>b>>L>>c;
add(a,b,L,c);
add(b,a,L,c);
}
spfa(s);
cout<<dist[d]<<" "<<cost[d]<<endl;
return 0;
}
哈利波特的考试
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。
输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。
输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
Floyd的板子题，但答案需要在到每个点距离最大的所有点中找最小的，代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, inf = 0x3f3f3f3f;
int n,m,a,b,c;
int g[N][N];
void floyd()
{
for(int k = 1; k<=n; k++)
for(int i = 1; i<=n; i++)
for(int j = 1; j<=n; j++)
g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
}
int main()
{
cin>>n>>m;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=n ;j++)
if(i == j) g[i][j] = 0;
else g[i][j] = inf;
for(int i = 1; i<=m ;i++)
{
cin>>a>>b>>c;
g[a][b] = g[b][a] = c;
}
floyd();
int ans = inf;
int cnt = 0;
for(int i = 1; i<=n; i++)
{
int Max = 0;
for(int j = 1; j<=n; j++)
{
//cout<<i<<" "<<j<<" "<<g[i][j]<<endl;
if(g[i][j] == inf)
{
cout<<0<<endl;
return 0;
}
Max = max(Max,g[i][j]);
}
if(Max<ans)
{
ans = Max;
cnt = i;
}
}
cout<<cnt<<" "<<ans<<endl;
return 0;
}
