e509 - Conscription
題目描述
題目描述了 Windy 需要招募 N 個女孩和 M 個男孩，每個士兵的招募成本為 10000。女孩和男孩之間存在關係，如果他們之間存在關係 d，則招募其中一人時，另一人的成本可以降低到 10000 - d。目標是找到招募所有士兵的最小成本。
解題思路
這道題可以建模為一個最小生成樹問題。將 N 個女孩和 M 個男孩看作圖的節點，女孩的節點編號為 0 到 N-1，男孩的節點編號為 N 到 N+M-1。每條關係 (x, y, d) 都可以看作一條邊，連接女孩 x 和男孩 y，權重為 10000 - d。然後使用 Kruskal 算法找到最小生成樹，最小生成樹的權重和就是招募所有士兵的最小成本。
程式碼中，fa 陣列用於實現 Disjoint Set Union (並查集)，用於判斷兩個節點是否在同一個連通分量中。cmp 函數用於對邊進行排序，按照權重降序排列。f 函數用於查找節點的根節點。merge 函數用於合併兩個連通分量。主函數中，首先讀取輸入數據，然後對邊進行排序，然後使用 Kruskal 算法找到最小生成樹，並計算最小成本。
複雜度分析
- 時間複雜度: O(E log E)，其中 E 是邊的數量 (w)。排序邊需要 O(E log E) 的時間，Kruskal 算法需要 O(E α(V)) 的時間，其中 α(V) 是反阿克曼函數，增長非常慢，可以看作常數。因此，總時間複雜度為 O(E log E)。
- 空間複雜度: O(V + E)，其中 V 是節點的數量 (N + M)，E 是邊的數量 (w)。
fa陣列需要 O(V) 的空間，p陣列需要 O(E) 的空間。因此，總空間複雜度為 O(V + E)。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long fa[20005],n,m,w,t,ans;
struct edge{
long long x,y,v;
};
edge p[50005];//v,x,y
long long f(long long x){
if(fa[x]==x)return x;
return f(fa[x]);
}
void merge(long long a,long long b){
a=f(a);
b=f(b);
fa[b]=a;
}
bool cmp(edge a,edge b){
if(a.v > b.v)return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n >> m >> w;
ans=(n+m)*10000;
for(int i=0;i<=n+m;++i){
fa[i]=i;
}
for(int i=0;i<w;++i){
cin >> p[i].x >> p[i].y >> p[i].v;
p[i].y+=n;
p[i].v = 10000 - p[i].v;
}
sort(p,p+w,cmp);
for(int i=0;i<w;++i){
if(f(p[i].x)!=f(p[i].y)){
merge(p[i].x,p[i].y);
ans-=p[i].v;
}
}
cout << ans << "\n";
}
}