【洛谷P7528】PortalsG【最小生成树】

$link$

很明显是$kruskal$ 然后考虑把所有环合并起来的最小代价 那就是加的边的总和
因为$kruskal$ 按边权排过序 这样选的一定是最优的

CODE&＃xff1a;

#include
#include
#include
#include
#include
using namespace std;
const int N&＃61;1e5&＃43;5;
int n,p[N][4],fa[N<<1],a[N],ans;
int find(int x){return x&＃61;&＃61;fa[x]?x:fa[x]&＃61;find(fa[x]);}
void Merge(int x,int y)
{int fx&＃61;find(x),fy&＃61;find(y);fa[fx]&＃61;fy;
}
vector<pair<int,int> > Vec;
int main(){scanf("%d",&n);for(int i&＃61;1;i<&＃61;(n<<1);i&＃43;&＃43;)fa[i]&＃61;i;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d%d%d%d%d",&a[i],&p[i][0],&p[i][1],&p[i][2],&p[i][3]);Merge(p[i][0],p[i][1]);Merge(p[i][2],p[i][3]);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)Vec.push_back(make_pair(a[i],i));sort(Vec.begin(),Vec.end());for(int i&＃61;0;i<n;i&＃43;&＃43;){int x&＃61;Vec[i].second;int fx&＃61;find(p[x][0]),fy&＃61;find(p[x][2]);if(fx^fy){fa[fx]&＃61;fy;ans&＃43;&＃61;Vec[i].first;}}printf("%d",ans);return 0;
}