题意：~ 思路：给定一个图，几个障碍点，问删除至多一条边能否使得起始位置到不了终点位置，即求最小割。数据范围较大，还卡SAP，ISAP，只能用dinic过？ #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long lo...

题目链接：点我~~ 题意：n个点m条边的有向图，f个可选城市，每个城市都有其价值w，国王的城市在1，要分配一些城市，分配的原则是：只能在规定的f个城市中选若干个，这f个城市每个都有一个价值，被选择的城市要与城市1隔离，所以需要花费一些费用来破坏边。问能获取到的最大利益，以及要破坏的边。 思路：求能获取的最大利益，先建立一个超级汇点，将f个可选城市与汇点连接，...

题目链接：点我~~ 题意：1000个点10000条边的无向图，敌人从n走一条最短路到1，在第i条路设置障碍的代价是wi，求最少的代价使得敌人至少会遇到一次障碍。 思路：先确定最短路，然后在最短路径上跑一个网络流，即可求出最小割。 #include <bits/stdc++.h> using namespace std; typedef lon...