最小费用最大流模板(POJ 2135-Farm Tour)
2024-10-12 07:42:11
最近正好需要用到最小费用最大流,所以网上就找了这方面的代码,动手写了写,先在博客里存一下~
代码的题目是POJ2135-Farm Tour
需要了解算法思想的,可以参考下面一篇文章,个人觉得有最大流基础的童鞋,看了基本就能看懂了,通俗易懂。
https://www.cnblogs.com/gtarcoder/p/4890739.html
#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm> #define E 50000
#define maxn 1005
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
int u,v,flow,cost,next;
}edge[E]; int tot,head[maxn],pre[maxn],dist[maxn],vis[maxn];
int n,m;
void add(int u,int v,int flow,int cost)//flow为流量 cost为费用
{
edge[tot].u=u;
edge[tot].v=v;
edge[tot].flow=flow;
edge[tot].cost=cost;
edge[tot].next=head[u];
head[u]=tot++;
} void addEdge(int u,int v,int flow,int cost){
add(u,v,flow,cost);
add(v,u,,-cost);
} bool SPFA(int s,int t,int n)
{
int v,tmp;
queue<int> q;
for(int i=;i<=n;i++)
{
pre[i]=-;
vis[i]=;
dist[i]=INF;
}
vis[s]=;
dist[s]=;
q.push(s);
while(!q.empty())
{
tmp=q.front();
q.pop();
vis[tmp]=;
for(int k=head[tmp];k!=-;k=edge[k].next)
if(edge[k].flow){
v=edge[k].v;
if(dist[v]>dist[tmp]+edge[k].cost){
dist[v]=dist[tmp]+edge[k].cost;
pre[v]=k; //存储对应的边
if(!vis[v]){
vis[v]=;
q.push(v);
}
}
}
}
return dist[t]!=INF;
} int mcmf(int s,int t,int n)
{
int flow=INF,ans=;
while(SPFA(s,t,n))
{
ans+=dist[t];
for(int k=pre[t];k!=-;k=pre[edge[k].u])
flow=min(flow,edge[k].flow);
for(int k=pre[t];k!=-;k=pre[edge[k].u])
{
edge[k].flow-=flow;
edge[k^].flow+=flow;
}
}
return ans;
} void init(){
for(int i=;i<maxn;i++)
head[i]=-;
tot=;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int s=,t=n+;
init();
for(int i=;i<m;i++){
int u,v,c;
scanf("%d %d %d",&u,&v,&c);
addEdge(u,v,,c);
addEdge(v,u,,c);
}
addEdge(s,,,);
addEdge(n,t,,);
int ans=mcmf(s,t,n+);
printf("%d\n",ans);
return ;
}
最新文章
- 我的MYSQL学习心得(十) 自定义存储过程和函数
- Nehe Opengl
- oracle、mysql、sql server等;流行数据库的链接驱动配置
- 161027、Java 中的 12 大要素及其他因素
- Ecshop安装过程中的的问题:cls_image::gd_version()和不支持JPEG
- git查看历史命令
- Careercup - Google面试题 - 5692127791022080
- Apache CXF实现Web Service(3)——Tomcat容器和不借助Spring的普通Servlet实现JAX-RS(RESTful) web service
- 【ERROR】---Error executing ";adb devices";:ADB server didn&#39;t ACK
- Daject初探之Record模型
- ios中Raw文件系统常用文件夹
- jsp页面间的传值
- RPC-client异步收发核心细节?
- 从0开始的Python学习012数据结构&;对象与类
- [HEOI2016/TJOI2016]排序
- Shiro权限管理框架详解
- 基于MFC的OpenGL程序<;转>;
- Error:svn: E160013 svn主干切换分支时报错
- 【NOIP 2018】填数游戏(思考与推导)
- java-selenium下载百度图片