nyoj 1239 引水project （河南省第八届acm程序设计大赛）

墨蓝 2022-03-30 14:08 145阅读 0赞

*  题目1239
 *  [题目信息][Link 1]
 *  [执行结果][Link 2]
 *  [本题排行][Link 3]
 *  [讨论区][Link 4]

## 引水project ##

时间限制：2000 ms | 内存限制：65535 KB

难度：3

描写叙述

南水北调project是优化水资源配置、促进区域协调发展的基础性project。是新中国成立以来投资额最大、涉及面最广的战略性project，事关中华民族长远发展。“[南水北调project][project]”。旨在缓解中国[华北][Link 5]和[西北][Link 6]地区水资源短缺的国家战略性project。就是把中国长江流域丰盈的水资源抽调一部分送到华北和西北地区。

我国南涝北旱，南水北调project通过跨流域的[水资源][Link 7]合理配置。促进南北方经济、社会与人口、资源、环境的协调发展。

整个project分东线、中线、西线三条调水线。东线project位于东部，因地势低需抽水北送至[华北地区][Link 8]。中线project从[汉水][Link 9]与其最大支流[丹江][Link 10]交汇处的[丹江口水库][Link 11]引水，自流供水给[黄淮海平原][Link 12]大部分地区，20多座大中城市；西线project在[青藏高原][Link 13]上，由[长江][Link 14]上游向黄河上游补水。

如今有N个区域须要建设水资源project，它们能够自建水库解决缺水问题，也能够从已有水源的地区建立管道引水过来。

当然。这些建设都须要大量投资。

你能不能给出一个优化水资源配置方案，在保证每一个区域都能用上水的前提下。使得整个引水project费用最低。

输入

第一行： K 表示有多少组測试数据。

接下来对每组測试数据：  
第1行: N 表示有N个区域（ 1<=N<=300 ）  
第2 行： W1 W2 …. WN Wi表示第i个区域自建水库须要的费用  
再有N行： Pi1 Pi2 …. Pin Pij表示建立第i个区域与第j个区域引水管道的费用

输出

对于每组測试数据，输出占一行，即建立整个引水project的最小费用。

例子输入

155 4 4 3 60 2 2 2 22 0 3 3 32 3 0 4 52 3 4 0 12 3 5 1 0

例子输出

来源

[第八届河南省程序设计大赛][Link 15]

去年刚刚大一 对于什么图论算法都不懂 也不懂得变通 看到这道题 就直接放弃了。今天再做 清晰明了 明年再来。

仅仅要把问题转换一下 就是最小生成树

最好用prim算法 反正我是用kruskal算法没算出来。

。

我的大概思路 就是 首先找到一个自建水库最少费用的 然后以此为根本 找到与之相关的边

比較权值和它本身自建水库所需费用

#include <stdio.h>
    #include <string.h>
    #define INF 0x3fffffff
    int map[350][350];
    bool vis[350];
    int n;
    void dijkstra()
    {
    	int minn=INF;
    	int pos=-1;
    	int res=0;
    	for(int i=1;i<=n;i++)
    	{
    		if(minn>map[i][i])
    		{
    			minn=map[i][i];
    			pos=i;
    		}
    	}
    	int stamp[350];
    	int cnt=0;
    	stamp[cnt++]=pos;
    	vis[pos]=true;
    	res=minn;
    	while(cnt<n)
    	{
    		minn=INF;
    		for(int i=0;i<cnt;i++)
    		{
    			int x=stamp[i];
    			for(int j=1;j<=n;j++)
    			{
    				if(!vis[j])
    				{
    					if(minn>map[x][j])
    					{
    						minn=map[x][j];
    						pos=j;
    					}
    					if(minn>map[j][j])
    					{
    						minn=map[j][j];
    						pos=j;
    					}
    				}
    			}
    		}
    		stamp[cnt++]=pos;
    		vis[pos]=true;
    		res+=minn;
    	}
    	printf("%d\n",res);
    }
    int main()
    {
    	int k;
    	scanf("%d",&k);
    	while(k--)
    	{
    		memset(vis,false,sizeof(vis));
    		memset(map,100,sizeof(map));
    		scanf("%d",&n);
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d",&map[i][i]);
    		} 
    		int skip;
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=1;j<=n;j++)
    			{
    				if(i==j) scanf("%d",&skip);
    				else scanf("%d",&map[i][j]);
    			}
    		}
    		dijkstra();
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/problem.php?
[Link 2]: http://acm.nyist.net/JudgeOnline/status.php?
[Link 3]: http://acm.nyist.net/JudgeOnline/problemrank.php?
[Link 4]: http://acm.nyist.net/JudgeOnline/talking.php?pid=1239
[project]: http://baike.baidu.com/view/51108.htm
[Link 5]: http://baike.baidu.com/subview/144248/5062655.htm
[Link 6]: http://baike.baidu.com/subview/393189/11037469.htm
[Link 7]: http://baike.baidu.com/view/16491.htm
[Link 8]: http://baike.baidu.com/view/417518.htm
[Link 9]: http://baike.baidu.com/view/18683.htm
[Link 10]: http://baike.baidu.com/subview/74729/11988878.htm
[Link 11]: http://baike.baidu.com/view/188128.htm
[Link 12]: http://baike.baidu.com/view/416642.htm
[Link 13]: http://baike.baidu.com/subview/4979/5043819.htm
[Link 14]: http://baike.baidu.com/subview/4185/4998436.htm
[Link 15]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%AC%AC%E5%85%AB%E5%B1%8A%E6%B2%B3%E5%8D%97%E7%9C%81%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E5%A4%A7%E8%B5%9B