bzoj1877 晨跑 费用流

Description

---

给出n个点m条边，求不重复地从1出发走到n点最多走多少次，最短走多长的路

Solution

---

对于第一问就是拆点的最大流。第二问显然不能单纯用最大流解决了，于是我们每条边引入一个费用的概念，表示单位流量的价格。

连边的时候反向弧的费用要为相反数，那么就是每次找增广路的时候同时找一条费用最小的。因为有负权边所以只能spfa实现

调了一下午我果然还是太弱啊

Code

---

#include <stdio.h> #include <string.h> #include <queue> #define rep(i, st, ed) for (int i = st; i <= ed; i += 1) #define erg(i, st) for (int i = ls[st]; i; i = e[i].next) #define fill(x, t) memset(x, t, sizeof(x)) #define INF 0x3f3f3f3f #define N 501 #define E 40001 struct edge{int x, y, w, c, next;}e[E]; struct data{int x, t;}; int rc[N][N], ls[N]; inline void addEdge(int &cnt, int x, int y, int w, int c){ cnt += 1; e[cnt] = (edge){x, y, w, c, ls[x]}; ls[x] = cnt; cnt += 1; e[cnt] = (edge){y, x, 0, -c, ls[y]}; ls[y] = cnt; } int inQueue[N], dis[N], pre[N], q[N]; inline int spfa(int st, int ed){ fill(dis, 63); fill(inQueue, 0); dis[st] = 0; inQueue[st] = 1; int head = 0, tail = 1; q[tail] = st; while (head != tail){ head += 1; if (head == N){ head = 1; } int now = q[head]; erg(i, now){ if (e[i].w > 0 && dis[now] + e[i].c < dis[e[i].y]){ dis[e[i].y] = dis[now] + e[i].c; pre[e[i].y] = i; if (!inQueue[e[i].y]){ tail += 1; if (tail == N){ tail = 1; } q[tail] = e[i].y; inQueue[e[i].y] = 1; } } } inQueue[now] = 0; } return dis[ed] != INF; } inline int min(int x, int y){ return x<y?x:y; } int ans1 = 0, ans2 = 0; inline void mcf(int st, int ed){ int mn = INF; for (int i = ed; pre[i]; i = e[pre[i]].x){ mn = min(mn, e[pre[i]].w); } for (int i = ed; i; i = e[pre[i]].x){ e[pre[i]].w -= mn; e[pre[i] ^ 1].w += mn; ans2 += mn * e[pre[i]].c; } ans1 += 1; } int main(void){ int n, m; scanf("%d%d", &n, &m); int st = 1, ed = n + n; int edgeCnt = 1; fill(ls, 0); rep(i, 1, m){ int x, y, w; scanf("%d%d%d", &x, &y, &w); addEdge(edgeCnt, x + n, y, 1, w); } rep(i, 2, n - 1){ addEdge(edgeCnt, i, i + n, 1, 0); } addEdge(edgeCnt, st, st + n, INF, 0); addEdge(edgeCnt, n, ed, INF, 0); while (spfa(st, ed)){ mcf(st, ed); } printf("%d %d\n", ans1, ans2); return 0; }