网络流

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PI; const int INF = 0x3f3f3f3f; const int MAXN = 1500; const...

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

题意：在n个点上有着食物，有m条边，除了第一个走的人，其他人都有pi的概率这条边，再大家都能获得食物的前提下，求破坏网络的概率最小。 思路： 每条边有走的次数（流量），每条边走一次发生破坏概率为p（流量1，费用p），容易想到费用流。可是费用流往往是费用相加的，这个是概率，只能相乘。有什么办法，log函数可以把乘除法转换为加减法。所以对每个概率取个log当成费...

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

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

题意：n个点，m条边，构建有权无向图。求出删去最少条边数没有最短路，以及删出最多条边，使最短路的长度不变。 思路：先处理出最短路，然后使用结果的dis数组，若dis[v]-dis[u] = w(u,v)，则该路就是最短路经中的一条边。建出最短路径之后跑最大流，流量是有多少边权相同的重边，跑出来就是最小割，也就是阻断所有最短路的最小花费。最后再跑最短路，边权为...