洛谷模板题
没什么好说的，用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了。。
上一篇：[洛谷P2580]于是他错误的点名开始了（Trie树）
下一篇：NOIP2009T3最优贸易（Dfs + spfa）
最小费用最大流 最大流 堆 模板 stl 网络流
