【集训Day1】Spy dispatch

Spy dispatch

---

解题思路

用最小的代价将所有节点联系在一起，用最小生成树。
为了处理参加任务的花费，我们将每个节点与 “根节点” 相连，边权为 $M_k$。

code

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int n,ans,s;
int v[1010];
int minn[1010];
int a[1010][1010];

int main()
{
    
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
    
		int t;
		scanf("%d",&t);
		minn[i]=t;
		a[i][n+1]=a[n+1][i]=t;
	}
	v[++n]=1;
	for(int i=1;i<n;i++)
	{
    
		int t,mi=0x3f3f3f3f;
		for(int j=1;j<=n;j++)
			if(!v[j]&&mi>minn[j])
				t=j,mi=minn[j];
		v[t]=1;
		ans+=mi;
		for(int j=1;j<=n;j++)
			minn[j]=min(minn[j],a[t][j]);
	}
	cout<<ans<<endl;
}