| 题目名称 | 1564. [SGU U252]铁路网 |
|---|---|
| 输入输出 | railwaycommunication.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-03-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：18， 提交：27， 通过率：66.67% | ||||
 AAAAAAAAAA |
100 | 0.005 s | 0.37 MiB | C++ |
 Hzoi_ |
100 | 0.006 s | 0.42 MiB | C++ |
 KZNS |
100 | 0.008 s | 0.46 MiB | C++ |
 cstdio |
100 | 0.012 s | 0.32 MiB | C++ |
 mikumikumi |
100 | 0.013 s | 0.55 MiB | C++ |
 AntiLeaf |
100 | 0.016 s | 0.46 MiB | C++ |
 Hzoi_chairman |
100 | 0.017 s | 0.39 MiB | C++ |
 YueYueZha |
100 | 0.018 s | 0.34 MiB | C++ |
 金身人面兽 |
100 | 0.018 s | 0.39 MiB | C++ |
 _Itachi |
100 | 0.021 s | 0.61 MiB | C++ |
| 关于 铁路网 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
1A，哈哈哈
AAAAAAAAAA
2017-07-29 16:14
5楼
| ||||
|
| ||||
|
"二分图开2倍点"*3....上午都因为这RE了下午又R一发。。。
| ||||
|
简直一毛一样
| ||||
|
又是一道模板题……
友情链接：728.最小路径覆盖问题 | ||||
面对疾风吧 疾风 疾风吧
sxysxy1564. [SGU U252]铁路网
★★★☆ 输入文件：railwaycommunication.in
输出文件：railwaycommunication.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
某国有N个城镇，M条铁路。所有的铁路都是单向的，并且铁路不行成环。必须按照如下事实选择最好的列车运行线：
运行线是指火车经过的一个城镇序列，必须满足如下要求：
1）每条铁路最多属于一条列车运行线
2）每个城镇最多被一条列车运行线通过（通过包括作为起点或终点）
3）每个城镇至少被一条列车运行线通过
4）列车运行线的数量应尽量小
并且，每条铁路都需要花钱维护，第i条铁路需要每年花费c[i]元来检修。这是该国总统决定安排列车运行线使得维护运行线上铁路的总费用最小。当然，这个任务被交给了你。
【输入格式】
输入文件的第一行有两个正整数N，M（1<=N<=100,0<=M<=1000）.接下来的M行描述了M条铁路。
每一行有三个整数a[i],b[i]和c[i]（1<=a[i],b[i]<=N,a[i]≠b[i]），即该条线路的起点，终点和维护费用（0<=c[i]<=1000）.因为铁路是单向的，火车只能从a[i]开到b[i]。两个城镇之间至多有一条铁路。
【输出格式】
输出一行两个正整数，即最少的运行线数量，和在此前提下最少的总花费。
【样例输入】
4 4
1 2 1
1 3 2
3 4 2
2 4 2
【样例输出】
2 3
【提示】
本题的输出格式和SGU上原题有所区别，在这里不要求输出答案。
【来源】
作者:Sergey Simonchik
来源:Petrozavodsk Summer Training Sessions 2004
日期:August 25, 2004