题解 T28305 【yizimi的旅游景点】

2023-07-24 01:00:29

题目链接这里！！！

AC军团月赛题目地址这里！！！正比例函数的旅游景点

题目翻译

我依然不会告诉你题目的难度有一半是读题

其实就是给定一个图中一部分点，给定一部分边，先让你求这之中的最小生成树，然后再这个树的基础上求关于所有点和所有边的最大生成树。

好用的最小生成树模板

看到这里我觉得大部分dalao就可以喊着“这出题人语文真差而且这道题真水”去写代码秒题了

如果您还往下看，只有两种可能：

1.yizimi的语文太菜了，题目翻译还是看不懂2.不会写代码诶

好，基本上就没别的弯路，上代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 20020
#define mm 200010
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read()
{int f = 1, x = 0;char ch = getchar();while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void write(int x)
{if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 + '0');
}
//This is AC head above...
int n, m;
int ans, tot, cnt;
bool b[mn];
struct edge
{int u, v, w, p;bool used;
} e[mm];
inline bool cmp1(edge a, edge b)
{return a.w < b.w;
}
inline bool cmp2(edge a, edge b)
{return a.w > b.w;
}
int father[mn];
inline int findx(int x)
{return father[x] == x ? x : father[x] = findx(father[x]);
}
inline void mergex(int x, int y)//随机合并大法好
{int xx = findx(x);int yy = findx(y);if (xx == yy)return;srand((unsigned)time(NULL));//随机合并if (rand() % 2){father[xx] = yy;}else{father[yy] = xx;}
}
inline void Krus()//最小生成树
{go(i, 1, n, 1)father[i] = i;sort(e + 1, e + m + 1, cmp1);go(i, 1, m, 1){if (b[e[i].u] && b[e[i].v] && findx(e[i].u) != findx(e[i].v) && e[i].p == 1 && !e[i].used){ans += e[i].w;mergex(e[i].u, e[i].v);e[i].used = true;cnt++;}if (cnt == tot - 1)return;}
}
inline void Krub()//最大生成树
{sort(e + 1, e + m + 1, cmp2);go(i, 1, m, 1){if (findx(e[i].u) != findx(e[i].v) && !e[i].used){ans += e[i].w;mergex(e[i].u, e[i].v);e[i].used = true;cnt++;}if (cnt == n - 1)return;}
}
int main()
{//freopen("002.in", "r", stdin);//freopen("002.out", "w", stdout);n = read(), m = read();go(i, 1, n, 1){b[i] = read();//cin >> b[i];//scanf("%d", &b[i]);if (b[i])tot++;}go(i, 1, m, 1){e[i].u = read(), e[i].v = read(), e[i].w = read(), e[i].p = read(), e[i].w *= e[i].p, e[i].used = false;//cin >> e[i].u >> e[i].v >> e[i].w >> e[i].p;//scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].w, &e[i].p);//e[i].w *= e[i].p, e[i].used = false;}//这里你可以试试cin，保证慢死Krus();if (cnt != tot - 1){cout << -1;return 0;}int ans1 = ans;Krub();if (cnt != n - 1){cout << -1;return 0;}cout << ans1 << " " << ans - ans1;return 0;
}

有些大佬看到这里可能会说：

明明我写对了，为什么会T？

我只是想说：

dalao您先看看时限！

这个题是300ms，如果你用cin大约是600ms（部分点），不开O2都有可能T掉。

这就是这个题的最大的坑

读入优化大法好

转载于:https://www.cnblogs.com/yizimi/p/10056230.html


本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

相关文章

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统 微软输入法 于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销 是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题 跑道 汽车 绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

立即
投稿

微信公众账号

微信扫一扫加关注

 返回
顶部