新的开始

前言

构建虚拟源点的方式来求解图论问题，比较常用，尤其是在负环问题和差分约束问题上更为普遍。

在最小生成树类的问题上同样有相似的应用。

solution

求解本题的关键在于办法1上，我们可以通过构建虚拟源点 0 来解决，对于每一个 $ii$ 点，构建一条以$00$为起点，$ii$ 为终点，边权为 $v_{i}v\_i$ 的边。经过这样的处理，我们就可以构建出一张图，然后在图上跑最小生成树求解答案即可。

code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#define Simon namespace
//#define int long long
#define ll long long
#define ls p << 1
#define rs p << 1 | 1
#define pii pair<int,int>
#define mk make_pair
#define eps 1e-10
#define orz cout<<"msr_AK_IOI"
using namespace std;
const int Mod=1e9+7;	const int maxn = 1e6 + 7 ;		const int MAXN = 2e5 + 50 ; 	const int INF = 2147483647 ;
namespace O_O
{
void Fre(){	freopen(".in", "r", stdin);	freopen(".out", "w", stdout);	}
inline int read(){	int x=0,f=1;	char ch=getchar();	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();	}	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
inline void wrt(long long  x){	if(x<0)	{	putchar('-');	x=-x;	}	if(x>9) wrt(x/10);	putchar(x%10+48);}
template <typename T> inline T Min(T x, T y) {return x < y ? x : y;}
template <typename T> inline T Max(T x, T y) {return x > y ? x : y;}
	}
using Simon O_O ;
struct node 
{
	int frm , to , dis ;
} ed[maxn << 1] ; 
bool operator <(node x , node y)
{
	return x.dis < y.dis ;
}
int n ,cnt ;
int fa[maxn] ; 
void add(int u , int v , int w)
{
	ed[++cnt] = { u , v , w} ;
}
int find(int x)
{
//	orz ;
	if(fa[x] == x)	return x ;
	return fa[x] = find(fa[x]) ;
}
int kru()
{
	int res = 0 , tot = 0 ; 	sort(ed + 1 , ed + 1 + cnt ) ;
	for(int i = 1 ; i <= cnt ; i++ )
	{
		int v = find(ed[i].to) , u = find(ed[i].frm) ;
		if(u == v)	continue ;
		res += ed[i].dis ;	fa[v] = u ;
		if(tot == n )	break ;
	}               
	return res ;	
}
signed main()
{
	cin >> n ; 
	for(int i = 1 ; i <= n ; i++ )
	{
		int x = read() ;
		fa[i] = i ; 
		add(0 , i , x) ; add(i , 0 , x) ;
	}
	for(int i = 1 ; i <= n ; i++ )
		for(int j = 1 ; j <= n ; j++ )
		{
			int x = read() ;
			if(i <= j)	continue ; 
			add(i , j , x) ;
		}
	cout << kru() ; 
	return 0 ;
}