#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint maxn = 1e3 + 10; int V; vector<int>G[maxn]; int match[maxn]; bool used[maxn]; voidadd_edge(int u, int v){ G[u].push_back(v); G[v].push_back(u); } booldfs(int v){ used[v] = 1; for (int i = 0; i < G[v].size(); i++) { int u = G[v][i], w = match[u]; if (w < 0 || !used[w] && dfs(w)) { match[v] = u; match[u] = v; returntrue; } } returnfalse; } intbi_match(){ int res = 0; memset(match, -1, sizeof(match)); for (int v = 1; v <= V; v++) { if (match[v] < 0) { memset(used, 0, sizeof(used)); if (dfs(v)) { res++; } } } return res; } int n, m; intmain(){ scanf("%d%d", &m, &n); V = n + m; int u, v; while (scanf("%d%d", &u, &v) && u != -1) { G[u].push_back(v); G[v].push_back(u); } int ans = bi_match(); if (ans == 0)printf("No Solution!\n"); else { printf("%d\n", ans); for (int i = 1; i <= V; i++) { if (match[i] != -1) { printf("%d %d\n", i, match[i]); match[match[i]] = -1; } } } return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint maxn = 1e6 + 10; int n, m, k; int mz[40][40]; intxy2id(int x, int y){ return x * m + y; } pii id2xy(int id){ returnpii(id / m, id%m); } structE { int from, to, cp, v; int rev; E() {} E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {} }; structMCMF { int n, m, s, t; vector<E> edges; vector<int> G[maxn]; bool inq[maxn]; //是否在队列 int d[maxn]; //Bellman_ford单源最短路径 int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号 int a[maxn]; //a[i]表示从s到i的最小残量 voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; for (int i = 0; i <= n; i++) G[i].clear(); edges.clear(); m = 0; }
voidaddedge(int from, int to, int cap, int cost){ edges.push_back(E(from, to, cap, cost, 0)); edges.push_back(E(to, from, 0, -cost, 1)); G[from].push_back(m++); G[to].push_back(m++); }
boolBellmanFord(int &flow, int &cost){ for (int i = 0; i <= n; i++) d[i] = INF; memset(inq, 0, sizeof inq); d[s] = 0, a[s] = INF, inq[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int& idx : G[u]) { E &e = edges[idx]; if (e.cp && d[e.to] > d[u] + e.v) { d[e.to] = d[u] + e.v; p[e.to] = idx; a[e.to] = min(a[u], e.cp); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; } } } } if (d[t] == INF) returnfalse; flow += a[t]; cost += a[t] * d[t]; int u = t; while (u != s) { edges[p[u]].cp -= a[t]; edges[p[u] ^ 1].cp += a[t]; u = edges[p[u]].from; } returntrue; }
pii go(){ int flow = 0, cost = 0; while (BellmanFord(flow, cost)); returnpii(flow, cost); } } MM; int dx[]{ 1,0 }; int dy[]{ 0,1 }; boolleg(int x, int y){ return x >= 0 && x < n&&y >= 0 && y < m && mz[x][y] != 1; } bool vis[maxn]; intmain(){ scanf("%d", &k); scanf("%d%d", &m, &n); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &mz[i][j]); } } if (mz[0][0] == 1) { printf("0\n"); return0; } int t = n * m - 1; MM.init(n*m, n*m, t); MM.addedge(MM.s, 0, 1, mz[0][0] == 2 ? -1 : 0); for (int x = 0; x < n; x++) { for (int y = 0; y < m; y++) { if (leg(x, y)) { int id = xy2id(x, y); for (int i = 0; i < 2; i++) { int nx = x + dx[i], ny = y + dy[i]; if (leg(nx, ny)) { MM.addedge(id, xy2id(nx, ny), 1, mz[nx][ny] == 2 ? -1 : 0); } } } } } for (int i = 1; i <= k; i++) { pii p = MM.go(); if (!p.first) { printf("0\n"); return0; } else { int u = 0; while (u != t) { vis[u] = 1; pii p = id2xy(u); int x = p.first, y = p.second; for (int j = 0; j < MM.G[u].size(); j++) { if (MM.edges[MM.G[u][j]].rev)continue; if (MM.edges[MM.G[u][j]].cp == 0) { int v = MM.edges[MM.G[u][j]].to; u = v; if (id2xy(v).first == x)printf("%d %d\n", i, 1); elseprintf("%d %d\n", i, 0); break; } } } vis[u] = 1; for (int i = 0; i < MM.m; i += 2) { if (vis[MM.edges[i].to])MM.edges[i].v = MM.edges[i + 1].v = 0; MM.edges[i].cp = 1; MM.edges[i + 1].cp = 0; } } } return0; }
structE { int from, to, cp, v; E() {} E(int f, int t, int cp, int v) :from(f), to(t), cp(cp), v(v) {} }; structMCMF { int n, m, s, t; vector<E> edges; vector<int> G[maxn]; bool inq[maxn]; //是否在队列 int d[maxn]; //Bellman_ford单源最短路径 int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号 int a[maxn]; //a[i]表示从s到i的最小残量 voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); m = 0; }
voidaddedge(int from, int to, int cap, int cost){ edges.push_back(E(from, to, cap, cost)); edges.push_back(E(to, from, 0, -cost)); G[from].push_back(m++); G[to].push_back(m++); }
boolBellmanFord(int &flow, ll &cost){ for (int i = 0; i < n; i++) d[i] = INF; memset(inq, 0, sizeof inq); d[s] = 0, a[s] = INF, inq[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int& idx : G[u]) { E &e = edges[idx]; if (e.cp && d[e.to] > d[u] + e.v) { d[e.to] = d[u] + e.v; p[e.to] = idx; a[e.to] = min(a[u], e.cp); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; } } } } if (d[t] == INF) returnfalse; flow += a[t]; cost += a[t] * d[t]; int u = t; while (u != s) { edges[p[u]].cp -= a[t]; edges[p[u] ^ 1].cp += a[t]; u = edges[p[u]].from; } returntrue; }
ll go(){ int flow = 0; ll cost = 0; while (BellmanFord(flow, cost)); return cost; } } MM;
int N; int r[maxn]; ll p, m, f, n, s; int S, T; intmain(){ scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &r[i]); } S = 2 * N, T = 2 * N + 1; cin >> p >> m >> f >> n >> s; MM.init(2 * N + 2, S, T); for (int i = 0; i < N; i++) { MM.addedge(S, 2 * i, INF, p); MM.addedge(S, 2 * i + 1, r[i], 0); MM.addedge(2 * i, T, r[i], 0); if (i < N - 1) { MM.addedge(2 * i + 1, 2 * i + 3, INF, 0); } if (i + m < N) { MM.addedge(2 * i + 1, 2 * i + 2 * m, INF, f); } if (i + n < N) { MM.addedge(2 * i + 1, 2 * i + 2 * n, INF, s); } } int flow = 0; cout << MM.go() << endl; return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint maxn = 1e5 + 10; int a[100][100]; int n, m; structE { int from, to, cp, v; int rev; E() {} E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {} }; structMCMF { int n, m, s, t; vector<E> edges; vector<int> G[maxn]; bool inq[maxn]; //是否在队列 int d[maxn]; //Bellman_ford单源最短路径 int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号 int a[maxn]; //a[i]表示从s到i的最小残量 voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); m = 0; }
voidaddedge(int from, int to, int cap, int cost){ edges.push_back(E(from, to, cap, cost, 0)); edges.push_back(E(to, from, 0, -cost, 1)); G[from].push_back(m++); G[to].push_back(m++); }
boolBellmanFord(int &flow, int &cost){ for (int i = 0; i < n; i++) d[i] = INF; memset(inq, 0, sizeof inq); d[s] = 0, a[s] = INF, inq[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int& idx : G[u]) { E &e = edges[idx]; if (e.cp && d[e.to] > d[u] + e.v) { d[e.to] = d[u] + e.v; p[e.to] = idx; a[e.to] = min(a[u], e.cp); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; } } } } if (d[t] == INF) returnfalse; flow += a[t]; cost += a[t] * d[t]; int u = t; while (u != s) { edges[p[u]].cp -= a[t]; edges[p[u] ^ 1].cp += a[t]; u = edges[p[u]].from; } returntrue; }
pii go(){ int flow = 0, cost = 0; while (BellmanFord(flow, cost)); returnpii(cost, flow); } } MM; int S, T; int sum[30]; intxy2k(int x, int y){ if (x == 0)return y; return sum[x - 1] + y; } intmain(){ scanf("%d%d", &m, &n); sum[0] = m; for (int i = 1; i < n; i++)sum[i] = sum[i - 1] + 1; for (int i = 1; i < n; i++)sum[i] += sum[i - 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < m + i; j++) { scanf("%d", &a[i][j]); } } int tot = (2 * m + n - 1)*n / 2; int N = 2 * tot + 2; S = N - 2; T = N - 1; MM.init(N, S, T); for (int i = 0; i < n; i++) { for (int j = 0; j < m + i; j++) { int id = xy2k(i, j); MM.addedge(id, id + tot, 1, -a[i][j]); if (i == n - 1)continue; MM.addedge(id + tot, xy2k(i + 1, j), 1, 0); MM.addedge(id + tot, xy2k(i + 1, j + 1), 1, 0); } } for (int i = 0; i < m; i++) { MM.addedge(S, i, 1, 0); } for (int i = 0; i < m + n - 1; i++) { MM.addedge(xy2k(n - 1, i)+tot, T, 1, 0); } cout << -MM.go().first << endl; S = tot, T = tot + 1; MM.init(tot + 2, S, T); for (int i = 0; i < m; i++) { MM.addedge(S, i, 1, -a[0][i]); } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m + i; j++) { int id = xy2k(i, j); MM.addedge(id, xy2k(i + 1, j),1,-a[i+1][j]); MM.addedge(id, xy2k(i + 1, j + 1), 1, -a[i + 1][j + 1]); } } for (int i = 0; i < m + n - 1; i++) { MM.addedge(xy2k(n - 1, i), T, INF, 0); } cout << -MM.go().first << endl; MM.init(tot + 2, S, T); for (int i = 0; i < m; i++) { MM.addedge(S, i, 1, -a[0][i]); } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m + i; j++) { int id = xy2k(i, j); MM.addedge(id, xy2k(i + 1, j), INF, -a[i + 1][j]); MM.addedge(id, xy2k(i + 1, j + 1), INF, -a[i + 1][j + 1]); } } for (int i = 0; i < m + n - 1; i++) { MM.addedge(xy2k(n - 1, i), T, INF, 0); } cout << -MM.go().first << endl; return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint maxn = 1e5 + 10; constint INF = 0x3f3f3f3f; structmxfl { int n = 0; int m = 0; int s, t; structEdge { int from, to, cap, flow; }; vector<Edge>edges; vector<int>G[maxn]; voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; edges.clear(); for (int i = 0; i < n; i++)G[i].clear(); } voidadd_edge(int from, int to, int cap){ edges.push_back(Edge{ from,to,cap,0 }); edges.push_back(Edge{ to,from,0,0 }); m = (int)edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool vis[maxn]; int d[maxn], cur[maxn]; boolbfs(){ memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } intdfs(int x, int a){ if (x == t || a == 0)return a; int flow = 0, f; for (int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0)break; } } return flow; } intmaxflow(){ int flow = 0; while (bfs()) { memset(cur, 0, sizeof(cur)); flow += dfs(s, INF); } return flow; } }MF;
int n, m; intxy2k(int x, int y){ return x * m + y; } boolleg(int x, int y){ return x >= 0 && x < n&&y >= 0 && y < m; } int mz[110][110]; int dx[]{ -1,1,0,0 }; int dy[]{ 0,0,-1,1 }; int ans; intmain(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &mz[i][j]); ans += mz[i][j]; } } int s = n * m, t = n * m + 1; MF.init(n*m + 2, s, t); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int id = xy2k(i, j); if ((i+j) & 1)MF.add_edge(id, t, mz[i][j]); else { MF.add_edge(s, id, mz[i][j]); for (int k = 0; k < 4; k++) { int nx = i + dx[k], ny = j + dy[k]; if (leg(nx, ny)) { MF.add_edge(id, xy2k(nx, ny), INF); } } } } } printf("%d\n", ans - MF.maxflow()); return0; }
structmxfl { int n = 0; int m = 0; int s, t; structEdge { int from, to, cap, flow; }; vector<Edge>edges; vector<int>G[maxn]; voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; edges.clear(); for (int i = 0; i < n; i++)G[i].clear(); } voidadd_edge(int from, int to, int cap){ edges.push_back(Edge{ from,to,cap,0 }); edges.push_back(Edge{ to,from,0,0 }); m = (int)edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool vis[maxn]; int d[maxn], cur[maxn]; boolbfs(){ memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } intdfs(int x, int a){ if (x == t || a == 0)return a; int flow = 0, f; for (int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0)break; } } return flow; } intmaxflow(){ int flow = 0; while (bfs()) { memset(cur, 0, sizeof(cur)); flow += dfs(s, INF); } return flow; } }MF;
int n, m, k, N; int H[maxn], r[maxn]; vector<int>vc[maxn]; int pre = 0; boolcheck(int t){ for (int i = 0; i < N; i++) { MF.add_edge(i + (t - 1)*N, i + t * N, INF); } for (int i = 0; i < m; i++) { int u = vc[i][(t - 1 + r[i]) % r[i]], v = vc[i][t%r[i]]; MF.add_edge(u + (t - 1)*N, v + t * N, H[i]); } MF.s = 0, MF.t = N * t + (N - 1); int nw = MF.maxflow(); if (pre + nw >= k)returntrue; pre += nw; returnfalse; }
intmain(){ scanf("%d%d%d", &n, &m, &k); N = n + 2; for (int i = 0; i < m; i++) { scanf("%d", &H[i]); scanf("%d", &r[i]); for (int j = 0; j < r[i]; j++) { int x; scanf("%d", &x); if (x == -1)x = N - 1; vc[i].push_back(x); } } for (int t = 1; t <= 100; t++) { if (check(t)) { printf("%d\n", t); return0; } } printf("0\n"); return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint maxn = 1e5 + 10; constint INF = 0x3f3f3f3f; int K = 2; structE { int from, to, cp, v; int rev; E() {} E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {} }; structMCMF { int n, m, s, t; vector<E> edges; vector<int> G[maxn]; bool inq[maxn]; //是否在队列 int d[maxn]; //Bellman_ford单源最短路径 int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号 int a[maxn]; //a[i]表示从s到i的最小残量 voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); m = 0; }
voidaddedge(int from, int to, int cap, int cost){ edges.push_back(E(from, to, cap, cost, 0)); edges.push_back(E(to, from, 0, -cost, 1)); G[from].push_back(m++); G[to].push_back(m++); }
boolBellmanFord(int &flow, int &cost){ for (int i = 0; i < n; i++) d[i] = INF; memset(inq, 0, sizeof inq); d[s] = 0, a[s] = INF, inq[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int& idx : G[u]) { E &e = edges[idx]; if (e.cp && d[e.to] > d[u] + e.v) { d[e.to] = d[u] + e.v; p[e.to] = idx; a[e.to] = min(a[u], e.cp); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; } } } } if (d[t] == INF) returnfalse; if (flow + a[t] > K)a[t] = K - flow; flow += a[t]; cost += a[t] * d[t]; int u = t; while (u != s) { edges[p[u]].cp -= a[t]; edges[p[u] ^ 1].cp += a[t]; u = edges[p[u]].from; } if (flow == K)returnfalse; returntrue; }
pii go(){ int flow = 0, cost = 0; while (BellmanFord(flow, cost)); returnpii(flow, cost); } } MM; int n, m; string mz[110]; map<string, int>mp; queue<int>q; voidpr(int u){ q.push(u/2); for (int i : MM.G[u+1]) { if (MM.edges[i].rev)continue; if (MM.edges[i ^ 1].cp > 0) { MM.edges[i ^ 1].cp--; pr(MM.edges[i].to); break; } } } stack<int>st; voidpr1(int u){ st.push(u / 2); for (int i : MM.G[u + 1]) { if (MM.edges[i].rev)continue; if (MM.edges[i ^ 1].cp > 0) { MM.edges[i ^ 1].cp--; pr1(MM.edges[i].to); } } } intmain(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { cin >> mz[i]; mp[mz[i]] = i; } int S = 0, T = 2 * n - 1; MM.init(2 * n, S, T); for (int i = 0; i < m; i++) { string u, v; cin >> u >> v; int p = mp[u], q = mp[v]; if (p > q)swap(p, q); MM.addedge(p * 2 + 1, q * 2, INF, -1); } for (int i = 1; i < n - 1; i++) { MM.addedge(i * 2, i * 2 + 1, 1, 0); } MM.addedge(0, 1, 2, 0); MM.addedge(2 * n - 2, 2 * n - 1, 2, 0); pii ans = MM.go(); if (ans.first < 2) { cout << "No Solution!" << endl; return0; } cout << -ans.second << endl; pr(0); while (!q.empty()) { cout << mz[q.front()] << endl; q.pop(); } pr1(0); st.pop(); while (!st.empty()) { cout << mz[st.top()] << endl; st.pop(); } return0; }
structmxfl { int n = 0; int m = 0; int s, t; structEdge { int from, to, cap, flow; }; vector<Edge>edges; vector<int>G[maxn]; voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; edges.clear(); for (int i = 0; i < n; i++)G[i].clear(); } voidadd_edge(int from, int to, int cap){ edges.push_back(Edge{ from,to,cap,0 }); edges.push_back(Edge{ to,from,0,0 }); m = (int)edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool vis[maxn]; int d[maxn], cur[maxn]; boolbfs(){ memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } intdfs(int x, int a){ if (x == t || a == 0)return a; int flow = 0, f; for (int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0)break; } } return flow; } intmaxflow(){ int flow = 0; while (bfs()) { memset(cur, 0, sizeof(cur)); flow += dfs(s, INF); } return flow; } }MF; int n, m; int sum; intmain(){ scanf("%d%d", &n, &m); int S = 0, T = n + m + 1; MF.init(n + m + 2, S, T); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); sum += x; MF.add_edge(S, i, x); char tools[10000]; memset(tools, 0, sizeof tools); cin.getline(tools, 10000); int ulen = 0, tool; while (sscanf(tools + ulen, "%d", &tool) == 1)//之前已经用scanf读完了赞助商同意支付该实验的费用 {//tool是该实验所需仪器的其中一个 MF.add_edge(i, tool + n, INF); if (tool == 0) ulen++; else { while (tool) { tool /= 10; ulen++; } } ulen++; } } for (int i = 1; i <= m; i++) { int x; scanf("%d", &x); MF.add_edge(i + n, T, x); } int res = sum - MF.maxflow(); for (int i = 1; i <= n; i++)if (MF.vis[i])printf("%d ", i); printf("\n"); for (int i = 1; i <= m; i++)if (MF.vis[i + n])printf("%d ", i); printf("\n"); printf("%d\n", res); return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint maxn = 100 + 10; constint INF = 0x3f3f3f3f; structE { int from, to, cp, v; int rev; E() {} E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {} }; structMCMF { int n, m, s, t; vector<E> edges; vector<int> G[maxn]; bool inq[maxn]; //是否在队列 int d[maxn]; //Bellman_ford单源最短路径 int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号 int a[maxn]; //a[i]表示从s到i的最小残量 voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); m = 0; }
voidaddedge(int from, int to, int cap, int cost){ edges.push_back(E(from, to, cap, cost, 0)); edges.push_back(E(to, from, 0, -cost, 1)); G[from].push_back(m++); G[to].push_back(m++); }
boolBellmanFord(int &flow, int &cost){ for (int i = 0; i < n; i++) d[i] = INF; memset(inq, 0, sizeof inq); d[s] = 0, a[s] = INF, inq[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int& idx : G[u]) { E &e = edges[idx]; if (e.cp && d[e.to] > d[u] + e.v) { d[e.to] = d[u] + e.v; p[e.to] = idx; a[e.to] = min(a[u], e.cp); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; } } } } if (d[t] == INF) returnfalse; //if (flow + a[t] > K)a[t] = K - flow;//固定流量 flow += a[t]; cost += a[t] * d[t]; int u = t; while (u != s) { edges[p[u]].cp -= a[t]; edges[p[u] ^ 1].cp += a[t]; u = edges[p[u]].from; } //if (flow == K)return false;//固定流量 returntrue; }
pii go(){ int flow = 0, cost = 0; while (BellmanFord(flow, cost)); returnpii(flow, cost); } } MM; int n, m; int a[maxn], b[maxn], co[maxn][maxn]; voidsolve(int x){ int S = 0, T = n + m + 1; MM.init(n + m + 2, S, T); for (int i = 1; i <= n; i++) { int x = a[i]; MM.addedge(S, i, x, 0); } for (int i = 1; i <= m; i++) { int x = b[i]; MM.addedge(i + n, T, x, 0); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int w = co[i][j]; MM.addedge(i, j + n, INF, w*x); } } printf("%d\n", x*MM.go().second); } intmain(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)scanf("%d", &a[i]); for (int i = 1; i <= m; i++)scanf("%d", &b[i]); for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) scanf("%d", &co[i][j]); solve(1); solve(-1); return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint maxn = 100 + 10; constint INF = 0x3f3f3f3f; structE { int from, to, cp, v; int rev; E() {} E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {} }; structMCMF { int n, m, s, t; vector<E> edges; vector<int> G[maxn]; bool inq[maxn]; //是否在队列 int d[maxn]; //Bellman_ford单源最短路径 int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号 int a[maxn]; //a[i]表示从s到i的最小残量 voidinit(int _n, int _s, int_t){ n = _n; s = _s; t = _t; for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); m = 0; }
voidaddedge(int from, int to, int cap, int cost){ edges.push_back(E(from, to, cap, cost, 0)); edges.push_back(E(to, from, 0, -cost, 1)); G[from].push_back(m++); G[to].push_back(m++); }
boolBellmanFord(int &flow, int &cost){ for (int i = 0; i < n; i++) d[i] = INF; memset(inq, 0, sizeof inq); d[s] = 0, a[s] = INF, inq[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int& idx : G[u]) { E &e = edges[idx]; if (e.cp && d[e.to] > d[u] + e.v) { d[e.to] = d[u] + e.v; p[e.to] = idx; a[e.to] = min(a[u], e.cp); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; } } } } if (d[t] == INF) returnfalse; //if (flow + a[t] > K)a[t] = K - flow;//固定流量 flow += a[t]; cost += a[t] * d[t]; int u = t; while (u != s) { edges[p[u]].cp -= a[t]; edges[p[u] ^ 1].cp += a[t]; u = edges[p[u]].from; } //if (flow == K)return false;//固定流量 returntrue; }
pii go(){ int flow = 0, cost = 0; while (BellmanFord(flow, cost)); returnpii(flow, cost); } } MM; int n; int ave, a[maxn]; intmain(){ scanf("%d", &n); int S = 0, T = n + 1; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); ave += a[i]; } ave /= n; MM.init(n + 2, S, T); for (int i = 1; i <= n; i++) { MM.addedge(S, i, a[i], 0); MM.addedge(i, i%n + 1, INF, 1); MM.addedge(i, (i - 2 + n) % n + 1, INF, 1); MM.addedge(i, T, ave, 0); } cout << MM.go().second << endl; return0; }
int depth[MAXN], gap[MAXN], cur[MAXN]; int n, m; bool vis[MAXN];
voidbfs(int s, int t){ memset(depth, 0, sizeof(depth)); memset(gap, 0, sizeof(depth)); queue<int> que; que.push(t); depth[t] = 1; gap[1] = 1; while (!que.empty()) { int now = que.front(); que.pop(); for (int i = A.head[now]; i; i = A.edge[i].nxt) { int v = A.edge[i].ed; if (depth[v]) continue; que.push(v); depth[v] = depth[now] + 1; ++gap[depth[v]]; } } }
intdfs(int now, int flow, int s, int t){ if (now == t) return flow; int used = 0; for (int i = cur[now]; i; i = A.edge[i].nxt) { cur[now] = i; int v = A.edge[i].ed; if (A.edge[i].flow && depth[v] + 1 == depth[now]) { int change = dfs(v, min(flow - used, A.edge[i].flow), s, t); A.edge[i].flow -= change; A.edge[i ^ 1].flow += change; used += change; } if (used == flow) return used; } --gap[depth[now]]; if (!gap[depth[now]]) depth[s] = (n << 1) + 1; ++depth[now]; ++gap[depth[now]]; return used; }
intISAP(int s, int t){ bfs(s, t); int ans = 0; while (depth[s] <= (n << 1)) { memcpy(cur, A.head, sizeof(A.head)); ans += dfs(s, INF, s, t); } return ans; }
voidprint(int now, int s, int t){ printf("%d ", now); for (int i = A.head[now]; i; i = A.edge[i].nxt) { if (A.edge[i].flow || A.edge[i].ed == s || A.edge[i].ed == now + n) continue;//这里要注意的是不要把边连回自己 print(A.edge[i].ed - n, s, t);//下一个点应从xi出发搜索,所以要减n return; } }
intmain(){ memset(vis, false, sizeof(vis)); int x, y, s, t, ans; scanf("%d%d", &n, &m); s = 2 * n + 5, t = s + 1, ans = n; for (int i = 1; i <= n; ++i) { A.insert(s, i, 1); A.insert(i + n, t, 1); } for (int i = 1; i <= m; ++i) { scanf("%d%d", &x, &y); A.insert(x, y + n, 1); } ans -= ISAP(s, t); for (int i = 1; i <= n; ++i) { bool flag = false; for (int j = A.head[i + n]; j; j = A.edge[j].nxt) //查找yi if (A.edge[j].flow && A.edge[j].ed != i && A.edge[j].ed != t) { flag = true; break; } if (!flag) { print(i, s, t);//递归输出 printf("\n"); } } printf("%d\n", ans); return0; }