P1550 [USACO08OCT]打井Watering Hole

    • 538通过
    • 1K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 图论 贪心 USACO 2008
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    John的农场缺水了!!!

    题目描述

    Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

    Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).

    Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

    Determine the minimum amount Farmer John will have to pay to water all of his pastures.

    POINTS: 400

    农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若

    干井,并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。

    请求出农民John 需要为连通整个牧场的每一块田地所需要的钱数。

    输入输出格式

    输入格式:

    第1 行为一个整数n。

    第2 到n+1 行每行一个整数,从上到下分别为W_1 到W_n。

    第n+2 到2n+1 行为一个矩阵,表示需要的经费(P_ij)。

    输出格式:

    只有一行,为一个整数,表示所需要的钱数。

    输入输出样例

    输入样例#1: 复制
    4
    5
    4
    4
    3
    0 2 2 2
    2 0 3 3
    2 3 0 4
    2 3 4 0
    输出样例#1: 复制
    9

    说明

    John等着用水,你只有1s时间!!!

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。