| 题目名称 | 1291. [ZJOI 2011] 最小割 |
|---|---|
| 输入输出 | mincuto.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 15 |
| 题目来源 |
 Makazeu
于2013-01-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：75， 提交：235， 通过率：31.91% | ||||
 CreationAugust |
100 | 0.465 s | 1.85 MiB | C++ |
 faebdc |
100 | 0.498 s | 0.55 MiB | C++ |
 Rivendell |
100 | 0.512 s | 1.53 MiB | C++ |
 fye |
100 | 0.533 s | 0.70 MiB | C++ |
 小DOTA |
100 | 0.538 s | 2.88 MiB | C++ |
 徐心雨 |
100 | 0.565 s | 0.69 MiB | C++ |
 sunshine123 |
100 | 0.598 s | 1.07 MiB | C++ |
|
sunshine123 |
100 | 0.617 s | 1.07 MiB | C++ |
 stdafx.h |
100 | 0.619 s | 0.84 MiB | C++ |
|
sunshine123 |
100 | 0.623 s | 1.07 MiB | C++ |
| 关于 最小割 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
多组数据要清空........好久没有学新东西了QWQ
| ||||
|
祝大家NOIP rp++
 泪寒之雪
2017-11-09 20:40
10楼
| ||||
|
| ||||
|
好吧 我傻了
stdafx.h
2016-01-28 22:58
8楼
| ||||
|
为毛写floydWA,写dfs就A了.....
stdafx.h
2016-01-28 22:56
7楼
| ||||
|
回复 @GDFRWMY :
喵的........我是刷水狂魔,还有这个叫水题?  Chenyao2333
2014-05-12 11:23
6楼
| ||||
 GDFRWMY
2014-05-11 10:58
5楼
| ||||
|
Chenyao2333
2014-05-11 10:27
4楼
| ||||
|
回复 @cstdio :
弱菜的博客怎能入神犇的眼= = GDFRWMY
2014-05-10 22:43
3楼
| ||||
|
回复 @GDFRWMY :
犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇你的博客呢 | ||||
Hale
cstdio【题目描述】
小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话：
“对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点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
5 0
1
0
【样例输出】
10
【提示】
对于30%的数据 n<=40,m<=400,q<=10
对于100%的数据 T<=10,n<=150,m<=3000,q<=30，x在32位有符号整数类型范围内。
图中两个点之间可能有多条边
【来源】
ZJOI2011 Day1