UC知道pascal 搜索的问题(高难度)
来源：百度知道 编辑：UC知道 时间：2024/06/10 18:45:55
道路维修
NOIP组委会最近收到一个紧急任务，某省给组委会发了一份地图，这份地图给出了该省一些城市的连通情况：任两个城市之间是用一条或多条公路连接起来的，出可以没有公路相连，但是每个城市都可以直接或间接的到达另外的所有城市，注意这些公路是可以双向行驶的。由于最近天降大雨造成山泥倾泻，使得车辆在这些公路行驶变得不安全，于是该省决定尽快对某些公路进行维修，以保障行车的安全。
该省对所有公路情况都进行了勘查，分析估计了维修某段公路所需要花费的时间，并记录在地图里面。现在该省希望组委会能找到一个方案，该方案决定出哪些公路需要维修，使得维修后的公路仍能保证任意两城市之间都能直接或间接的相连，同时为了安全起见，即使某一条维修的公路被山泥阻隔了，任意两城市间仍能保持这个性质。由于时间很紧，组委会还需保证找到的这个方案总维修时间最少。
输入格式（输入文件road.in）
输入文件有多组数据。第1行为一个整数t，为case总数。接下来按顺序给出每个case的描述，首先是两个整数n，m（1<=n<=12,1<=m<=40）,为城市数量与公路数量，维修该公路专需要c个单位时间。注意上面所说的两城市间可能有多条公路。
输出格式（输出文件名road.out）
按顺序输出每个case的结果，如果找不到一个合适的方案，则输出一行“impossible”，否则输出一个整数，为最优方案维修所需的总时间。
输入输出样例
输入(road.in)
2
4 6
1 2 1
1 3 2
1 3 3
2 4 2
3 4 1
2 3 1
2 1
1 2 3
输出(road.out)
6
IMPOSSIBLE
三楼的朋友，你说的太深了，可否编个程序，Pascal？
NOIP组委会最近收到一个紧急任务，某省给组委会发了一份地图，这份地图给出了该省一些城市的连通情况：任两个城市之间是用一条或多条公路连接起来的，出可以没有公路相连，但是每个城市都可以直接或间接的到达另外的所有城市，注意这些公路是可以双向行驶的。由于最近天降大雨造成山泥倾泻，使得车辆在这些公路行驶变得不安全，于是该省决定尽快对某些公路进行维修，以保障行车的安全。
该省对所有公路情况都进行了勘查，分析估计了维修某段公路所需要花费的时间，并记录在地图里面。现在该省希望组委会能找到一个方案，该方案决定出哪些公路需要维修，使得维修后的公路仍能保证任意两城市之间都能直接或间接的相连，同时为了安全起见，即使某一条维修的公路被山泥阻隔了，任意两城市间仍能保持这个性质。由于时间很紧，组委会还需保证找到的这个方案总维修时间最少。
输入格式（输入文件road.in）
输入文件有多组数据。第1行为一个整数t，为case总数。接下来按顺序给出每个case的描述，首先是两个整数n，m（1<=n<=12,1<=m<=40）,为城市数量与公路数量，维修该公路专需要c个单位时间。注意上面所说的两城市间可能有多条公路。
输出格式（输出文件名road.out）
按顺序输出每个case的结果，如果找不到一个合适的方案，则输出一行“impossible”，否则输出一个整数，为最优方案维修所需的总时间。
输入输出样例
输入(road.in)
2
4 6
1 2 1
1 3 2
1 3 3
2 4 2
3 4 1
2 3 1
2 1
1 2 3
输出(road.out)
6
IMPOSSIBLE
三楼的朋友，你说的太深了，可否编个程序，Pascal？
这题直接DFS加些剪枝,针对这个数据规模应该没有问题.
当然我觉得可以考虑状态压缩DP
F[i,j,k]表示从i号出发,现在j号,且已经经过的点的集合为k(k是一个n位的二进制数).所需要的最小时间.这样就不超过2^12*12^次了.
或者考虑随机调整.
var rp:int64;
i:longint;
begin
for i:=1 to 0 do
begin
for j:=1 to 0 do
inc(rp);
rp:=rp*rp;
end;
writeln('Congratulations!!');
end.
因为“某一条维修的公路被山泥阻隔了，任意两城市间仍能保持这个性质”,又要花费最少，所以所选的公路必定是一个环，这个环包涵了所有的节点，并且边的权值和最小。
而对于寻找一个满足条件环，方式上深搜显然优于款搜，并且搜索的起点是可以任意选择的。
如果说成这样你还不会做，那我只能说你在这方面没什么前途了