【luogu P3381 最小费用最大流】 模板
2024-10-21 06:04:28
题目链接:https://www.luogu.org/problemnew/show/P3381
把bfs变成spfa
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = + ;
int n, m, s, t, maxflow, mincost, dis[maxn], flow[maxn], pre[maxn], last[maxn];
struct edge{
int to, next, cost, flow;
}e[maxn<<];
int head[maxn], cnt = -;
bool vis[maxn];
queue<int> q;
void add(int u, int v, int w, int c)
{
e[++cnt].next = head[u];
e[cnt].to = v;
e[cnt].cost = c;
e[cnt].flow = w;
head[u] = cnt; e[++cnt].next = head[v];
e[cnt].to = u;
e[cnt].cost = -c;
e[cnt].flow = ;
head[v] = cnt;
}
bool SPFA(int s, int t)
{
memset(dis, 0x7f, sizeof(dis));
memset(flow, 0x7f, sizeof(flow));
memset(vis, , sizeof(vis));
q.push(s); pre[t] = -; vis[s] = ; dis[s] = ;
while(!q.empty())
{
int now = q.front(); q.pop();
vis[now] = ;
for(int i = head[now]; i != -; i = e[i].next)
{
if(e[i].flow > && dis[e[i].to] > dis[now] + e[i].cost)
{
dis[e[i].to] = dis[now] + e[i].cost;
pre[e[i].to] = now;
last[e[i].to] = i;
flow[e[i].to] = min(flow[now], e[i].flow);
if(!vis[e[i].to])
{
q.push(e[i].to);
vis[e[i].to] = ;
}
}
}
}
return pre[t] != -;
}
void MCMF(int s, int t)
{
while(SPFA(s, t))
{
int now = t;
maxflow += flow[t];
mincost += flow[t] * dis[t];
while(now != s)
{
e[last[now]].flow -= flow[t];
e[last[now]^].flow += flow[t];
now = pre[now];
}
}
}
int main()
{
memset(head, -, sizeof(head));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i = ; i <= m; i++)
{
int u, v, w, c;
scanf("%d%d%d%d",&u,&v,&w,&c);
add(u, v, w, c);
}
MCMF(s, t);
printf("%d %d\n",maxflow, mincost);
return ;
}
最新文章
- HTTP Session、Cookie机制详解
- 报错:org.hibernate.AssertionFailure: null id in com.tt.hibernate.entities.News entry (don&#39;t flush the Session after an exception occurs)
- 如何在安装程序中判断操作系统是否是64位 inno
- EF,MVC相关项目请参见→
- 前端优化:DNS预解析提升页面速度
- 好用的编辑框布局控件TdxLayoutControl
- C按格式输出数字
- Windows服务之启动、停止、暂停、继续
- MySQL函数大全【转载】
- framework7+node+mongo项目
- Maven学习-Profile详解
- 表空间移动(transporting tablespaces)
- 【dp】P2642 双子序列最大和
- 距离不是一个连续的物理量(Distance is not a continuous physical quantity)
- java中编写增删改查
- 下拉框插件select2的使用
- JavaSE回顾及巩固的自学之路(一)——————前言
- 【数据库问题】sql server 获取MD5值结果不一致的问题 substring(sys.fn_sqlvarbasetostr(HashBytes(&#39;MD5&#39;,&#39;111111&#39;)),11,32)
- 【Windows】Windows中解析DOS的for命令使用
- 如何通过创建切片器窗格节省PowerBI报告空间