修改

NC213862. 修改

描述

scimoon 有一个长度为 n 的数列

一个不幸的事实是，这个数列里的数非常地混乱，scimoon 想让它变得工整

scimoon 现在有 m 种操作，第 i 种操作可以把 $[l_i,r_i]$ 之间的数全部加一或减一，但是，要使用它就必须先支付 $w_i$ 的费用，然后就可以无限制次数地使用这种操作

scimoon 想要知道，对于任意长度为 n 的数列，是否存在一种选择操作的方式，可以通过使用这些操作，使得所有数列中的数都等于 0

scimoon 并不富有，因此如果有解，他还想要知道最少支付多少费用

输入描述

第一行两个整数 n,m，表示数列长度和操作个数

接下来 m 行，每行三个整数 ，意义见题目描述

输出描述

如果不存在一种选择操作的方式，输出 -1 

否则输出最少支付的费用

示例1

输入:

输出:

示例2

输入:

输出:

-1

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 183ms, 内存消耗: 3564K, 提交时间: 2020-11-18 16:49:21

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;

struct edge
{
	int u,v;
	ll w;
}e[N<<1];
int n,m,cnt,fa[N];
ll ans;

bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

int main()
{
	cin>>n>>m; ++n;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int rx=find(e[i].u),ry=find(e[i].v+1);
		if(rx!=ry) ans+=e[i].w,fa[rx]=ry,++cnt;
	}
	cout<<(cnt==n-1?ans:-1)<<endl;
}