题目描述

有 N 头奶牛（3 <= N <= 100）在田地中间吃草。为了防止它们走丢，农夫约翰想把它们连成一个圈，即奶牛 i 与奶牛 i-1 和 i+1 相连（奶牛 N 与奶牛 1 相连以完成这个圈）。

每头奶牛都有一些它喜欢的吃草地点，并且只有当它位于其中一个喜欢的地点时才会开心。假设农夫约翰在安置奶牛时必须保证它们开心，计算他将所有奶牛连成圈所需的最短绳子长度。圈的不同部分可能会相互交叉。

输入

• 第一行：整数 N。
• 第 2 行到第 N+1 行：每行描述一头奶牛，使用几个空格分隔的整数。第一个整数是这头奶牛喜欢的地点数量 S（1 <= S <= 40）。接下来是 2*S 个整数，表示这些地点的 (x, y) 坐标。坐标范围是 -100 到 100。

输出

一行，包含一个整数，表示所需的最短绳子长度的 100 倍（对于这个结果不需要进行特殊的四舍五入）。

示例输入

4
1 0 0
2 1 0 2 0
3 -1 -1 1 1 2 2
2 0 1 0 2

示例输出

400

提示

[奶牛 1 位于 (0,0)；奶牛 2 位于 (1,0)；奶牛 3 位于 (1,1)；奶牛 4 位于 (0,1)。]

来源

USACO 2003 年 2 月 Orange 组

题意分析

已知有 N 头奶牛在田地中吃草，为防止奶牛走丢，农夫约翰要将奶牛连成一个圈（奶牛 i 和奶牛 i - 1、奶牛 i + 1 相连，奶牛 N 和奶牛 1 相连）。每头奶牛都有若干个喜欢的吃草地点，且只有在喜欢的地点时奶牛才会开心。现在需要在保证每头奶牛都开心（即每头奶牛都在自己喜欢的地点）的前提下，计算将所有奶牛用绳子连成圈所需的最短绳子长度，最后输出最短绳子长度的 100 倍。

解题思路

1. 数据输入与初始化：读入奶牛的数量 n 以及每头奶牛喜欢的地点数量 s[i] 和地点坐标，并将每个奶牛喜欢的地点信息存储在 v[i] 中。同时，初始化距离数组 dis[j][k] ，表示第 j 头奶牛的第 k 个喜欢的地点与其他奶牛喜欢的地点之间的距离，初始值设为一个很大的数 999999999 。
2. 计算距离：
   • 首先，对于奶牛 1 的每个喜欢的地点 i ，计算它与奶牛 2 的每个喜欢的地点 j 之间的距离，并存储在 dis[2][j] 中。
   • 然后，对于奶牛 3 到奶牛 n ，对于每头奶牛 j 的每个喜欢的地点 k ，遍历前一头奶牛 j - 1 的所有喜欢的地点 l ，计算从奶牛 j - 1 的地点 l 到奶牛 j 的地点 k 的距离 td ，更新 dis[j][k] 为 dis[j][k] 和 td + dis[j - 1][l] 中的较小值。
   • 最后，对于奶牛 n 的每个喜欢的地点 j ，计算从奶牛 1 的地点 i 到奶牛 n 的地点 j 的距离 td ，更新 dis[1][i] 为 dis[1][i] 和 td + dis[n][j] 中的较小值。
3. 确定最短距离：在对奶牛 1 的所有喜欢的地点进行上述操作后，ans 初始值为 -1 ，通过比较 ans 和 dis[1][i] ，取较小值更新 ans ，最终得到最短的绳子长度。
4. 输出结果：将 ans 乘以 100 ，转换为题目要求的输出格式（最短绳子长度的 100 倍），并输出结果。

算法标签

1. 图论 - 路径规划：将奶牛及其喜欢的地点看作图中的节点，奶牛之间的连接关系看作边，通过计算节点之间的距离来规划最短路径（绳子长度）。
2. 动态规划：在计算每头奶牛的每个喜欢的地点与其他奶牛喜欢的地点之间的距离时，利用动态规划的思想，通过状态转移方程 dis[j][k]=dis[j][k]>td+dis[j-1][l]?td+dis[j-1][l]:dis[j][k] 来更新距离，以找到最短的连接路径。
3. 暴力枚举：对奶牛 1 的每个喜欢的地点进行枚举，计算不同情况下的最短绳子长度，最后取最小值，属于暴力枚举的思想。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
struct point
{
    double x;
    double y;
};
vector<point> v[110];
double dist(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double dis[110][50];
int main()
{
    int n,i,j,t,k,l,s[110];
    double td,ans;
    point p;
    scanf("%d",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%d",s+i);
        v[i].clear();
        for (j=0; j<s[i]; j++)
        {
            scanf("%lf%lf",&p.x,&p.y);
            v[i].push_back(p);
        }
    }
    ans=-1;
    for (i=0; i<s[1]; i++)
    {
        for (j=1; j<=n; j++)
        {
            for (k=0; k<s[j]; k++)
            {
                dis[j][k]=999999999;
            }
        }
        for (j=0; j<s[2]; j++)
        {
            dis[2][j]=dist(v[1][i],v[2][j]);
        }
        for (j=3; j<=n; j++)
        {
            for (k=0; k<s[j]; k++)
            {
                for (l=0; l<s[j-1]; l++)
                {
                    td=dist(v[j-1][l],v[j][k]);
                    dis[j][k]=dis[j][k]>td+dis[j-1][l]?td+dis[j-1][l]:dis[j][k];
                }
            }
        }
        for (j=0; j<s[n]; j++)
        {
            td=dist(v[1][i],v[n][j]);
            dis[1][i]=dis[1][i]>td+dis[n][j]?td+dis[n][j]:dis[1][i];
        }
        if (ans == -1 || ans > dis[1][i])
            ans=dis[1][i];
    }
//    for (j=1; j<=n; j++)
//        {
//            for (k=0; k<v[j].size(); k++)
//            {
//                printf("%f ",dis[j][k]);
//                dis[j][k]=999999999;
//            }
//            printf("\n");
//        }
    ans*=100.0;
    printf("%d\n",(int)ans);
}