185. [USACO Oct08] 挖水井
2018-06-17 22:47:39来源:未知 阅读 ()
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C/C++常考面试题(二)
- 题解 P5116 【[USACO18DEC]Mixing Milk】 2020-03-14
- 【做题笔记】P2871 [USACO07DEC]手链Charm Bracelet 2020-02-14
- LuoguP3069 【[USACO13JAN]牛的阵容Cow Lineup 2019-10-30
- P2995 [USACO10NOV]牛的照片(树状数组,逆序对) 2019-10-25
- 洛谷 P3144 [USACO16OPEN]关闭农场Closing the Farm_Silver 2019-09-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash