???? 這題是求無向圖中的一個最小環的長度。
???? 主要思路是：因為邊都是直線，邊的兩點之間的最短距離必然是這個邊長。那么，再求一條到兩頂點的最短距徑，這個路徑與邊構成了一個環。這個環是包含該邊的最小環。枚舉一下所有邊，計算出最小環即可。對于每個邊，刪除該邊，然后計算兩頂點的最短路徑，再恢復該邊。
???? 但是這個圖的輸入是用邊表示的，一個難點就是將其轉換成用點表示。這里用邊的集合來表示一個點。然后用map<set<int>,int>來存儲某一邊對應的邊的編號。每找到一個新的頂點則分配一個新的編號。這部分主要通過函數get_vertex(set<int>&s)來實現。
代碼如下：
#include?<iostream>
#include?<fstream>
#include?<set>
#include?<map>
#include?<climits>
#include?<cstring>
using?namespace?std;
ifstream?fin("fence6.in");
ofstream?fout("fence6.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
struct?Edge{
????int?va,vb,len;
};
int?edge_num;
int?vertex_num;
int?graph[100][100];
Edge?edges[100];
int?get_vertex(set<int>&s)
{
????static?map<set<int>,int>vertex;
????if(?vertex.find(s)?==?vertex.end()?){
????????vertex[s]?=?vertex_num;
????????return?vertex_num++;
????}else{
????????return?vertex[s];
????}
}
void?build_graph()
{
????in>>edge_num;
????for(int?i=0;i<100;++i)
????????for(int?j=0;j<100;++j)
????????????graph[i][j]?=?INT_MAX/2;
????for(int?i=0;i<edge_num;++i){
????????int?edge,tmp,len;
????????int?left_num,right_num;
????????set<int>?s;
????????in>>edge>>len>>left_num>>right_num;
????????s.insert(edge);
????????for(int?j=0;j<left_num;++j){
????????????in>>tmp;
????????????s.insert(tmp);
????????}
????????int?left_vertex?=?get_vertex(s);
????????s.clear();
????????s.insert(edge);
????????for(int?j=0;j<right_num;++j){
????????????in>>tmp;
????????????s.insert(tmp);
????????}
????????int?right_vertex?=?get_vertex(s);
????????graph[left_vertex][right_vertex]?=?
????????????graph[right_vertex][left_vertex]?=?len;
????????edges[i].va?=?left_vertex;
????????edges[i].vb?=?right_vertex;
????????edges[i].len?=?len;
????}
}
int?shortest_path(int?va,int?vb)
{
????int?shortest[100];
????bool?visited[100];
????memset(visited,0,sizeof(visited));
???
????for(int?i=0;i<vertex_num;++i){
????????shortest[i]?=?graph[va][i];
????}
????visited[va]?=?true;
????while(true){
????????int?m?=?-1;
????????for(int?i=0;i<vertex_num;++i){
??????????????if(!visited[i]){
????????????????if(m==-1||shortest[i]<shortest[m])
????????????????????m?=?i;
??????????????}
????????}
????????//沒有新加結點了
????????
????????visited[m]?=?true;
????????if(?m==vb?)
????????????return?shortest[vb];
????????for(int?i=0;i<vertex_num;++i){
????????????if(!visited[i])
????????????shortest[i]?=?min(shortest[i],shortest[m]+graph[m][i]);
????????}
????}
}
void?solve()
{
????build_graph();
????int?best?=?INT_MAX;
????for(int?i=0;i<edge_num;++i){
??????graph[edges[i].va][edges[i].vb]?=?graph[edges[i].vb][edges[i].va]?=?INT_MAX/2;?
??????best?=?min(best,edges[i].len+shortest_path(edges[i].va,edges[i].vb)?);
??????graph[edges[i].va][edges[i].vb]?=?graph[edges[i].vb][edges[i].va]?=?edges[i].len;?
????}
????out<<best<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
Fence Loops
The fences that surround Farmer Brown's collection of pastures have
gotten out of control. They are made up of straight segments from 1
through 200 feet long that join together only at their endpoints though
sometimes more than two fences join together at a given endpoint. The
result is a web of fences enclosing his pastures. Farmer Brown wants to
start to straighten things out. In particular, he wants to know which of
the pastures has the smallest perimeter.
Farmer Brown has numbered his fence segments from 1 to N (N = the
total number of segments). He knows the following about each fence
segment:
- the length of the segment
- the segments which connect to it at one end
- the segments which connect to it at the other end.
Happily, no fence connects to itself.
Given a list of fence segments that represents a set of surrounded
pastures, write a program to compute the smallest perimeter of any pasture.
As an example, consider a pasture arrangement, with fences numbered 1 to
10 that looks like this one (the numbers are fence ID numbers):
1
+---------------+
|\ /|
2| \7 / |
| \ / |
+---+ / |6
| 8 \ /10 |
3| \9 / |
| \ / |
+-------+-------+
4 5
The pasture with the smallest perimeter is the one that is enclosed
by fence segments 2, 7, and 8.
PROGRAM NAME: fence6
INPUT FORMAT
| Line 1: | N (1 <= N <= 100) |
| Line 2..3*N+1: | N sets of three line records:
- The first line of each record contains four integers:
s, the segment number (1 <= s <= N); Ls, the
length of the segment (1 <= Ls <= 255);
N1s (1 <= N1s <= 8) the number of
items on the subsequent line; and N2sthe number of
items on the line after that (1 <= N2s <= 8).
- The second line of the record contains N1 integers, each
representing a connected line segment on one end of the fence.
- The third line of the record contains N2 integers, each
representing a connected line segment on the other end of the
fence.
|
SAMPLE INPUT (file fence6.in)
10
1 16 2 2
2 7
10 6
2 3 2 2
1 7
8 3
3 3 2 1
8 2
4
4 8 1 3
3
9 10 5
5 8 3 1
9 10 4
6
6 6 1 2
5
1 10
7 5 2 2
1 2
8 9
8 4 2 2
2 3
7 9
9 5 2 3
7 8
4 5 10
10 10 2 3
1 6
4 9 5
OUTPUT FORMAT
The output file should contain a single line with a single integer that
represents the shortest surrounded perimeter.
SAMPLE OUTPUT (file fence6.out)
12