P3329 [ZJOI2011]最小割

    • 331通过
    • 1.1K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 分治 最小割 网络流 2011 浙江 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小白在图论课上学到了一个新的概念——最小割,下课后小白在笔记本上写下了如下这段话: ”对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点s,t不在同一个部分中,则称这个划分是关于s,t的割。

    对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量,而s,t的最小割指的是在关于s,t的割中容量最小的割“

    现给定一张无向图,小白有若干个形如”图中有多少对点它们的最小割的容量不超过x呢“的疑问,小蓝虽然很想回答这些问题,但小蓝最近忙着挖木块,于是作为仍然是小蓝的好友,你又有任务了。

    输入输出格式

    输入格式:

    输入文件第一行有且只有一个正整数T,表示测试数据的组数。 对于每组测试数据, 第一行包含两个整数n,m,表示图的点数和边数。 下面m行,每行3个正整数u,v,c(1<=u,v<=n,0<=c<=106),表示有一条权为c的无向边(u,v) 接下来一行,包含一个整数q,表示询问的个数 下面q行,每行一个整数x,其含义同题目描述。

    输出格式:

    对于每组测试数据,输出应包括q行,第i行表示第i个问题的答案。对于点对(p,q)和(q,p),只统计一次(见样例)。两组测试数据之间用空行隔开。

    输入输出样例

    输入样例#1: 复制
    1
    5 0
    1
    0
    输出样例#1: 复制
    10

    说明

    【数据范围】

    对于100%的数据 T<=10,n<=150,m<=3000,q<=30,x在32位有符号整数类型范围内。

    图中两个点之间可能有多条边

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。