发了网络流,再来一发费用流

能做费用流的,网络流自然做得来,但在这还是不要脸的安利一下自己的博客(里面也有网络流的题解):

点我

扯远了...

费用流,就是在不炸水管的情况下求源点到汇点的最小费用。

有没有想起什么?

思考一下......

对,最短路径!

所以我们完全可以用已死的SPFA求出不炸水管的最短路径(当然,实在有心理阴影的可以用dijkstra)。

如果你最短路径都不会,还是去 这儿 和 这儿

然后再一把增广路求出最大流与最小费用就好了(我觉得很OK)

献上本蒟蒻的代码:

#include<cstdio>
#define maxn 5050
#define maxm 50005
#define INF 0x3f3f3f3f
inline int read(){
int r=,f=;
char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){r=(r<<)+(r<<)+c-'';c=getchar();}
return r*f;
}
int s,t,n,m,head[maxn],pre[maxn],dis[maxn],q[maxn];
bool vis[maxn];
int s_e;
struct E{
int v,c,w,nxt;
}e[maxm*];
struct Max_fei{//本人喜欢结构体
inline void a_e(int u,int v,int c,int w){
e[s_e]=(E){v,c,w,head[u]};
head[u]=s_e++;
}
inline void add(int u,int v,int c,int w){
a_e(u,v,c,w);
a_e(v,u,,-w);
}
inline bool spfa(){
for(int i=;i<=n;i++){
dis[i]=INF;
vis[i]=false;
}
dis[s]=;
vis[s]=true;
q[]=s;
int hd=,tl=;
while(hd^tl){
int u=q[hd++];//循环队列
hd%=maxn;
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w&&e[i].c){//判断水管还能运水吗
dis[v]=dis[u]+e[i].w;//更新
pre[v]=i;//记录位置
if(vis[v])continue;//如果在队里,那就不进队
vis[v]=true;
q[tl++]=v;
tl%=maxn;
}
}
vis[u]=false;
}
if(dis[t]==INF)return false;
return true;
}
inline int min(int a,int b){//原谅我的手写min
return a<b?a:b;
}
inline int end(int &flow){//flow求最大流
int p,u,Min=1e9,ans=;
for(u=t;u!=s;u=e[p^].v){//因为开始值为0,可以用xor来找反边
p=pre[u];//往前找
Min=min(Min,e[p].c);//找全部经过水管都能流过的最大流 }
for(u=t;u!=s;u=e[p^].v){
p=pre[u];
e[p].c-=Min;
e[p^].c+=Min;
ans+=e[p].w*Min;//加费用
}
flow+=Min;//加最大流
return ans;
}
inline int solve(int &flow){
int ans=;
while(spfa()){
ans+=end(flow);
}
return ans;
}
}Flow;
inline void work(){
n=read();m=read();
s=read();t=read();
for(int i=;i<=n;i++)head[i]=-;//初始值为-1,方便xor
for(int i=;i<=m;i++){
int u=read(),v=read(),c=read(),w=read();
Flow.add(u,v,c,w);
}
int flow=;
int ans=Flow.solve(flow);
printf("%d %d\n",flow,ans);
}
int main(){
work();
return ;
}

最新文章

  1. Mvc网站发布到IIS
  2. maven 手动安装jar到仓库的命令
  3. 深入浅出百度地图API开发系列(2):创建地图
  4. CPU/寄存器/内存
  5. (转载)MVC 4.0 PartialView()与View()真的一样吗?
  6. [补档][COGS 2434]暗之链锁
  7. Spring3.x企业开发应用实战读书笔记 —— 第三章IoC容器概述
  8. 国内可用的Internet时间同步服务器地址(NTP时间服务器)
  9. unity零基础开始学习做游戏(四)biu~biu~biu发射子弹打飞机
  10. Gradle连接Maven仓库直接从仓库 更新JAR包
  11. procemon
  12. 通过本质看现象:关于Integer受内部初始化赋值范围限制而出现的有趣现象
  13. 2018上C语言程序设计(高级)作业- 第3次作业成绩
  14. Nodejs 使用Protobuf
  15. FortiGate 路由
  16. 外观模式Facade pattern
  17. HashMap怎样解决碰撞问题
  18. 索引Hint提示(INDEX Hint)
  19. [LeetCode] 674. Longest Continuous Increasing Subsequence_Easy Dynamic Programming
  20. MongoDB 之 aggregate $group 巧妙运用

热门文章

  1. 使用Storyboard实现复杂界面
  2. ASP.NET-Session与复杂数据类型
  3. 《iOS Human Interface Guidelines》——System Button
  4. JSON数据的生成与解析
  5. [Unit Testing] Configure the Angular CLI to use the Karma Mocha test reporter
  6. (手冊)Animation 之 使用Animation View
  7. CoreData 从入门到精通(四)并发操作
  8. BZOJ 2194 FFT
  9. 你不知道的JavaScript(五)内置对象模版
  10. LeetCode 1. Two Sum (c++ stl map)