题意：王国里有n个城市通过m条双向边相连，每个城市可以花费bi去造一个士兵守护，然后每个城市需要ai个士兵守护。每条道路如果要守护，就必须要ci个士兵，这ci个士兵可以同时守护道路两端的城市。如果城市或者道路被守住了，那就可以免费运送士兵。问守住所有城市的最小花费。
思路：首先守边和守点求最小花费，最先想到的是树形DP的板题，只不过这是在一张图上，所以思路是一个DP。要考虑运兵的因素，，所以我们dp维护一个集合，表示守护这个集合的最小花费。集合之间的合并通过Kruskal。
#include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <string> #include <map> using namespace std; struct edge { int u,v; long long num; }; edge ed[300010]; int n,m; long long ai[300010],bi[300010],sum[300010]; int fa[300010]; void init() { for(int i=1;i<=n;i++) fa[i]=i; } bool cmp(const edge &a,const edge &b) { return a.num<b.num; } int findfa(int x) { if(fa[x]!=x) fa[x]=findfa(fa[x]); return fa[x]; } int main() { int i; scanf("%d%d",&n,&m); init(); for(i=1;i<=n;i++) { scanf("%lld%lld",&ai[i],&bi[i]); sum[i]=ai[i]*bi[i]; } for(i=1;i<=m;i++) { scanf("%d%d%lld",&ed[i].u,&ed[i].v,&ed[i].num); } sort(ed+1,ed+1+m,cmp); for(i=1;i<=m;i++) { int u=findfa(ed[i].u),v=findfa(ed[i].v); if(u==v) continue; long long num=max(ai[u],max(ai[v],ed[i].num)); long long cnt=min(bi[v],bi[u]); sum[u]=min(sum[v]+sum[u],cnt*num); fa[v]=u; ai[u]=num; bi[u]=cnt; } long long ans=0; for(i=1;i<=n;i++) { if(fa[i]==i) ans+=sum[i]; } printf("%lld\n",ans); return 0; }