[luoguP2045] 方格取数加强版（最小费用最大流）

传送门

水题

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 51 6 #define M 100001 7 #define INF 1e9 8 #define min(x, y) ((x) < (y) ? (x) : (y)) 9 10 int n, k, s, t, cnt, tot, sum; 11 int head[M], to[M], val[M], cost[M], next[M], dis[M], pre[M], a[N][N], b[N][N]; 12 bool vis[M]; 13 14 inline int read() 15 22 23 inline void add2(int x, int y, int z, int c) 24 31 32 inline void add(int x, int y, int z, int c) 33 37 38 inline bool spfa() 39 } 64 } 65 } 66 return pre[t] ^ 1; 67 } 68 69 int main() 70 83 for(i = 1; i <= n; i++) 84 for(j = 1; j <= n; j++) 85 89 add(s, 1, k, 0); 90 add(n * n << 1, t, k, 0); 91 while(spfa()) 92 100 sum += dis[t] * d; 101 } 102 printf("%d\n", sum); 103 return 0; 104 }
View Code

上一篇：[POJ3162]Walking Race（DP + 单调队列）

下一篇：[luoguP1197] [JSOI2008]星球大战（并查集）

---

最小费用最大流 网络流