想做的时候随时更新吧 前几道都是水题 呃呃呃呃
|
问题编号 |
问题名称 |
问题模型 |
转化模型 |
|
1 |
飞行员配对方案问题 |
二分图最大匹配 |
网络最大流 |
|
2 |
太空飞行计划问题 |
最大权闭合图 |
网络最小割 |
|
3 |
最小路径覆盖问题 |
有向无环图最小路径覆盖 |
网络最大流 |
|
4 |
魔术球问题 |
有向无环图最小路径覆盖 |
网络最大流 |
|
5 |
圆桌问题 |
二分图多重匹配 |
网络最大流 |
|
6 |
最长递增子序列问题 |
最多不相交路径 |
网络最大流 |
|
7 |
试题库问题 |
二分图多重匹配 |
网络最大流 |
|
8 |
机器人路径规划问题 |
(未解决) |
最小费用最大流 |
|
9 |
方格取数问题 |
二分图点权最大独立集 |
网络最小割 |
|
10 |
餐巾计划问题 |
线性规划网络优化 |
最小费用最大流 |
|
11 |
航空路线问题 |
最长不相交路径 |
最小费用最大流 |
|
12 |
软件补丁问题 |
最小转移代价 |
最短路径 |
|
13 |
星际转移问题 |
网络判定 |
网络最大流 |
|
14 |
孤岛营救问题 |
分层图最短路径 |
最短路径 |
|
15 |
汽车加油行驶问题 |
分层图最短路径 |
最短路径 |
|
16 |
数字梯形问题 |
最大权不相交路径 |
最小费用最大流 |
|
17 |
运输问题 |
网络费用流量 |
最小费用最大流 |
|
18 |
分配问题 |
二分图最佳匹配 |
最小费用最大流 |
|
19 |
负载平衡问题 |
最小代价供求 |
最小费用最大流 |
|
20 |
深海机器人问题 |
线性规划网络优化 |
最小费用最大流 |
|
21 |
最长k可重区间集问题 |
最大权不相交路径 |
最小费用最大流 |
|
22 |
最长k可重线段集问题 |
最大权不相交路径 |
最小费用最大流 |
|
23 |
火星探险问题 |
线性规划网络优化 |
最小费用最大流 |
|
24 |
骑士共存问题 |
二分图最大独立集 |
网络最小割 |
1
太水了 不写了
2
显然也是水题 but 输出方案get了
判断d[i]即可
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 1e5 + 10, INF = 0x7fffffff; int n, m, s, t; vector<int> g, f, h; int head[maxn], cur[maxn], vis[maxn], d[maxn], cnt, nex[maxn << 1]; struct node { int u, v, c; }Node[maxn << 1]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; nex[cnt] = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u, v, c); add_(v, u, 0); } bool bfs() { queue<int> Q; mem(d, 0); Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(!d[v] && Node[i].c > 0) { d[v] = d[u] + 1; Q.push(v); if(v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { int ret = 0; if(u == t || cap == 0) return cap; for(int &i = cur[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] == d[u] + 1 && Node[i].c > 0) { int V = dfs(v, min(cap, Node[i].c)); Node[i].c -= V; Node[i ^ 1].c += V; ret += V; cap -= V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret; } int Dinic() { int ans = 0; while(bfs()) { memcpy(cur, head, sizeof head); ans += dfs(s, INF); } return ans; } int main() { scanf("%d%d", &n, &m); mem(head, -1); cnt = 0; g.clear(); f.clear(), h.clear(); s = 0, t = n + m + 1; int sum = 0; int u, v, w; rap(i, 1, n) { rd(w); g.push_back(cnt); add(s, i, w); sum += w; int x; char ch; while(1) //输入一行 遇到回车结束 { scanf("%d%c", &x, &ch); add(i, n + x, INF); if(ch == ' ' || ch == ' ') break; } } rap(i, 1, m) { f.push_back(cnt); rd(w); add(n + i, t, w); } // cout << 111 << endl; sum -= Dinic(); // for(int i = 0; i < g.size(); i++) // { // if(i != 0) cout << " "; // if(Node[g[i]].c > 0) // cout << Node[g[i]].v; // } // cout << endl; // for(int i = 0; i < f.size(); i++) // { // if(Node[f[i]].c == 0) // h.push_back(Node[f[i]].u - n); // } // h.erase(unique(h.begin(), h.end()), h.end()); // for(int i = 0; i < h.size(); i++) // { // if(i != 0) cout << " "; // cout << h[i]; // // } rap(i, 1, n) { if(d[i]) cout << i << " "; } cout << endl; rap(i, 1, m) { if(d[i + n]) cout << i << " "; } cout << endl << sum << endl; return 0; }
3 最小路径覆盖
有向无环图！！无环！！无环！！
拆点建边就好了
关键是输出路径
遍历n个点u，然后for(int i = head[u]; i != -1; i = nex[i]) 遍历每个点的子代，用to[u]记录当前点的下一个点 vis[v] = 1标记点 目的是：当某个点的vis[i]值为0时，则这个点就是起点 输出的时候从起点开始 for(int j = i; j; j = to[j]) 输出即可
这部分代码如下：
rap(u, 1, n) for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(Node[i].c == 0 && !vis[v - n] && v) to[u] = v - n, vis[v - n] = 1; } rap(i, 1, n) { if(!vis[i]) { for(int j = i; j; j = to[j]) cout << j << " "; cout << endl; } }
完整代码：
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 1e5 + 10, INF = 0x7fffffff; int n, m, s, t; int head[maxn], cur[maxn], vis[maxn], d[maxn], cnt, nex[maxn << 1]; int to[maxn]; struct node { int u, v, c; }Node[maxn << 1]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; nex[cnt] = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u, v, c); add_(v, u, 0); } bool bfs() { queue<int> Q; mem(d, 0); Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(!d[v] && Node[i].c > 0) { d[v] = d[u] + 1; Q.push(v); if(v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { int ret = 0; if(u == t || cap == 0) return cap; for(int &i = cur[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] == d[u] + 1 && Node[i].c > 0) { int V = dfs(v, min(cap, Node[i].c)); Node[i].c -= V; Node[i ^ 1].c += V; ret += V; cap -= V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret; } int Dinic() { int ans = 0; while(bfs()) { memcpy(cur, head, sizeof head); ans += dfs(s, INF); } return ans; } int main() { int u, v; mem(head, -1); cnt = 0; rd(n), rd(m); s = 0, t = n * 2 + 1; rap(i, 1, m) { rd(u), rd(v); add(u, n + v, 1); } rap(i, 1, n) add(s, i, 1), add(n + i, t, 1); int ans = Dinic(); rap(u, 1, n) for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(Node[i].c == 0 && !vis[v - n] && v) to[u] = v - n, vis[v - n] = 1; } rap(i, 1, n) { if(!vis[i]) { for(int j = i; j; j = to[j]) cout << j << " "; cout << endl; } } cout << n - ans << endl; return 0; }
4 魔术球
两个球如果能放在一起（和为完全平方数）那么就将他们之间连一条从小编号指向大编号的有向边，如此一来，每根柱子可以看做是这个途中的一条路径，而用最小路径覆盖就可以求出最少需要的柱子数量。那么我们从小到大枚举N，一旦最小路径覆盖数大于n，那么N-1就是答案。
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 1e4 + 10, INF = 0x7fffffff, N = 5000 + 10; int n, m, s, t, k; bool is_sq[maxn]; int head[maxn], cur[maxn], d[maxn], nex[maxn * 20], to[maxn], vis[maxn]; int cnt; struct node { int u, v, c; }Node[maxn * 20]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; nex[cnt] = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u, v, c); add_(v, u, 0); } bool bfs() { queue<int> Q; mem(d, 0); Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(!d[v] && Node[i].c > 0) { d[v] = d[u] + 1; Q.push(v); if(v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { int ret = 0; if(u == t || cap == 0) return cap; for(int &i = cur[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] == d[u] + 1 && Node[i].c > 0) { int V = dfs(v, min(Node[i].c, cap)); Node[i].c -= V; Node[i ^ 1].c += V; ret += V; cap -= V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret; } int Dinic() { int ans = 0; while(bfs()) { memcpy(cur, head, sizeof head); ans += dfs(s, INF); } return ans; } int main() { for(int i = 1; i * i <= 5000; i++) is_sq[i * i] = 1; int ans = 0, ans1 = 0; rd(n); s = 0, t = maxn - 10; mem(head, -1); cnt = 0; while(1) { ans++, ans1++; for(int i = 1; i < ans; i++) if(is_sq[i + ans]) add(i, N + ans, 1); add(s, ans, 1); add(N + ans, t, 1); // cout << 222 << endl; ans1 -= Dinic(); if(ans1 > n) break; // cout << 111111 << endl; } pd(ans - 1); ans--; for(int u = 1; u < ans; u++) for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(Node[i].c == 0 && !vis[v - N] && v) to[u] = v - N, vis[v - N] = 1; } rap(i, 1, ans) { if(!vis[i]) { for(int j = i; j; j = to[j]) printf("%d ", j); printf(" "); } } }
5 圆桌问题
就是多重匹配 输出每个的选择方案
输出方案 用dfs去搜一下 就是对于当前左边的点 如果选择了右边的点 那么Node[i].c == 0 二维vis标记一下即可
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 1e5 + 10, INF = 0x7fffffff; int n, m, s, t; vector<int> g[maxn], f[maxn]; int head[maxn], cur[maxn], vis[400][400], d[maxn], cnt, nex[maxn << 1]; struct node { int u, v, c; }Node[maxn << 1]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; nex[cnt] = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u, v, c); add_(v, u, 0); } bool bfs() { queue<int> Q; mem(d, 0); Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(!d[v] && Node[i].c > 0) { d[v] = d[u] + 1; Q.push(v); if(v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { int ret = 0; if(u == t || cap == 0) return cap; for(int &i = cur[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] == d[u] + 1 && Node[i].c > 0) { int V = dfs(v, min(cap, Node[i].c)); // g[u].push_back(v); Node[i].c -= V; Node[i ^ 1].c += V; ret += V; cap -= V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret; } int Dinic() { int ans = 0; while(bfs()) { //cout << 1111 << endl; memcpy(cur, head, sizeof head); ans += dfs(s, INF); } return ans; } void dfs1(int u) { // vis[u] = 1; for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(Node[i].c == 0 && !vis[u][v]) { g[u].push_back(v); vis[u][v] = 1; dfs1(v); } } } int main() { int tmp; mem(head, -1); cnt = 0; rd(n), rd(m); s = 0, t = n + m + 1; int sum = 0; rap(i, 1, n) { rd(tmp); sum += tmp; add(s, i, tmp); rap(j, 1, m) add(i, n + j, 1); } rap(i, 1, m) { rd(tmp); add(n + i, t, tmp); } int ans = Dinic(); if(ans == sum) { pd(1); dfs1(s); rap(i, 1, n) { for(int j = 0; j < g[i].size(); j++) { cout << g[i][j] - n << " "; } cout << endl; } } else pd(0); return 0; }
6 最长递增子序列问题
本地对了就是对了 oj错了说明oj有问题
这题其实是不下降
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define pd(a) printf("%d ", a); #define plld(a) printf("%lld ", a); #define pc(a) printf("%c ", a); #define ps(a) printf("%s ", a); #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 22222, INF = 1e9, LL_INF = 0x7ffffffffffffff, maxm = 1e6; int s, t, n, m; int dp[maxn], num[maxn]; int head[maxn], cur[maxn], d[maxn], cnt; struct node { int u, v, c, next; }Node[maxm << 1]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; Node[cnt].next = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u, v, c); add_(v, u, 0); } bool bfs() { mem(d, 0); queue<int> Q; Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = Node[i].next) { node e = Node[i]; if(!d[e.v] && e.c > 0) { d[e.v] = d[u] + 1; Q.push(e.v); if(e.v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { int ret = 0; if(u == t || cap == 0) return cap; for(int &i = cur[u]; i != -1; i = Node[i].next) { node e = Node[i]; if(d[e.v] == d[u] + 1 && e.c > 0) { int V = dfs(e.v, min(e.c, cap)); Node[i].c -= V; Node[i ^ 1].c += V; ret += V; cap -= V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret; } int Dinic() { int ans = 0; while(bfs()) { memcpy(cur, head, sizeof(head)); ans += dfs(s, INF); } return ans; } int main() { scanf("%d", &n); mem(head, -1); cnt = 0; s = 0, t = n * 2 + 1; mem(dp, 0); int max_len = -INF; for(int i = 1; i <= n; i++) { rd(num[i]); dp[i] = 1; for(int j = 1; j < i; j++) if(num[j] <= num[i] && dp[j] + 1 >= dp[i]) dp[i] = dp[j] + 1; max_len = max(max_len, dp[i]); } for(int i = 1; i <= n; i++) { add(i, i + n, 1); if(dp[i] == 1) add(s, i, 1); if(dp[i] == max_len) add(i + n, t, 1); for(int j = i + 1; j <= n; j++) { if(num[j] >= num[i] && dp[i] + 1 == dp[j]) add(i + n, j, 1); } } cout << max_len << endl; cout << Dinic() << endl; mem(head, -1); cnt = 0; for(int i = 1; i <= n; i++) { if(i == 1 || i == n) add(i, i + n, INF); else add(i, i + n, 1); if(dp[i] == 1) { if(i == 1 || i == n) add(s, i, INF); else add(s, i, 1); } if(dp[i] == max_len) { if(i == 1 || i == n) add(i + n, t, INF); else add(i + n, t, 1); } for(int j = i + 1; j <= n; j++) { if(num[j] >= num[i] && dp[i] + 1 == dp[j]) add(i + n, j, 1); } } cout << Dinic() << endl; return 0; }
7 试题库问题
呃呃呃呃 水题输出方案一道
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) using namespace std; const int maxn = 1e4 + 10, INF = 0x7fffffff; int n, m, s, t; vector<int> g[maxn]; int head[maxn], cur[maxn],vis[1500][1500], d[maxn], cnt, nex[maxn << 1], vv[2000]; struct node { int u, v, c; }Node[maxn << 1]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; nex[cnt] = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u, v, c); add_(v, u, 0); } bool bfs() { queue<int> Q; mem(d, 0); Q.push(s); d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(!d[v] && Node[i].c > 0) { d[v] = d[u] + 1; Q.push(v); if(v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { int ret = 0; if(u == t || cap == 0) return cap; for(int &i = cur[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] == d[u] + 1 && Node[i].c > 0) { int V = dfs(v, min(cap, Node[i].c)); Node[i].c -= V; Node[i ^ 1].c += V; ret += V; cap -= V; if(cap == 0) break; } } if(cap > 0) d[u] = -1; return ret; } int Dinic() { int ans = 0; while(bfs()) { memcpy(cur, head, sizeof head); ans += dfs(s, INF); } return ans; } void dfs1(int u) { for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(u == s) dfs1(v); else { if(Node[i].c == 0 && !vv[u]) { vv[u] = 1; vv[u] = 1, g[v].push_back(u); dfs1(v); } } } } int main() { int tmp, p; scanf("%d%d", &n, &m); int sum = 0; mem(head, -1); mem(vis, 0); mem(vv, 0); cnt = 0; s = 0, t = n + m + 1; rap(i, 1, n) { rd(tmp); sum += tmp; add(i, t, tmp); } rap(i, 1, m) { rd(p); add(s, n + i, 1); rap(j, 1, p) { rd(tmp); add(n + i, tmp, 1); } } if(sum == Dinic()) { dfs1(s); rap(i, 1, n) { cout << i << ": "; for(int j = 0; j < g[i].size(); j++) { if(j != 0) cout << " "; cout << g[i][j] - n; } cout << endl; } } else ps("No Solution!"); return 0; }
10 餐巾计划问题
这题海星
注意最小费用最大流是在保证最大流的基础上的最小流
所以不能直接 线性连边
add(s, i, 0, tmp) 代表第i天用了多少餐巾
add(s, i + n, pp, tmp) add(i + n, t, 0, INF) 代表第i天直接买
而 i - i + n 不连边 这样就能保证最小费用 且还能满足满流
add(i, i + m1 + n, 0, INF) add(i, i + m2 + n, 0, INF) 分别代表A和B洗了之后
用add(i, i + 1, 0, INF) 代表用完保留
不能直接向后循环连边 会爆
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d
", a)
#define plld(a) printf("%lld
", a)
#define pc(a) printf("%c
", a)
#define ps(a) printf("%s
", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 1e5 + 10, INF = 0x7fffffff, N = 5000 + 10;
int n, m, s, t, k;
int pp, m1, f1, m2, f2;
int head[maxn], d[maxn], vis[maxn], nex[maxn << 1], f[maxn], p[maxn], cnt;
int xu[maxn], flow, value;
struct node
{
int u, v, w, c;
}Node[maxn << 1];
void add_(int u, int v, int w, int c)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].w = w;
Node[cnt].c = c;
nex[cnt] = head[u];
head[u] = cnt++;
}
void add(int u, int v, int w, int c)
{
add_(u, v, w, c);
add_(v, u, -w, 0);
}
int spfa()
{
for(int i = 0; i < maxn; i++) d[i] = INF;
deque<int> Q;
mem(vis, 0);
mem(p, -1);
Q.push_front(s);
d[s] = 0;
p[s] = 0, f[s] = INF;
while(!Q.empty())
{
int u = Q.front(); Q.pop_front();
vis[u] = 0;
for(int i = head[u];i != -1; i = nex[i])
{
int v = Node[i].v;
// cout << v << endl;
if(Node[i].c)
{
if(d[v] > d[u] + Node[i].w)
{
d[v] = d[u] + Node[i].w;
p[v] = i;
f[v] = min(f[u], Node[i].c);
if(!vis[v])
{
// cout << v << endl;
if(Q.empty()) Q.push_front(v);
else
{
if(d[v] < d[Q.front()]) Q.push_front(v);
else Q.push_back(v);
}
vis[v] = 1;
}
}
}
}
}
if(p[t] == -1) return 0;
// cout << 111 << endl;
flow += f[t], value += f[t] * d[t];
// cout << value << endl;
for(int i = t; i != s; i = Node[p[i]].u)
{
Node[p[i]].c -= f[t];
Node[p[i] ^ 1].c += f[t];
}
return 1;
}
void max_flow()
{
flow = value = 0;
while(spfa());
pd(value);
}
void init()
{
mem(head, -1);
cnt = 0;
}
int main()
{
init();
int tmp;
rd(n), rd(pp), rd(m1), rd(f1), rd(m2), rd(f2);
s = 0, t = 2 * n + 1;
// ss = 2 * n + 11;
rap(i, 1, n)
{
rd(tmp);
add(s, i, 0, tmp);
add(s, i + n, pp, tmp);
add(n + i, t, 0, tmp);
// for(int j = i + m1; j <= n && j + n <= 2 * n; j++)
// add(i, j + n, f1, INF);
// for(int j = i + m2; j <= n && j + n <= 2 * n; j++)
// add(i, j + n, f2, INF);
if(i < n)
add(i, i + 1, 0, INF);
if(i + m1 <= n)
add(i, i + m1 + n, f1, INF);
if(i + m2 <= n)
add(i, i + m2 + n, f2, INF);
}
max_flow();
return 0;
}