编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：34ms

以前一直用邻接矩阵编，这次换用链表调了N久。。。

SAP+GAP+当前弧优化=AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 181ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：362ms

网络流建模题（最小割模型）。

把所有的中转站和用户群看成流网络中的点，增加一个源和汇。

源连到所有的中转站，容量为pi；所有的用户群连到汇，容量为ci。然后对于每个用户群所使用的中转站ai和bi，分别连一条边到用户群i，容量为无穷大。

最小割即为最少的建设中转站费用加上失去用户群的收益。

最终的答案为所用用户群的收益减最小割（最大流）。

p.s. 想要程序奔的快，SAP、Gap、邻接表、当前弧一个不能少。一开始没写当前弧，程序慢了数倍……

P1000 P1001 P1002 P1003 P1004 P1006 P1007 P1008 P1011 P1014 P1016 P1019 P1021 P1022 P1023 P1024 P1025 P1028 P1029 P1030 P1032 P1033 P1034 P1035 P1037 P1039 P1040 P1041 P1042 P1045 P1046 P1047 P1051 P1055 P1057 P1058 P1059 P1060 P1061 P1062 P1063 P1064 P1066 P1069 P1071 P1072 P1073 P1078 P1080 P1090 P1092 P1093 P1096 P1097 P1098 P1100 P1102 P1103 P1104 P1113 P1114 P1115 P1116 P1117 P1118 P1120 P1121 P1122 P1123 P1125 P1126 P1127 P1128 P1129 P1130 P1131 P1133 P1134 P1139 P1141 P1143 P1144 P1146 P1153 P1164 P1165 P1176 P1180 P1181 P1182 P1187 P1192 P1196 P1198 P1199 P1200 P1201 P1203 P1211 P1212 P1216 P1217 P1218 P1220 P1223 P1229 P1230 P1232 P1234 P1237 P1242 P1248 P1249 P1253 P1257 P1258 P1263 P1279 P1281 P1282 P1290 P1291 P1293 P1294 P1300 P1301 P1302 P1303 P1304 P1307 P1312 P1313 P1314 P1315 P1316 P1317 P1318 P1319 P1320 P1324 P1327 P1333 P1334 P1335 P1336 P1344 P1347 P1354 P1355 P1356 P1359 P1360 P1361 P1362 P1363 P1364 P1369 P1372 P1378 P1379 P1380 P1382 P1383 P1385 P1393 P1398 P1406 P1407 P1408 P1409 P1412 P1413 P1414 P1415 P1421 P1425 P1431 P1433 P1436 P1437 P1439 P1445 P1446 P1447 P1449 P1450 P1454 P1455 P1456 P1474 P1482 P1484 P1485 P1493 P1495 P1496 P1497 P1498 P1500 P1501 P1502 P1505 P1509

多吧！！！！！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 1694ms

├ 测试数据 10：答案正确... 1741ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3435ms

一次AC了，不过没有加当前弧优化 ，很慢！

请问残余流量的数组怎么开

SAP+GAP+CQF优化=AC

我巨菜,一开始0分,以为SAP都写错了

疯狂看别人程序,没错啊

原来是累加了建站的费用而没去计算客户的收益

迥了

跪求标程：只是想学学Dinic，别无他求；

那位超级大牛可以帮我，感激不尽；

我必：生当殒首，死当结草；谢谢。

Dinic+贪出流，所有点秒闪。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

Dinic居然打错了一个小地方。。。

普通SAP就行了,本人没有任何优化

SAP+GAP速度太快了！！！！！

Sap+Gap+Current Edge=34ms Accepted

提交的时候还有点害怕，在我的机子上最后俩点都要0.9s左右，我就害怕评测机抽个筋...

还好puppy听话，那么快...看来我要换机器了，跟不上时代的步伐了..

非递归实现dinic

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

sap+间隙优化+当前弧

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 25ms

to curimit：

不要惊叹，不加GAP和当前弧优化的SAP更本没有意义

就是个最小割,SAP 0.3s就过了.根本不需要什么贪心流啊堆啊

刘亦菲给我口交。

我才发现这道题目是我发出来的. 今天终于AC了....

啊, 题解骗人的, 写贪心流还不死掉啊, Dinic简单的要死...快得要死...