USACO 4.1 Fence Loops


     这题是求无向图中的一个最小环的长度。
     主要思路是:因为边都是直线,边的两点之间的最短距离必然是这个边长。那么,再求一条到两顶点的最短距径,这个路径与边构成了一个环。这个环是包含该边的最小环。枚举一下所有边,计算出最小环即可。对于每个边,删除该边,然后计算两顶点的最短路径,再恢复该边。
     但是这个图的输入是用边表示的,一个难点就是将其转换成用点表示。这里用边的集合来表示一个点。然后用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




posted on 2009-07-17 14:26 YZY 阅读(572) 评论(0)  编辑 收藏 引用 所属分类: AlgorithmUSACO图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