****OJ - 1**7 B***d (费用流)
题意 某国防御系统需要保证节点1和节点n保持联通，每条路有一个防卫等级的属性，初始都为0，最高限制为 m a x i max_i maxi?,每提高一级需要花费 c o s t i cost_i costi?，敌国每破坏一条路都要花费该路的等级那么多的成本，该国国防预算F，问最优防御策略下敌国需要多少钱才能使得该国防御系统瘫痪（使得1节点和n节点不连通）
思路 【****OJ - 1**7 B***d （费用流）】这题怎么看出来是网络流呢？我们可以把每条边的等级看成流量，每条边的等级上限看成容量，提高一级的花费就是费用了。每条路径破坏的最低成本就是该路径上等级最低的边。所以我们可以用费用流求该路径上的最小的边（找增广路的过程）。如果预算不足，那么就只能把预算平摊到该路径上的所有边。其实如果预算充足，最后求到的就是最小割。需要注意的是这题是无向图，一定要加反向的边，虽然防御联络的时候只会从1走到n，但是谁能保证题目不把边反着给呢？我这么wa了20发，疯狂在找自己费用流所谓不存在的bug，还好凉凉把我点醒了。比赛的时候因为G题的no response，卡死了G 的特判没空写这题（估计有空也是死在无向图这个坑上，毕竟做到的网络流题目基本都是有向图，我会想当然）。
因为官方重现没有放出，所以对题目进行了和谐处理，如果官方重现出了我就回来把屏蔽去掉（不鸽的话）
这可能是我最后一篇题解博客了，EC之前没有遗憾了
代码
#include
#include
#include
#include using namespace std;
struct edge{
long long from;
long long to;
long long flow;
long long cap;
long long cost;
long long nxt;
edge(long long f,long long t,long long ca,long long co,long long n):from(f),to(t),cap(ca),cost(co),nxt(n){
flow=0;
}
edge(){}
};
long long egs[1005];
vector edges;
void addedge(long long f,long long t,long long ca,long long co){
edges.emplace_back(f,t,ca,co,egs[f]);
egs[f]=edges.size()-1;
edges.emplace_back(t,f,0,-co,egs[t]);
egs[t]=edges.size()-1;
}
long long dis[1005];
long long pre[1005];
long long flower[1005];
bool vis[1005];
long long total;
long long bellmanford(long long s,long long t)
{
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
memset(pre,-1,sizeof pre);
memset(flower,0,sizeof flower);
dis[s]=0;
flower[s]=0x3f3f3f3f3f3f3f3f;
deque qq;
qq.push_back(s);
vis[s]=true;
while(!qq.empty())
{
long long now=qq.front();
qq.pop_front();
for(long long i=egs[now];
i!=-1;
i=edges[i].nxt)
{
if(edges[i].cap-edges[i].flow>0 && dis[edges[i].to]>dis[now]+edges[i].cost)
{
dis[edges[i].to]=dis[now]+edges[i].cost;
pre[edges[i].to]=i;
flower[edges[i].to]=min(flower[now],edges[i].cap-edges[i].flow);
if(!vis[edges[i].to])
{
if((!qq.empty()) && dis[edges[i].to]0){//直接把nowflow=bellmanford(s,t)放进来在oj上好像会死循环不知道为啥
if(nowflow*dis[t]+mincost> n >> m >> f;
memset(egs, -1, sizeof egs);
edges.clear();
total = n;
for (long long i = 0;
i < m;
i++) {
long long a, b, c, d;
cin >> a >> b >> c >> d;
addedge(a, b, c, d);
addedge(b, a, c, d);
//加了这句话就过了，死在无向图20发
}
cout << mfmc(1, n, f) << "\n";
//除了加了预算限制外就是裸的费用流
return 0;
}
感谢我校最强银牌图论选手女装凉
