专栏首页数据结构与算法185. [USACO Oct08] 挖水井

185. [USACO Oct08] 挖水井

185. [USACO Oct08] 挖水井

★★   输入文件:water.in   输出文件:water.out 简单对比 时间限制:1 s   内存限制:128 MB

农夫约翰决定给他的N(1<=N<=300)个牧场浇水,这些牧场被自然的命名为1..N。他可以给一个牧场引入水通过在这个牧场挖一口井或者修一条管道使这个牧场和一个已经有水的牧场连接。

在牧场i挖一口井的花费是w_i(1<=w_i<=100000)。修建一条水管连接牧场i和牧场j的花费是p_ij(1<=p_ij<=100000;p_ij=p_ji;p_ii=0)。

请确定农夫约翰为了完成浇灌所有的牧场所需的最小的总花费。

题目名称:water

输入格式:

  • 第1行:一个单独的整数n。
  • 第2..n+1行:第i+1行包含一个单独的整数w_i。
  • 第n+2..2n+1行:第n+1+i行包含n个用空可分开的整数;其中第j个数是p_ij。

输入样例(file water.in):

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输入说明:

这里有4个牧场,修井和修管道的代价如图。

输出格式:

  • 第1行:一个单独的整数,表示花费。

输出样例(file water.out):

9

输出说明:

农夫约翰可以在第4个牧场修井,并且将每个牧场和第一个连接起来,这样,花费是3+2+2+2=9。

思路:一看到最小花费,就应该想到Kruskal算法,但是这个题有一个不同的地方就是多了一个挖水井的花费,这样的话我们要想用Kruskal算法解题就应该把他挖水井所用的花费一起加入到边中。我们可以将第i条边接到第n+1(这个本身不存在)条边上,这样在来跑Kruskal,跑出来的就一定是最小话费

    其实这道题理论上用贪心也可以,我一开始就是这么做的,无奈贪心的时候逻辑太混乱,贪到最后都不知道应该贪谁了。。。。。(但自测贪心可以过n<=4的所有情况)、

错因:1.思路没打开

   2.贪心没贪好

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=100001;
 7 const int maxn=0x7fffffff;
 8 int n;
 9 int w[MAXN];
10 int f[MAXN];
11 struct node
12 {
13     int u;
14     int v;
15     int w;
16 }edge[MAXN];
17 int num=1;
18 int comp(const node & a,const node & b)
19 {
20     if(a.w<b.w)
21     return 1;
22     else 
23     return 0;
24 }
25 int find(int x)
26 {
27     if(f[x]!=x)
28     f[x]=find(f[x]);
29     return f[x];
30 }
31 void unionn(int x,int y)
32 {
33     int fx=find(x);
34     int fy=find(y);
35     f[fx]=fy;
36 }
37 int main()
38 {
39     freopen("water.in","r",stdin);
40     freopen("water.out","w",stdout);
41     scanf("%d",&n);
42     for(int i=1;i<=n;i++)f[i]=i;
43     for(int i=1;i<=n;i++)
44         scanf("%d",&w[i]);
45     for(int i=1;i<=n;i++)
46     {
47         for(int j=1;j<=n;j++)
48         {
49             scanf("%d",&edge[num].w);
50             edge[num].u=i;
51             edge[num].v=j;
52             num++;
53         }
54     }
55     for(int i=1;i<=n;i++)//  将挖水井所需要的花费做成一条从i到n+1的边 
56     {
57         edge[num].u=i;
58         edge[num].v=n+1;
59         edge[num].w=w[i];
60         num++;
61         edge[num].u=edge[num-1].v;
62         edge[num].v=edge[num-1].u;
63         edge[num].w=w[i];
64         num++;
65     }
66     sort(edge+1,edge+num,comp);
67     int k=0;
68     long long int tot=0;
69     for(int i=1;i<=num;i++)
70     {
71         if(find(edge[i].u)!=find(edge[i].v))
72         {
73             unionn(edge[i].u,edge[i].v);
74             tot=tot+edge[i].w;
75             k++;
76         }
77         if(k==n)
78         break;
79     }
80     printf("%lld",tot);
81     return 0;
82 }

