首页 > 其他分享 >POJ--3723 Conscription(最小生成树)

POJ--3723 Conscription(最小生成树)

时间:2023-01-29 19:14:46浏览次数:61  
标签:cost -- MAX int edge POJ Conscription find es

记录
18:30 2023-1-29

http://poj.org/problem?id=3723

reference:《挑战程序设计竞赛(第2版)》2.5.6 p109

Description

Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl x and boy y have a relationship d and one of them has been collected, Windy can collect the other one with 10000-d RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.

Input

The first line of input is the number of test case.
The first line of each test case contains three integers, N, M and R.
Then R lines followed, each contains three integers xi, yi and di.
There is a blank line before each test case.

1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ xi < N
0 ≤ yi < M
0 < di < 10000

Output

For each test case output the answer in a single line.

Sample Input

2

5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889

Sample Output

71071
54223

最小生成树问题。要想让花费的钱最少,也就是尽可能选择关系最大的边,这样转换成了一个最大生成树问题,将边上的值取成负号就变成了最小生成树问题。(怕什么真理无穷,进一寸有一寸的惊喜)

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX_V 100000
#define MAX_E 100000
#define MAX_R 100000

const int INF = 0x3f3f3f3f;
#define MAX_N 100000
int par[MAX_N];
int ran[MAX_N];

void init(int n) {
    for(int i = 0; i < n; i++) {
        par[i] = i;
        ran[i] = 0;
    }
}

int find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;

    if(ran[x] < ran[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if(ran[x] == ran[y]) ran[x]++;
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

struct edge {int u, v, cost;};

bool comp(const edge &e1, const edge &e2) {
    return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;

int kruskal() {
    sort(es, es + E, comp); // 按照edge.cost的顺序 从小到大
    init(V);
    int res = 0;
    for(int i = 0; i < E; i++) {
        edge e = es[i];
        if(!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int N, M, R;
int x[MAX_R], y[MAX_R], d[MAX_R];

void solve() {
    V = N + M;
    E = R;
    for(int i = 0; i < R; i++) {
        // es[i] = (edge){x[i], N + y[i], -d[i]};
        es[i].u = x[i];
        es[i].v = N + y[i];
        es[i].cost = -d[i];
    }
    printf("%d\n", 10000 * (N + M) + kruskal());
}

int main() {
    int T;
    scanf("%d", &T);
    for(int i = 0; i < T; i++) {
        scanf("%d %d %d", &N, &M, &R);
        for(int j = 0; j < R; j++) {
            scanf("%d %d %d", &x[j], &y[j], &d[j]);
        }
        solve();
    }
}

标签:cost,--,MAX,int,edge,POJ,Conscription,find,es
From: https://www.cnblogs.com/57one/p/17073610.html

相关文章

  • Vue+axios+Servlet上传并显示图片
    做了和重写summernote插入图片的回调函数并上传图片到服务器一样的事,但是servlet简介:summernote点击上传(或粘贴)图片,前端用axios以multipart/form-data的形式传到后端,servl......
  • Java数组
    Java数组数组是相同类型数据的有序集合每一个数据称作一个数组元素,每个数组元素可以通过一个下标来访问它们。数组的声明必须声明数组变量才能在程序中使用。dataTy......
  • openwrt_imagebuilder_修改缺省配置_network_firewall_root密码
    openwrt_imagebuilder_修改缺省配置_network_firewall_root密码转载注明来源:本文链接来自osnosn的博客,写于2023-01-29.参考和方法【官方文档:使用ImageBuilder】......
  • Java反射之Field用法
    参考:https://www.cnblogs.com/ldq2016/p/6834643.htmlhttps://www.cnblogs.com/cuglkb/p/8463039.html工具类:publicclassObjectUtils{staticpublicfinalBo......
  • 2023/1/19 考试总结
    时间规划8:30~8:42题看起来都比较抽象,T2送了60分的康托展开,直接就写了。8:45~9:02T1的答案是2,且一定有上升和下降,手玩了一下发现解唯一,因此直接\(O(n^3)\)就有40分。9......
  • 「解题报告」ARC136F Flip Cells
    感觉AtCoder上高于铜的难度就完全是随机了,这题完全是金吧,怎么可能只有铜啊,我快写自闭了。以下记\(n=hw\)。我们设三个DP数组:\(f_i\)为从初始状态经过\(i\)步之......
  • OutputDebugString在X64出现异常 0xC0000005
    xxxxx.exe中的0x78ebb746处最可能的异常:0xC0000005:读取位置0xffffffffffffffff时发生访问冲突对应位置指令0000000078EBB7460FAE8100010000fxsave......
  • monaco编辑器的基础api使用
    目录添加js/ts扩展库添加js扩展库添加ts扩展库添加js/ts扩展库添加js扩展库1.使用addExtraLibfilePath同名会覆盖monaco.languages.typescript.javascriptDefaults.ad......
  • 未能找到类型或命名空间名“XXX”(是否缺少 using 指令或程序集引用?)
    编译以前一个Console控制台程序的时候提示"未能找到类型或命名空间名“XXX”(是否缺少using指令或程序集引用?)".VS智能感知是通过的,但是编译的时候死活不通过,提示找不......
  • Surface Pro (1796),安装Win11之后出现的问题。
    2020年年中我为了体验微软新的操作系统,加入了Review计划,即:Windows预览体验计划。然后升级到了Win11。由于苏菲一直是作为辅助设备用,所以平时就是开节电模式,中途也升级了几......