1162. 【NOI2002】贪吃的九头龙 (Standard IO)

2024-01-30 07:18

本文主要是介绍1162. 【NOI2002】贪吃的九头龙 (Standard IO),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”,但这只是说它出生的时候有九个头,而在成长的过程中,它有时会长出很多的新头,头的总数会远大于九,当然也会有旧头因衰老而自己脱落。
有一天,有M个脑袋的九头龙看到一棵长有N个果子的果树,喜出望外,恨不得一口把它全部吃掉。可是必须照顾到每个头,因此它需要把N个果子分成M组,每组至少有一个果子,让每个头吃一组。
这M个脑袋中有一个最大,称为“大头”,是众头之首,它要吃掉恰好K个果子,而且K个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来,由于果树是一个整体,因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。
对于每段树枝,如果它所连接的两个果子需要由不同的头来吃掉,那么两个头会共同把树枝弄断而把果子分开;如果这两个果子是由同一个头来吃掉,那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然,吃树枝并不是很舒服的,因此每段树枝都有一个吃下去的“难受值”,而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。
九头龙希望它的“难受值”尽量小,你能帮它算算吗?
例如图1所示的例子中,果树包含8个果子,7段树枝,各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋,大头需要吃掉4个果子,其中必须包含最大的果子。即N=8,M=2,K=4:

Input

输入文件的第1行包含三个整数N (1<=N<=300),M (2<=M<=N),K (1<=K<=N)。 N个果子依次编号1,2,…,N,且最大的果子的编号总是1。第2行到第N行描述了果树的形态,每行包含三个整数a (1<=a<=N),b (1<=b<=N),c (0<=c<=10^5),表示存在一段难受值为c的树枝连接果子a和果子b。

Output

输出文件仅有一行,包含一个整数,表示在满足“大头”的要求的前提下,九头龙的难受值的最小值。如果无法满足要求,输出-1。

Sample Input

8 2 4
1 2 20
1 3 4
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5

Sample Output

4

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 305
typedef long long LL;
using namespace std;
struct near{int pu;//purposeint va;//valueint next;//next}p[2*N];int list[N];//last appearint f[N][N][2];int aa[N][2];int n,m,k;int tot;inline void dfs(int x,int y){memset(f[x],60,sizeof(f[x]));f[x][1][1]=f[x][0][0]=0;for(int i=list[x];i;i=p[i].next){if(p[i].pu==y)continue;int s=p[i].pu;dfs(s,x);memcpy(aa,f[x],sizeof(f[x]));memset(f[x],60,sizeof(f[x]));for(int j=0;j<=k;j++)for(int w=0;w<=j;w++){if(j!=w&&j)f[x][j][1]=min(f[x][j][1],min(f[s][w][1]+aa[j-w][1]+p[i].va,f[s][w][0]+aa[j-w][1]));if(m==2)f[x][j][0]=min(f[x][j][0],min(f[s][w][0]+aa[j-w][0]+p[i].va,f[s][w][1]+aa[j-w][0]));else f[x][j][0]=min(f[x][j][0],min(f[s][w][0]+aa[j-w][0],f[s][w][1]+aa[j-w][0]));}}return;}
int main(){scanf("%d%d%d",&n,&m,&k);if(n-k<m-1){printf("-1\n");return 0;}for(int i=1;i<n;i++){int x;int y;int z;scanf("%d%d%d",&x,&y,&z);p[++tot].pu=y;p[tot].va=z;p[tot].next=list[x];list[x]=tot;p[++tot].pu=x;p[tot].va=z;p[tot].next=list[y];list[y]=tot;} dfs(1,-1);printf("%d\n",f[1][k][1]);return 0;}

这篇关于1162. 【NOI2002】贪吃的九头龙 (Standard IO)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java IO 操作——个人理解

之前一直Java的IO操作一知半解。今天看到一个便文章觉得很有道理( 原文章),记录一下。 首先,理解Java的IO操作到底操作的什么内容,过程又是怎么样子。          数据来源的操作: 来源有文件,网络数据。使用File类和Sockets等。这里操作的是数据本身,1,0结构。    File file = new File("path");   字

springboot体会BIO(阻塞式IO)

使用springboot体会阻塞式IO 大致的思路为: 创建一个socket服务端,监听socket通道,并打印出socket通道中的内容。 创建两个socket客户端,向socket服务端写入消息。 1.创建服务端 public class RedisServer {public static void main(String[] args) throws IOException {

Java基础回顾系列-第七天-高级编程之IO

Java基础回顾系列-第七天-高级编程之IO 文件操作字节流与字符流OutputStream字节输出流FileOutputStream InputStream字节输入流FileInputStream Writer字符输出流FileWriter Reader字符输入流字节流与字符流的区别转换流InputStreamReaderOutputStreamWriter 文件复制 字符编码内存操作流(

android java.io.IOException: open failed: ENOENT (No such file or directory)-api23+权限受权

问题描述 在安卓上,清单明明已经受权了读写文件权限,但偏偏就是创建不了目录和文件 调用mkdirs()总是返回false. <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/><uses-permission android:name="android.permission.READ_E

JavaEE-文件操作与IO

目录 1,两种路径 二,两种文件 三,文件的操作/File类: 1)文件系统操作 File类 2)文件内容操作(读文件,写文件) (1)打开文件 (2)关闭文件 (3)读文件/InputStream (4)写文件/OutputStream (5)读文件/reader (6)写文件/writer (7)Scanner 四,练习: 1,两种路径 1)绝对路径

Python---文件IO流及对象序列化

文章目录 前言一、pandas是什么?二、使用步骤 1.引入库2.读入数据总结 前言 前文模块中提到加密模块,本文将终点介绍加密模块和文件流。 一、文件流和IO流概述         在Python中,IO流是用于输入和输出数据的通道。它可以用于读取输入数据或将数据写入输出目标。IO流可以是标准输入/输出流(stdin和stdout),也可以是文件流,网络流等。

标准IO与系统IO

概念区别 标准IO:(libc提供) fopen fread fwrite 系统IO:(linux系统提供) open read write 操作效率 因为内存与磁盘的执行效率不同 系统IO: 把数据从内存直接写到磁盘上 标准IO: 数据写到缓存,再刷写到磁盘上

linux基础IO——动静态库——进程编址、进程执行、动态库加载

前言:本节内容为基础IO部分的最后一节, 主要是为了讲一下动静态库里面的动态库如何加载到内存, 动态库的地址等等。 但是,这些内容牵扯到了程序的编址, 程序的加载, 进程的执行等等知识点, 所以,我们会从程序的编址讲起, 一直到进程的执行, 以及动态库加载结束。         ps:本节内容涉及到了进程地址空间, 磁盘的内容, 建议友友们了解相关知识后再来观看。 目录

mybatis错误——java.io.IOException Could not find resource comxxxxxxMapper.xml

在学习Mybatis的时候,参考网上的教程进行简单demo的搭建,配置的没有问题,然后出现了下面的错误! Exception in thread "main" java.lang.RuntimeException: org.apache.ibatis.builder.BuilderException: Error parsing SQL Mapper Configuration. Cause:

day09-IO-字符流其它流

一、字符流 字符流(只能做文本文件的处理)字符输入流 Reader--FileReader字符输出流 Writer--FileWriter​使用文件字符输入流的好处:读取中文不会出现乱码问题 1.1 字符输入流 构造器说明public FileReader (File file)创建字符输入流管道与源文件接通public FileReader(String pathname)创建字