贪心代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<queue>
  7 #include<stack>
  8 using namespace std;
  9 const int MAXN=100001;
 10 const int maxn=0x7fffffff;
 11 int wa[MAXN];
 12 int vis[MAXN];// 记录每个点是否已经被挖 
 13 int map[1001][1001];
 14 struct node
 15 {
 16     int u;
 17     int v;
 18     int w;
 19     int next;
 20 }edge[MAXN]; 
 21 int num=1;
 22 int head[MAXN];
 23 long long int tot;// 结果 
 24 int k;// 建立树 需要的边数 
 25 int n;
 26 int flag2=0;//记录到底有没有挖坑 
 27 int kcomp(const node & a,const node & b)
 28 {
 29     if(a.w<b.w)
 30     return 1;
 31     else return 0;
 32 }
 33 void find()//  找出不需要参与建立最小生成树的边 并删除 
 34 {
 35     for(int i=1;i<=n;i++)
 36     {
 37         int flag=1;// 默认需要挖 
 38         for(int j=head[i];j!=-1;j=edge[j].next)
 39         {
 40             if(edge[j].w<wa[i]&&edge[j].u!=edge[j].v)
 41             {
 42                 flag=0;
 43                 break;
 44             }
 45         }
 46         if(flag==1)
 47         {
 48             if(flag2==1)k--;
 49             flag2=1;
 50             tot=tot+wa[i];
 51             wa[i]=maxn;// 删除这个点 
 52             vis[i]=1;
 53             
 54         }
 55     }
 56 } 
 57 void kruskal()
 58 {
 59     for(int i=1;i<=num;i++)
 60     {
 61         if(k==0)break;
 62         if((vis[edge[i].u]==0||vis[edge[i].v]==0)||(map[edge[i].u][edge[i].v]==0))
 63         {
 64             if(edge[i].v<=edge[i].u)
 65             continue;
 66             if(vis[edge[i].u]==0)
 67             vis[edge[i].u]=1;
 68             else if(vis[edge[i].v]==0)
 69             vis[edge[i].v]=1;
 70             map[edge[i].u][edge[i].v]=1;
 71             map[edge[i].v][edge[i].u]=1;
 72             tot=tot+edge[i].w;
 73             k--;
 74         }
 75     }
 76 }
 77 int main()
 78 {
 79     freopen("water.in","r",stdin);
 80     freopen("water.out","w",stdout);
 81     scanf("%d",&n);
 82     for(int i=1;i<=n;i++)head[i]=-1;
 83     k=n-1;
 84     for(int i=1;i<=n;i++)
 85         scanf("%d",&wa[i]);
 86     for(int i=1;i<=n;i++)
 87     {
 88         for(int j=1;j<=n;j++)
 89         {
 90             scanf("%d",&edge[num].w);
 91             edge[num].u=i;
 92             edge[num].v=j;
 93             edge[num].next=head[i];
 94             head[i]=num++;
 95         }
 96     } 
 97     find();//  找出不需要参与建立最小生成树的边 
 98     sort(edge+1,edge+num,kcomp);
 99     kruskal();// 用剩余的边建立最小生成树 
100     sort(wa+1,wa+1+n);
101     if(wa[1]!=maxn&&flag2==0)
102     tot=tot+wa[1];
103     printf("%lld",tot);
104     fclose(stdin);
105     fclose(stdout);
106     return 0;
107 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1401 城市(30分,正解网络流)

    题目描述 N( )个城市,M( )条无向边,你要找T( )条从城市1到城市N的路,使得最长的边的长度最小,边不能重复用。 输入输出格式 输入格式: 第1行...

    attack
  • P1726 上白泽慧音(0分)

    题目描述 在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够...

    attack
  • 03:丛林中的路

    总时间限制: 1000ms内存限制: 65536kB描述 ? 热带岛屿Lagrishan的首领现在面临一个问题:几年前,一批外援资金被用于维护村落之间的道路,但...

    attack
  • P1401 城市(30分,正解网络流)

    题目描述 N( )个城市,M( )条无向边,你要找T( )条从城市1到城市N的路,使得最长的边的长度最小,边不能重复用。 输入输出格式 输入格式: 第1行...

    attack
  • P1726 上白泽慧音(0分)

    题目描述 在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够...

    attack
  • 盘点今年秋招那些“送命”的算法面试题

    随着 2019 年校招结束,“金九银十”的跳槽季也已经接近尾声,不知道在裁员、消减HC、只招中高级岗位等等“悲观”情绪下,你是否已经如愿入职心意的企业?或者还是...

    五分钟学算法
  • 03:丛林中的路

    总时间限制: 1000ms内存限制: 65536kB描述 ? 热带岛屿Lagrishan的首领现在面临一个问题:几年前,一批外援资金被用于维护村落之间的道路,但...

    attack
  • 186. [USACO Oct08] 牧场旅行

    157. [USACO Nov07] 奶牛跨栏 186. [USACO Oct08] 牧场旅行 ★★   输入文件:pwalk.in   输出文件:pwalk....

    attack
  • 1807. [NOIP2014]寻找道路P2296 寻找道路

    题目描述 在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1 .路径上的所有点的出边所指向的点...

    attack
  • 最短网络Agri-Net

    问题描述】   农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。约翰已经给他的农场安排了一条高速...

    attack

扫码关注云+社区

领取腾讯云代金券