瓜农王大爷去年种西瓜赚了不少钱。看到收入不错，今年他又重新开辟了n个西瓜地。
为了能给他的n个西瓜地顺利的浇上水，对于每个西瓜地他可以选择在本地打井，也可以修管道从另一个瓜地（这个瓜地可能打了井；也可能没打井，他的水也是从其他瓜地引来的）将水引过来。
当然打井和修管道的费用有差别。已知在第i个西瓜地打井需要耗费wi元，在第i、j个西瓜地之间修管道需要耗费pi,j元。
现在的问题是：王大爷要想使所有瓜地都被浇上水，至少需要花费多少钱（打井与修管道的费用和）？
由于瓜地较多，王大爷无法选择在哪些（个）瓜地打井，哪些西瓜地之间修管道。
请你编程帮王大爷做出决策，求出最小费用。

其实多个生成块而言考虑一个超级源点将其依次连接即可，这种思路在图中很常见。

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
#define pi 3.1415927
#define double long double
#define x first
#define y second
const int N = 2e5 + 10;
double eps=  1e-8;

ll f[N + 5];
int p[N];
/*
  每次找到离u较近的点进行更新

*/
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<array<int,3>> t;
    for(int i = 1; i <= n * 2; i ++) p[i] = i;
    for(int i = 1; i <= n; i ++){
        int x;
        cin >> x;
        int u = i,v = i + n;
        t.push_back({x,0,i});
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            int x;
            cin >> x;
            t.push_back({x,i,j});
        }
    }
    sort(t.begin(),t.end());
    int m = t.size();
    ll res = 0,cnt = 0;
    for(int i = 0; i < m; i ++){
        int a = t[i][1],b = t[i][2],c = t[i][0];
        a = find(a),b = find(b);
        //cout << i <<  " " << a << " " << b << endl;
        if(a != b) res += c,p[a] = b;
    }
    cout << res << endl;
}

题目1：杭电实验室会定期去电影院看电影，按照惯例，每个成员需要先抽一个号码。
给出n个人的名字，各抽取一个数字， 自己用一种数据结构存取人的名字和抽取数字信息(票数)
例如：BOB 9 Alice 12 Tom 5 jack 7 Nick 4…
1.定义一种数叫丑数，其因子除1外只有2.3.5的倍数，(例如4,10,是丑数，11，13不是)，输出所有抽到丑数的人的名字
2. 根据个人所抽数字大小升序排序， 输出排序后的所有名字
3.现有一个新名字加入，将名字插入所有名字中间(n/2)处，并排序输出所有名字

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
#define pi 3.1415927
#define double long double
#define x first
#define y second
const int N = 2e5 + 10;
double eps=  1e-8;

ll f[N + 5];
int p[N];
/*
  每次找到离u较近的点进行更新

*/
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<pair<int,string>> a(n + 1);
    auto check = [&](int x){
        while(x % 2 == 0) x /= 2;
        while(x % 5 == 0) x /= 5;
        while(x % 3 == 0) x /= 3;
        if(x != 1) return 0;
        return 1;
    };
    for(int i = 1; i <= n; i ++) cin >> a[i].y >> a[i].x;
    for(int i = 1; i <= n; i ++){
        if(check(a[i].x)) cout << a[i].y << " ";
    }
    cout << endl;
}

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
#define pi 3.1415927
#define double long double
#define x first
#define y second
const int N = 2e5 + 10;
double eps=  1e-8;

ll f[N + 5];
int p[N];
/*
  每次找到离u较近的点进行更新

*/
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<pair<int,string>> a(n + 1);
    auto check = [&](int x){
        while(x % 2 == 0) x /= 2;
        while(x % 5 == 0) x /= 5;
        while(x % 3 == 0) x /= 3;
        if(x != 1) return 0;
        return 1;
    };
    for(int i = 1; i <= n; i ++) cin >> a[i].y >> a[i].x;
    sort(a.begin() + 1,a.end());
    for(int i = 1; i <= n; i ++) cout << a[i].y << " \n"[i == n];
    cout << endl;
}