TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2981
  • 题目
  • P2981【CH Fimbulvetr::Prologue】起源
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    题目背景:

    起源是生命的因,因此也决定着生命的走向,当然,也因此而不可见。
    望着即将关闭的龙之门,既然如此,我的起源又是什么呢?妮妮安陷入了沉思。
    一阵春风吹进了龙之门。
    风吹入树干,带来了生命。
    坐在树下的,是仍沉浸在终章《光》中的你。
    “气流么……好像水流的声音呢……”

    题目描述:
    你想到了费用流。
    假定树根是源点,每个叶子连向汇点一条流量为正无穷,费用为0的边,请你对这棵树求费用流。

    输入格式

    输入共N行。
    第一行,一个整数N,树中节点的个数,其中1号节点是根。
    接下来N-1行,每行四个整数,Xi,Yi,Capi,Costi。表示有一条从Xi到Yi,容量为Capi,费用为Costi的边。保证Xi是Yi的父亲。

    输出格式

    输出共两行。
    第一行,一个整数,表示树上的最大流。
    第二行,一个整数,表示最大流时树上的最小费用。

    样例输入

    7
    1 2 2 3
    2 3 2 5
    3 6 2 4
    2 5 1 3
    1 4 5 1
    4 7 3 2

    样例输出

    5
    27

    提示

    对于10%的数据,1<=N<=1000
    对于另外20%的数据,数据保证是用某种方式随机生成的。
    对于100%的数据,1<=N<=100000,1<=Xi,Yi<=N,1<=Capi<=400000,0<=Cost<=1000,答案保证不超过231-1。


    来源  感谢Mahiro命题,感谢nodgd放题