描述
南水北调工程是优化水资源配置、促进区域协调发展的基础性工程，是新中国成立以来投资额最大、涉及面最广的战略性工程，事关中华民族长远发展。“南水北调工程”，旨在缓解中国华北和西北地区水资源短缺的国家战略性工程。就是把中国长江流域丰盈的水资源抽调一部分送到华北和西北地区。我国南涝北旱，南水北调工程通过跨流域的水资源合理配置，促进南北方经济、社会与人口、资源、环境的协调发展。
整个工程分东线、中线、西线三条调水线。东线工程位于东部，因地势低需抽水北送至华北地区。中线工程从汉水与其最大支流丹江交汇处的丹江口水库引水，自流供水给黄淮海平原大部分地区，20多座大中城市；西线工程在青藏高原上，由长江上游向黄河上游补水。
现在有N个区域需要建设水资源工程，它们可以自建水库解决缺水问题，也可以从已有水源的地区建立管道引水过来。当然，这些建设都需要大量投资。
你能不能给出一个优化水资源配置方案，在保证每个区域都能用上水的前提下，使得整个引水工程费用最低。
- 输入
- 第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: N 表示有N个区域（ 1<=N<=300 ）
第2 行： W1 W2 …. WN Wi表示第i个区域自建水库需要的费用
再有N行： Pi1 Pi2 …. Pin Pij表示建立第i个区域与第j个区域引水管道的费用 - 输出
- 对于每组测试数据，输出占一行，即建立整个引水工程的最小费用。
- 样例输入
-
1
5
5 4 4 3 6
0 2 2 2 2
2 0 3 3 3
2 3 0 4 5
2 3 4 0 1
2 3 5 1 0 - 样例输出
-
10
- 来源
- 第八届河南省程序设计大赛
- 上传者
- hnu_acm
题解: 找到建立水库的最小值,以此建立最小生成树.......蒟蒻啊 ....自己刚开始的思路想错了.....
WA代码:
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 100010 int n,ans,minn;
int quyu[],vis[],dis[];
int mp[][]; void prim()
{
memset(vis,,sizeof(vis));
memset(dis,INF,sizeof(dis));
dis[]=;
ans=;
dis[]=INF;
while(true){
int m=;
for(int i=; i<=n; i++){
if(!vis[i] && dis[i]<dis[m])
m=i;
}
if(m==)
break;
vis[m]=;
ans+=dis[m];
for(int i=; i<=n; i++)
dis[i]=min(dis[i],mp[m][i]);
}
} void init()
{
memset(mp,INF,sizeof(mp));
memset(quyu,,sizeof(quyu));
minn=INF;
} int main()
{
int t;
scanf("%d",&t);
while(t--){
init();
scanf("%d",&n);
for(int i=; i<n; i++){
scanf("%d",&quyu[i]);
if(minn>quyu[i])
minn=quyu[i];
}
for(int i=; i<=n; i++)
for(int j=; j<=n; j++){
scanf("%d",&mp[i][j]);
}
prim();
printf("%d\n",ans+minn);
}
}
AC代码:
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 100010 int n,ans,minn;
int quyu[],vis[],dis[];
int mp[][]; void prim()
{
memset(vis,,sizeof(vis));
memset(dis,INF,sizeof(dis));
for(int i=;i<=n;i++)
dis[i]=mp[][i];
ans=;
//dis[0]=INF;
while(true){
int m=;
for(int i=; i<=n; i++){
if(!vis[i] && dis[i]<dis[m])
m=i;
}
if(m==)
break;
vis[m]=;
ans+=dis[m];
for(int i=; i<=n; i++)
dis[i]=min(dis[i],mp[m][i]);
}
} void init()
{
memset(mp,INF,sizeof(mp));
memset(quyu,,sizeof(quyu));
minn=INF;
} int main()
{
int t;
scanf("%d",&t);
while(t--){
init();
scanf("%d",&n);
for(int i=; i<=n; i++){
scanf("%d",&mp[][i]);
}
for(int i=; i<=n; i++)
for(int j=; j<=n; j++){
scanf("%d",&mp[i][j]);
}
prim();
printf("%d\n",ans);
}
}
别人的克鲁斯卡尔A的:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxsize 310
#define INF 0x3f3f3f3f
int n;
int p[Maxsize][Maxsize];
int par[Maxsize];
int rank[Maxsize];
void init()
{
memset(p,0x3f,sizeof(p));
for(int i=;i<=n;i++)
{
par[i]=i;
rank[i]=;
}
}
int find(int x)
{
if(par[x]==x)
return x;
else return par[x]=find(par[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(rank[x]<rank[y])
par[x]=y;
else
{
par[y]=x;
if(rank[x]==rank[y])
rank[x]++;
}
}
bool same(int x,int y)
{
return find(x)==find(y);
}
int FindTree()
{
int res=;
int a,b;
for(;;)
{
int min=INF;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
if(min>p[i][j]&&(!same(i,j)))
{
min=p[i][j];
a=i;b=j;
}
}
if(min==INF)
break;
// printf("%d\n",min);
res+=p[a][b];
unite(a,b);
}
return res;
}
int main()
{
int K;
int i,j;
scanf("%d",&K);
while(K--)
{
scanf("%d",&n);
init();
for(i=;i<=n;i++)
{
scanf("%d",&p[][i]);
p[i][]=p[][i];
}
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%d",&p[i][j]);
printf("%d\n",FindTree());
}
return ;
}