poj2135最小费用流
2024-10-19 07:31:04
裸题,就是存个模板
最小费用流是用spfa求解的,目的是方便求解负环,spfa类似于最大流中的bfs过程
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 20090717
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; struct edge{
int to,Next,c;
int cost;
}e[maxn<<];
int cnt,head[N];
int s,t;
int dis[N],pre[N],path[N];
void add(int u,int v,int c,int cost)
{
e[cnt].to=v;
e[cnt].c=c;
e[cnt].cost=cost;
e[cnt].Next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].c=;
e[cnt].cost=-cost;
e[cnt].Next=head[v];
head[v]=cnt++;
}
bool spfa()
{
memset(pre,-,sizeof pre);
memset(dis,inf,sizeof dis);
dis[s]=;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];~i;i=e[i].Next)
{
int te=e[i].to;
if(e[i].c>&&dis[x]+e[i].cost<dis[te])
{
dis[te]=dis[x]+e[i].cost;
pre[te]=x;
path[te]=i;
q.push(te);
}
}
}
return pre[t]!=-;
}
int mincostmaxflow()
{
int cost=,flow=;
while(spfa())
{
int f=inf;
for(int i=t;i!=s;i=pre[i])
if(e[path[i]].c<f)
f=e[path[i]].c;
flow+=f;
cost+=dis[t]*f;
for(int i=t;i!=s;i=pre[i])
{
e[path[i]].c-=f;
e[path[i]^].c+=f;
}
}
return cost;
}
void init()
{
memset(head,-,sizeof head);
cnt=;
}
int main()
{
/* ios::sync_with_stdio(false);
cin.tie(0);*/
int n,m;
while(~scanf("%d%d",&n,&m))
{
init();
s=,t=n+;
for(int i=;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,,c);
add(b,a,,c);
}
add(,,,);
add(n,n+,,);
printf("%d\n",mincostmaxflow());
}
return ;
}
/******************** ********************/
最新文章
- Eclipse迁移到Android studio步骤如下:
- C# 读取和配置IniFile
- August 8th 2016, Week 33rd Monday
- C++ Primer 第5版
- 『TCP/IP详解——卷一:协议』读书笔记——09
- sql批量获取wordpress所有留言者的邮件地址
- 洛谷P2727 01串 Stringsobits
- Android开源项目发现---Menu 篇(持续更新)
- jQuery练习实例(四)
- DOS头分析
- spider RPC更新至2.0.0-RELEASE
- Rust语言之HelloWorld Web版
- VS2017移动开发(C#、VB.NET)——Numeric控件的使用方式
- HTML5_canvas_像素操作_图片马赛克_图片反相
- Docker代理设置方法
- Java 8 停止维护,Java 9 难产,IDEA 2018 发布,还有……
- intest
- activemq 消息类型
- 基于 Python 和 Pandas 的数据分析(7) --- Pickling
- 2.15 C++常量指针this
热门文章
- Git 命令行帮助
- MySQL中Cardinality值的介绍
- 基于Cpython的 GIL(Global Interpreter Lock)
- Python中的魔术(双下划线&#39;__xxx__&#39;)方法详解
- 生产者,消费者,CDN
- 解决\build\outputs\apk\dream-debug.apk does not exist on disk错误
- Java基础—抽象类和接口
- 20170330 ABAP代理生成
- JavaWeb:实现文件上传与下载
- 吐槽 MySQL数据库jdbc操作,varchar类型占位符问题——单引号造孽