usaco training 4.1.3 fence6 题解

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.

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

OUTPUT FORMAT

这道题可以看出是求最小环。因为n的范围很小，可以采用如下方法：

①floyd求最小环（更推荐这个，因为代码简洁）

②用最短路的dijskra算法或是SPFA算法，每次删掉一条边求最短路，如果从左侧顶点到右侧定点仍存在最短路，那么加上这条边后，就是一个最小环了。同时更新答案。

但是我想说，这两种方法都不好O(∩_∩)O~~

因为读入的是边集而不是我们日常做的点集，所以在转化的过程中会比较麻烦。推荐用DFS直接0ms秒过。

代码：

/*
ID:juan1973
LANG:C++
PROG:fence6
*/
 
#include<stdio.h>
#include<cstring>
using namespace std;
const int maxn=101;
int num[maxn][2],map[maxn][2][10],f[maxn],n,i,ans,start,c,j;
bool flag[maxn];
int find(int a,int b)
{
  for (int i=1;i<=num[b][0];i++)
    if (map[b][0][i]==a) return 0;
  return 1;
}
void dfs(int k,int d,int s)
{
  if (s>ans) return;
  if (k==start&&s>0) {ans=s;return;}
  flag[k]=true;
  for (int i=1;i<=num[k][d];i++)
  {
    int go=map[k][d][i];
    if (!flag[go]||go==start) dfs(go,1-find(k,go),s+f[k]);
  }
  flag[k]=false;
}
int main()
{
  freopen("fence6.in","r",stdin);
  freopen("fence6.out","w",stdout);
  scanf("%ld",&n);
  for (i=1;i<=n;i++)
  {
    scanf("%ld",&c);
    scanf("%ld%ld%ld",&f[c],&num[c][0],&num[c][1]);
    for (j=1;j<=num[c][0];j++) scanf("%ld",&map[c][0][j]);
    for (j=1;j<=num[c][1];j++) scanf("%ld",&map[c][1][j]);
  }
  ans=9999999;
  for (start=1;start<=n;start++)
    {
      memset(flag,0,sizeof(flag));
      dfs(start,0,0);
    }
  printf("%ld\n",ans);
  return 0;
}
//果断放弃一下转化代码。  

/*for (i=1;i<=n;i++)
  
    scanf("%ld%ld%ld%ld",&p[i],&map_e[i],&map[0][p[i]][0],map[1][p[i]][0]);
    for (j=1;j<=map[0][p[i]][0];j++) scanf("%ld",&map[0][p[i]][j]);
    for (j=1;j<=map[1][p[i]][0];j++) scanf("%ld",&map[1][p[i]][j]);
  }
  flag[0][1]=true;now_e=1;now_v;cnt=1;
  while (true)
  {
    for (i=1;i<=n;i++) 
      {
        find=false;
        for (j=0;j<=1;j++)
          for (k=1;k<=map[j][i][0];k++)
            if (map[j][i][k]==now_e)*/                   

usaco training 4.1.3 fence6 题解,布布扣,bubuko.com

usaco training 4.1.3 fence6 题解

原文：http://blog.csdn.net/jiangshibiao/article/details/19932419