【模板】最小费用最大流

洛谷模板题

没什么好说的，用spfa来找增广路。

1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 const int INF = 1 << 26; 8 int n, m, s, t, cnt; 9 int to[100001], val[100001], next[100001], cost[100001], head[5001], pre[5001], path[5001], dis[5001]; 10 //pre记录前一个节点，path记录边 11 bool vis[5001]; 12 13 inline int read()//读入优化 14 22 while(ch >= '0' && ch <= '9') 23 27 return x * f; 28 } 29 30 inline void add(int a, int b, int c, int d) 31 38 39 inline bool spfa() 40 67 } 68 } 69 } 70 return pre[t] != 1; 71 } 72 73 int main() 74 90 while(spfa()) 91 101 } 102 printf("%d %d", flow, money); 103 return 0; 104 }
View Code

但是spfa对于稠密图的处理效果不是很好，所以改用dijkstra+stl堆优化，至少快了些。。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #define Heap pair<int, int> 5 6 using namespace std; 7 8 const int INF = 1 << 26; 9 int n, m, s, t, cnt; 10 int to[100001], val[100001], next[100001], cost[100001], head[5001], pre[5001], path[5001], dis[5001]; 11 //pre记录前一个节点，path记录边 12 13 inline int read()//读入优化 14 22 while(ch >= '0' && ch <= '9') 23 27 return x * f; 28 } 29 30 inline void add(int a, int b, int c, int d) 31 38 39 bool Dijkstra() 40 } 64 } 65 return pre[t] != 1; 66 } 67 68 int main() 69 85 while(Dijkstra()) 86 96 } 97 printf("%d %d", flow, money); 98 return 0; 99 }
View Code

洛谷改了数据之后dijk居然T了。。

上一篇：IDEA 常用快捷键

下一篇：【模板】链式前向星+spfa

---

stl 最小费用最大流 最大流 模板 堆 网络流