题目链接: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 ;
}

最新文章

  1. HTTP Session、Cookie机制详解
  2. 报错:org.hibernate.AssertionFailure: null id in com.tt.hibernate.entities.News entry (don&#39;t flush the Session after an exception occurs)
  3. 如何在安装程序中判断操作系统是否是64位 inno
  4. EF,MVC相关项目请参见→
  5. 前端优化:DNS预解析提升页面速度
  6. 好用的编辑框布局控件TdxLayoutControl
  7. C按格式输出数字
  8. Windows服务之启动、停止、暂停、继续
  9. MySQL函数大全【转载】
  10. framework7+node+mongo项目
  11. Maven学习-Profile详解
  12. 表空间移动(transporting tablespaces)
  13. 【dp】P2642 双子序列最大和
  14. 距离不是一个连续的物理量(Distance is not a continuous physical quantity)
  15. java中编写增删改查
  16. 下拉框插件select2的使用
  17. JavaSE回顾及巩固的自学之路(一)——————前言
  18. 【数据库问题】sql server 获取MD5值结果不一致的问题 substring(sys.fn_sqlvarbasetostr(HashBytes(&#39;MD5&#39;,&#39;111111&#39;)),11,32)
  19. 【Windows】Windows中解析DOS的for命令使用
  20. 如何通过创建切片器窗格节省PowerBI报告空间

热门文章

  1. 中文输入法无法在 QtCreator(Linux) 中输入汉字
  2. Object 公共方法详解
  3. CSS3动画属性animation的基本用法
  4. vscode插件推荐
  5. git本地分支关联远程分支
  6. (三)PHP网页架站
  7. BZOJ2438: [中山市选2011]杀人游戏(tarjan)
  8. css 小常识
  9. react里面stateless函数的默认参数
  10. SpringBoot-mvn插件