[C++知识库]招募军队 （超级源点）

超级源点+最大/最小生成树

招募军队

#include<bits/stdc++.h> 
using namespace std;
#define ff first
#define ss second
#define lowbit(x) (x&-x)
#define pf(a) printf("%d\n",a)
#define mem(x,y) memset(x,y,sizeof(x))
#define dbg(x) cout << #x << " = " << x << endl
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define fep(i,a,b) for(int i=b; i>=a; --i)
#define PII pair<int,int>
//#define long long in 
typedef long long ll;

const int N = 2e5+10;
struct rec{int x, y, z;} edge[N];
int fa[N],n,m;


bool cmp1(rec a, rec b){
	return a.z < b.z;
}

bool cmp2(rec a, rec b){
	return a.z > b.z;
}

int get(int x)
{
	if(x==fa[x]) return x;
	return fa[x] = get(fa[x]);
}

void solve()
{
	scanf("%d %d",&n,&m);
	int p = 0;
	ll sum = 0, mi = 0, ma = 0;
	rep(i,1,n) {
		int u;
		scanf("%d",&u);
		edge[p].x = 0;
		edge[p].y = i;
		edge[p].z = u;
		p++;
		sum += u;
	}
	rep(i,1,m) {
		scanf("%d %d %d",&edge[p].x, &edge[p].y, &edge[p].z);
		p++;
	}
	sort(edge,edge+p,cmp1);
	rep(i,0,n) fa[i] = i;
	rep(i,0,p-1){
		int x = get(edge[i].x);
		int y = get(edge[i].y);
		if(x==y) continue;
		fa[x] = y;
		mi += edge[i].z;
	}
	sort(edge,edge+p,cmp2);
	rep(i,0,n) fa[i] = i;
	rep(i,0,p-1){
		int x = get(edge[i].x);
		int y = get(edge[i].y);
		if(x==y) continue;
		fa[x] = y;
		ma += edge[i].z;
	}
	cout << max(abs(mi-sum), abs(ma-sum));
}

int main(){
		solve();
	return 0;
}