ural 1160

2024-06-10 17:32
文章标签 ural 1160

本文主要是介绍ural 1160,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最小生成树  第一次敲 套用几个函数 其实挺容易的

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{int u,v,w;void f(int a, int b, int c){u = a;v = b;w = c;}bool operator < (const node & e) const{return w < e.w;}
};
vector<node>q,qq;
int p[2000],r[2000];int findd(int x)
{return p[x] == x ? x : p[x] = findd(p[x]);
}
int main()
{int n,m;node cc;scanf("%d%d",&n,&m);for(int i = 0; i < m; i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);cc.f(a,b,c);q.push_back(cc);}sort(q.begin(), q.end());int ans = 0;for(int i = 0; i <= n; i++)p[i] = i;for(int i = 0; i < m; i++){int x = findd(q[i].u), y = findd(q[i].v);if(x != y){ans = q[i].w;qq.push_back(q[i]);p[x] = y;}}printf("%d\n",ans);int len = qq.size();printf("%d\n",len);for(int i = 0; i < len; i ++)printf("%d %d\n",qq[i].u,qq[i].v);return 0;
}


这篇关于ural 1160的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1048806

相关文章

ural 1297. Palindrome dp

1297. Palindrome Time limit: 1.0 second Memory limit: 64 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unli

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

ural 1820. Ural Steaks 贪心

1820. Ural Steaks Time limit: 0.5 second Memory limit: 64 MB After the personal contest, happy but hungry programmers dropped into the restaurant “Ural Steaks” and ordered  n specialty steaks

ural 1017. Staircases DP

1017. Staircases Time limit: 1.0 second Memory limit: 64 MB One curious child has a set of  N little bricks (5 ≤  N ≤ 500). From these bricks he builds different staircases. Staircase consist

ural 1026. Questions and Answers 查询

1026. Questions and Answers Time limit: 2.0 second Memory limit: 64 MB Background The database of the Pentagon contains a top-secret information. We don’t know what the information is — you

ural 1014. Product of Digits贪心

1014. Product of Digits Time limit: 1.0 second Memory limit: 64 MB Your task is to find the minimal positive integer number  Q so that the product of digits of  Q is exactly equal to  N. Inpu

后缀数组 - 求最长回文子串 + 模板题 --- ural 1297

1297. Palindrome Time Limit: 1.0 second Memory Limit: 16 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unlim

【URAL】1057 Amount of Degrees 数位DP

传送门:【URAL】1057 Amount of Degrees 题目分析:将数转化成能达到的最大的01串,串上从右往左第i位为1表示该数包括B^i。 代码如下: #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;typedef long long LL ;#de

hdu 1160 FatMouse's Speed(最长上升子序列 +记录路径)

http://acm.hdu.edu.cn/showproblem.php?pid=1160 题意:有若干只老鼠,给出每只老鼠的大小和速度。输出尽量多的老鼠的下标m1,m2,m3......满足下标对应的老鼠大小严格递增而老鼠速度严格递减。 思路:先对老鼠的速度从大到小排序,在对老鼠的大小求最长上升子序列。在这过程中,用pre[ ]记录路径。 #include <stdio.h>#in

ural Minimal Coverage (区间覆盖)

http://acm.timus.ru/problem.aspx?space=1&num=1303 给出一些区间,选择尽量少的区间能覆盖到[0,m]。 小白p154,典型的区间覆盖问题。一直在想怎么dp。。 首先预处理,先按左端点从小到大排序,若左端点相同右端点从大到小排序,若区间x完全包含y,按照贪心的思想,y是没有意义的,有大区间可以选何必选择小区间。处理完事之后各个区间满足a1