CCPC 2018秦皇島A題Build(ネットワークフロー、制限費用の最小費用最大フロー)

CCPC 2018秦皇島A題Build(ネットワークフロー、制限費用の最小費用最大フロー)

題意:無方向図を与えて、各辺の容量と単位の費用を与えて、1からnまで費用がfを超えない最大の流れを求めます
今回spfaが走り出した流量が全部買えなくなったら、一部を切って買います.

#include  using namespace std; const int maxn = 2100; const int maxm = 2100000; const int inf = 0x3f3f3f3f3f3f3f3f; typedef long long ll; struct Edge { int to, nex; ll cap, flow, cost; } edge[maxm]; int head[maxn], tot; int pre[maxn]; ll dis[maxn]; bool vis[maxn]; int N; void init(int n) { N = n; tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v, int cap, int cost) { edge[tot].to = v; edge[tot].cap = cap; edge[tot].cost = cost; edge[tot].flow = 0; edge[tot].nex = head[u]; head[u] = tot++; edge[tot].to = u; edge[tot].cap = 0; edge[tot].cost = -cost; edge[tot].flow = 0; edge[tot].nex = head[v]; head[v] = tot++; } bool spfa(int s, int t) { queue q; for (int i = 0; i <= N; i++) { dis[i] = inf; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = edge[i].nex) { int v = edge[i].to; if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if (!vis[v]) { vis[v] = true; q.push(v); } } } } return pre[t] != -1; } int n, m; ll f; ll mcmf(int s, int t, ll &cost, ll flow) { cost = 0; while (spfa(s, t)) { ll Min = inf; ll cost1 = 0; for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) { if (Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) { edge[i].flow += Min; edge[i ^ 1].flow -= Min; cost1 += edge[i].cost; } ll tmp = (f - cost) / cost1; if (Min > tmp) return flow + tmp; cost += cost1 * Min; flow += Min; } return flow; } int mx[maxm], costi[maxm]; int from[maxm], to[maxm]; int main() { scanf("%d %d %lld", &n, &m, &f); init(2 * n + 1); addedge(0, 1, inf, 0); for (int i = 1; i <= n; i++) { addedge(i, i + n, inf, 0); } for (int i = 1; i <= m; i++) { scanf("%d %d %d %d", &from[i], &to[i], &mx[i], &costi[i]); addedge(from[i] + n, to[i], mx[i], costi[i]); addedge(to[i] + n, from[i], mx[i], costi[i]); } ll cost, flow; flow = mcmf(0, 2 * n, cost, 0); printf("%lld
", flow); return 0; }