題目描述：點擊進入
思路
最小生成樹變形
新建虛擬 “零” 節點，這個節點跟每個農田 i 連邊，權值分別為在農田 i 建造水庫的花費，然后其他的邊正常連，最后求最小生成樹即可，
代碼
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int N=1e7+10;
int pre[310],n,p[310][310],w,cnt;
struct node
{
int x;
int y;
ll k;
}s[maxn];
int find(int x)
{
if(x==pre[x]) return x;
else return pre[x]=find(pre[x]);
}
bool unions(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
pre[fy]=fx;
return 0;
}
else return 1;
}
bool cmp(node a,node b)
{
return a.k<b.k;
}
int main()
{
//ios::sync_with_stdio(false);
scanf("%d",&n);
for(int i=0;i<=n;i++) pre[i]=i;
for(int i=1;i<=n;i++)
{
scanf("%d",&w);
s[++cnt].x=0;
s[cnt].y=i;
s[cnt].k=w;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&p[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
s[++cnt].x=i;
s[cnt].y=j;
s[cnt].k=p[i][j];
}
}
sort(s+1,s+cnt+1,cmp);
ll ans=0;
for(int i=1;i<=cnt;i++)
{
if(!unions(s[i].x,s[i].y))
ans+=s[i].k;
}
printf("%lld\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/210042.html
標籤：java