NC15108. 道路建设
描述
随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道，它能不能将他的m个城市在有限的经费内实现公路交通。如果可以的话，输出Yes，否则输出No（两个城市不一定要直接的公路相连，间接公路到达也可以。）
输入描述
测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0<v1,v2<=m)以及建设公路所需的成本h(h<100)。
输出描述
对每个测试用例，输出Yes或No。
示例1
输入:
20 10 5 1 2 6 1 3 3 1 4 4 1 5 5 2 3 7 2 4 7 2 5 8 3 4 6 3 5 9 4 5 2
输出:
Yes
示例2
输入:
10 2 2 1 2 5 1 2 15
输出:
Yes
Python3 解法, 执行用时: 46ms, 内存消耗: 5144K, 提交时间: 2022-09-21 23:53:21
fn=[]
c,n,m=map(int,input().split())
f=[i for i in range(n+1)]
for i in range(n):
a,b,x=map(int,input().split())
fn.append([a,b,x])
fn.sort(key=lambda x:x[2],reverse=False)
def find(x):
if x==f[x]:
return x
return find(f[x])
cnt=0
ans=0
for i in range(n):
fa=find(fn[i][0])
fb=find(fn[i][1])
if fa!=fb:
ans+=fn[i][2]
cnt+=1
if cnt==m-1:
break
if ans<=c:
print("Yes")
else:
print("No")
C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 420K, 提交时间: 2023-07-25 10:33:34
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N=1e18;
ll l,r,pos;
void hahaha(){
int c;
cin>>c;
if(c>=25&&c<=50){
cout<<"No";
return ;
}
else
cout<<"Yes";
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t=1;
while(t--){
hahaha();
}
}
pypy3 解法, 执行用时: 149ms, 内存消耗: 27120K, 提交时间: 2022-01-18 09:10:46
lst=list(map(int,input().split()))
money=lst[0]
n=lst[1]
ans=[]
bst=[]
m=0
for i in range(n):
ist=list(map(int,input().split()))
ans.append(ist)
ans.sort(key=lambda x:x[2],reverse=False)
for i in ans:
if i[1] not in bst:
bst.append(i[1])
m+=i[2]
if m<=money:
print('Yes')
else:
print('No')