| 题目名称 | 1575. [NEERC 2003][POJ2125]有向图破坏 |
|---|---|
| 输入输出 | destroyingthegraph.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 35 |
| 题目来源 |
 cstdio
于2014-04-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：65， 提交：129， 通过率：50.39% | ||||
 Marvolo |
100 | 0.000 s | 0.00 MiB | C++ |
 甘罗 |
100 | 0.000 s | 0.00 MiB | C++ |
|
Marvolo |
100 | 0.000 s | 0.00 MiB | C++ |
 abaoo |
100 | 0.016 s | 0.89 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.020 s | 0.48 MiB | C++ |
 小DOTA |
100 | 0.021 s | 0.88 MiB | C++ |
 dydxh |
100 | 0.023 s | 0.43 MiB | C++ |
|
小DOTA |
100 | 0.025 s | 0.90 MiB | C++ |
 葳棠殇 |
100 | 0.027 s | 1.48 MiB | C++ |
 new ioer |
100 | 0.028 s | 0.52 MiB | C++ |
| 关于 有向图破坏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
把w+和w-写反+1 可以说是so sad了
| ||||
|
w+和w-我也搞反了。。。。
 KZNS
2017-03-08 10:23
12楼
| ||||
|
最小割
| ||||
|
第一遍1A...重写第二遍W了...
以为是w+和w-看反了，然而跟先前A了的代码一对好像没写反... 一怒之下反着交了一遍，证明是我Dinic写挂了...药丸呐药丸...... 反向边容量加成跟正向边一样......身败名裂...... | ||||
|
啊啊！！苍天啊，我都看见评论了，w+和w-还是写反了！！！居然有71分！！
  浮生随想
2016-11-07 07:33
9楼
| ||||
|
那个w+和w-, 我没看反, 但是写的时候写反了, 居然对了一大半
| ||||
|
花式瞎玩最小割蒙对了..蛤蛤...输出文件名打错了没有1A真是氮藤
| ||||
|
不停地越界（捶桌。。
 raywzy
2015-10-05 22:30
6楼
| ||||
|
我相信这么执着于预流推进法的人只有我。。。
| ||||
|
手残党宣言,w+和w-搞反了
| ||||
Shirry
Go灬Fire
AntiLeaf
小e
四季木哥
mikumikumi
Chenyao23331575. [NEERC 2003][POJ2125]有向图破坏
★★★ 输入文件：destroyingthegraph.in
输出文件：destroyingthegraph.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
Alice和Bob正在玩如下的游戏。首先Alice画一个有N个顶点，M条边的有向图。然后Bob试着摧毁它。在一次操作中他可以找到图中的一个点，并且删除它所有的入边或所有的出边。
Alice给每个点定义了两个值：Wi+和Wi-。如果Bob删除了第i个点所有的入边他要给Alice付Wi+元，如果他删除了所有的出边就需要给Alice付Wi元。
找到Bob删除图中所有边需要的最小花费。
【输入格式】
输入数据描述了Alice画下的图。
输入文件的第一行有两个数N,M(1<=N<=100,1<=M<=5000)。第二行有N个整数，描述了N个点的Wi+，同样的第三行是这N个点的Wi-。所有的费用都是正数并且不超过10^6。接下来的M行每行有两个数，代表有向图中相应的一条边。
【输出格式】
输出一行一个整数，即Bob的最小花费。
【样例输入】
3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3
【样例输出】
5
【提示】
样例的一个方案是：删除点1，2所有的入边，删除点2所有的出边。
输出格式和原题有所不同。原题要求输出方案。
【来源】
Northeastern Europe 2003,Northern Subregion (NEERC 2003)