您的位置:首页 > 娱乐 > 八卦 > 设计师分六个级别_免费网站怎么建立_关键词排名的排名优化_seo推广是什么意怿

设计师分六个级别_免费网站怎么建立_关键词排名的排名优化_seo推广是什么意怿

2024/12/22 5:32:03 来源:https://blog.csdn.net/2301_78527293/article/details/143463889  浏览:    关键词:设计师分六个级别_免费网站怎么建立_关键词排名的排名优化_seo推广是什么意怿
设计师分六个级别_免费网站怎么建立_关键词排名的排名优化_seo推广是什么意怿

最小割补充文档及相关习题

2022 年 7 月 19 日晚上 21:30 在解题十分钟直播间讲解最小割解题方法和系列例题。

直播录像在这里

注意 : 这是相关题目的链接补充及代码参考,所有涉及到思路的地方都比较粗糙,看不懂很正常。

Asteroids

3041 – Asteroids

其实这题就是 n × m n \times m n×m 棋盘问题。可以用来练习 dinic。

假设 ( x , y ) (x,y) (x,y) 需要去掉,显然同时划分到不选他们的方案是不合法的,连边 + ∞ +\infty + ,其余根据自己的建模,参考 up 的建模方式即可。

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long longconst int N = 1E3 + 10, M = 2E5 + 10;struct edge{int v, c, ne;edge() {}edge(int v, int c, int ne) : v(v), c(c), ne(ne) {}
}e[M];int n, m, S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = edge(b, c, h[a]);h[a] = idx; 
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}int x, y;void solve(){cin >> n >> m;while(m --){cin >> x >> y;add(x, y + n, 1e18);add(y + n, x, 0);}S = 0, T = 2 * n + 1;for(int i = 1; i <= n; i ++){add(S, i, 1);add(i, S, 0);add(i + n, T, 1);add(T, i + n, 0);}cout << dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}

P3231 [HNOI2013] 消毒

[HNOI2013] 消毒 - 洛谷

这是我不独立完成的一道洛谷紫题,实际就是上一题的升级版,二维转三维。

当然这题之所以可做,是因为 a × b × c ≤ 5000 a\times b \times c \leq 5000 a×b×c5000 ,也就代表着总有一维 $\leq \sqrt[3] {5000} $ , 大概是 17 数量级。

对于最小的这一维,我们暴搜怎么消毒。

关于消毒,取 min ⁡ ( x , y , z ) = 1 \min (x,y,z)=1 min(x,y,z)=1 一定是最优的,相当于每次选一个截面消毒,花费一个代价。

暴搜最小的截面之后,剩下的点,已经消毒的直接忽略,没消毒的点,相当于第一个问题了。

注意到,求这个二分图的最小割,也就是求二分图的最大流,同时也就是最大匹配。

所以为了好写代码,匈牙利跑一遍即可。

时间复杂度不会算了已经,大概是 O ( T × 2 17 × b c ) O(T\times 2^{17} \times bc) O(T×217×bc) , 因为匈牙利实际更快,所以这个复杂度应该达不到。

#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 1E4 + 10, M = 2E4 + 10;int a, b, c;
int q[4][N];
int ans, cnt = 0;int h[N], e[M], ne[M], idx = 0;void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int ok[20];
int st[N], match[N];bool find(int u){for(int i = h[u]; ~i; i = ne[i]){int v = e[i];if(!st[v]){st[v] = true;if(!match[v] || find(match[v])){match[v] = u;return true;}}}return false;
}int cal(){int res = 0;memset(h, -1, sizeof h);idx = 0;for(int i = 1; i <= cnt; i ++){if(ok[q[1][i]] == false) {add(q[2][i], q[3][i] + b);add(q[3][i] + b, q[2][i]);}}for(int j = b + 1; j <= b + c; j ++) match[j] = 0;for(int i = 1; i <= b; i ++){for(int j = b + 1; j <= b + c; j ++) st[j] = false;if(find(i)) res ++;}return res;
}void dfs(int u, int v){if(u == a + 1){ans = min(ans, cal() + v);return ;}dfs(u + 1, v);ok[u] = 1;dfs(u + 1, v + 1);ok[u] = 0;
}void solve(){cin >> a >> b >> c;cnt = 0;for(int i = 1; i <= a; i ++){for(int j = 1; j <= b; j ++){for(int k = 1; k <= c; k ++){int x;cin >> x;if(x){q[1][++ cnt] = i, q[2][cnt] = j, q[3][cnt] = k;}}}}ans = 5000;memset(ok, 0, sizeof ok);dfs(1, 0); // 正在考虑第 i 层, 已经花费代价 jcout << ans << '\n';
}signed main(){// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}

P2762 太空飞行计划问题

太空飞行计划问题 - 洛谷

就是课上所讲的设备采购问题,不得不感叹 up 主讲得很好。

其实这是一个算法,或者说是图论的一个知识点吧,叫最大权闭合子图。

闭合子图的定义是,对于有向图 G = ( V , E ) G=(V,E) G=(V,E) ,如果存在子集 S ⊆ V S \subseteq V SV , 满足闭合条件 : 对于任意两个节点 u , v ∈ V u,v\in V u,vV , 如果 u ∈ S u \in S uS 且存在边 u → v u \rightarrow v uv ,那么 v v v 也必须属于 S S S

我们给每个点一个权值,权值最大的闭合子图就是最大权闭合子图。

我们直接看这道题就可以,会了这道题,你就会发现,其实最大权闭合子图是一个很无聊的东西。

注意,按照 up 的划分方式,我们 dinic 过程中 bfs 找增广路的时候,显然最后最小割断流,因此所有 d ≠ 0 d\neq 0 d=0 的就是 S S S 集合的元素,其余都是 T T T 集合的元素。

#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 210, M = 1E4 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx; 
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}int m, n, res = 0;int atS[N], st[N];void dfs(int u){st[u] = atS[u] = 1;for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(!st[v] && e[i].c){dfs(v);}}
}// tips : initialize S, T ; for (u, v, w), add(u, v, w), add(v, u, 0)void solve(){scanf("%lld %lld", &m, &n);S = 0, T = n + m + 1;for(int i = 1; i <= m; i ++){int x, I;scanf("%lld", &x);res += x;add(n + i, T, x);add(T, n + i, 0);while(getchar() == ' '){scanf("%lld", &I);add(I, n + i, 1e18);add(n + i, I, 0);}}for(int i = 1; i <= n; i ++){int x;scanf("%lld", &x);add(S, i, x);add(i, S, 0);}int ans = res - dinic();for(int i = 1; i <= m; i ++){if(d[n + i] == 0) printf("%lld ", i);}puts("");for(int i = 1; i <= n; i ++){if(d[i] == 0) printf("%lld ", i);}printf("\n%lld", ans);
}signed main(){// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0); solve();return 0;
}
/*
void solve(){int n;scanf("%lld", &n);vector<vector<int> > vc(n + 1);for(int i = 1; i <= n; i ++){int x;scanf("%lld", &x);vc[i].push_back(x);while(getchar() == ' '){scanf("%lld", &x);vc[i].push_back(x);}}for(int i = 1; i <= n; i ++){cout << "vector: " << i << '\n';for(auto &nx : vc[i]) cout << nx << ' ';cout << '\n';}
}
*/

tips : 这是题目的读入方式,我认为这个比题面中给出的更好写

void solve(){int n;scanf("%lld", &n);vector<vector<int> > vc(n + 1);for(int i = 1; i <= n; i ++){int x;scanf("%lld", &x);vc[i].push_back(x);while(getchar() == ' '){scanf("%lld", &x);vc[i].push_back(x);}}for(int i = 1; i <= n; i ++){cout << "vector: " << i << '\n';for(auto &nx : vc[i]) cout << nx << ' ';cout << '\n';}
}

P2774 方格取数问题

方格取数问题 - 洛谷

有件事情很有意思,出现在网络流专题的网络流题目难度自动下降一个等级。

不难理解,网络流的多数题目难点首先就在于想到这题可以用网络来做,其次就是建模,建模完成之后,题目就已经结束了。

这道题目也是,其实我们把棋盘看成图的话,相邻的点连边,类似国际象棋的黑白格,这些黑白格就是一张二分图。

这道题目,我们先把所有贡献收集过来,然后用最小割分配每个点,总贡献 - 最小割就是我们最多收集到的贡献。

#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 1E4 + 10, M = 2E5 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx; 
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}
/*set N, Minitialize S, T ;for (u, v, w), add(u, v, w), add(v, u, 0)
*/  int n, m, w[110][110];int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};int cal(int x, int y){return (x - 1) * m + y;
}void add(int x, int y){for(int i = 0; i < 4; i ++){int nx = x + dx[i], ny = y + dy[i];if(nx >= 1 && nx <= n && ny >= 1 && ny <= m){add(cal(x, y), cal(nx, ny), 1e18);add(cal(nx, ny), cal(x, y), 0);}}
}void solve(){int ans = 0; cin >> n >> m;S = 0, T = n * m + 1;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){cin >> w[i][j];ans += w[i][j];}}for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){if((i + j) & 1){add(i, j);add(S, cal(i, j), w[i][j]);add(cal(i, j), S, 0);}else{add(cal(i, j), T, w[i][j]);add(T, cal(i, j), 0);}}}cout << ans - dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}

G - Grid Card Game

G - Grid Card Game

对于每个行列,都是二元选择问题,要么选,要么不选。

我们用 S 集合表示选择行但不选择列 ;用 T 集合表示选择列但不选择行。

首先先拿走全部正数代价。然后对于负数格,显然不能同时选择,于是我们队 r → c r\rightarrow c rc 连一条 + ∞ +\infty + 的边 ;对于正数格,都不选择,会放弃这个价值,从 c → r c\rightarrow r cr 连一条 x x x 的边 ;对于每个行或者列,如果选择,会扣掉所有负数代价。

用提前拿走的所有价值减掉这个图的 S-T 最小割即可。

#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 210, M = 2E5 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx; 
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}
/*set N, Minitialize S, T ;for (u, v, w), add(u, v, w), add(v, u, 0)
*/  int n, m;int a[110][110];void solve(){int res = 0;cin >> n >> m;S = 0, T = n + m + 1;for(int i = 1; i <= n; i ++){int s = 0;for(int j = 1; j <= m; j ++){cin >> a[i][j];if(a[i][j] > 0){add(n + j, i, a[i][j]);add(i, n +  j, 0);res += a[i][j];}if(a[i][j] < 0){add(i, n + j, 1e18);add(n + j, i, 0);s += -a[i][j];}}add(i, T, s);add(T, i, 0);}for(int j = 1; j <= m; j ++){int s = 0;for(int i = 1; i <= n; i ++){if(a[i][j] < 0) s += -a[i][j];}add(S, n + j, s);add(n + j, S, 0);}cout << res - dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}

E. Best Subsequence

一切源于此题 。。。。

题目的 set bits 指的数字二进制表示 1 的出现次数。

其实这道题还是不容易想到最小割来解决的。

如果能想到,首先想到,对于每个元素,当然是选择或者不选择,一般会往 DP 去想。

假设 DP 没想到做法吧,你会在思考过程中发现,对于每个数,选择他,那么他的所有二进制 1 都要选。注意题目是 bitwise OR , 我一开始看成 bitwise xor 了,正好 1 | 2 == 1 ^ 2,没太注意。

既然是按位或,对于每个数,看做点,每个位 1 ,看做点。

最多 n + 60 + 2 n+60+2 n+60+2 个点,多出来的是 S = 0 , T = n + 60 + 1 S=0,T=n+60+1 S=0,T=n+60+1

S 集合表示选数字,选二进制,T 集合相反。

不能选数字不选二进制,每个数字往他的 bit sets 连 1.

先拿走 n 个贡献,不选数字,割掉贡献,S 向 i 连 1 ;

选择位,割掉贡献,位向 T 连 1.

n - 最小割就是答案。

#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 210, M = 2E5 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx; 
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}
/*set N, Minitialize S, T ;for (u, v, w), add(u, v, w), add(v, u, 0)
*/  int n, a[110];void solve(){memset(h, 0, sizeof h);idx = 1;cin >> n;S = 0, T = n + 60 + 1;for(int i = 1; i <= n; i ++){cin >> a[i];add(S, i, 1);add(i, S, 0);for(int j = 0; j < 60; j ++){if(a[i] >> j & 1){add(i, n + j + 1, 1e18);add(n + j + 1, i, 0);}}}for(int j = 1; j <= 60; j ++){add(n + j, T, 1);add(T, n + j, 0);}cout << n - dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}





以下是原文档,需要的可以去 up 主的github 仓库下载

网络流与最小割

2022 年 7 月 19 日晚上 21:30 在解题十分钟直播间讲解最小割解题方法和系列例题。

直播录像在这里

网络流的定义:

  • 有一个 s 点有一个 t 点,以及若干其它点
  • 有若干有向边。其中 s 点没有入边,t 点没有出边
  • 对于除了 s 点和 t 点以外的所有点,入流量之和等于出流量之和
  • 形象的比喻想象水管,s 点是无限的水源,t 点是无限的出口,边的权值等于管的容量
  • 整个网络同时能通过的最大流量,这个流量等于 s 点的所有出流量,等于 t 点的所有入流量

割的定义:

  • 设置两个集合 S 集合和 T 集合,且 s 点属于 S 集合,t 点属于 T 集合
  • 其它所有点属于 S 集合或 T 集合之一
  • 所有来自于 S 集合,指向 T 集合的边,权值之和为割的大小

定理:

  • 最小割 = 最大流
  • 直观理解就是 最小割的边满流的情况下,无法再找到增加流量的办法

能否套用最小割方法的判断:

  1. 把最少/最小代价对应到最小割
  2. 把二元选择问题 改变为集合选择问题
  3. 不合法的方案,定义成流量无穷大的边

建图过程:

  1. 根据可以做二元选择的对象定义所有的点
  2. 根据不合法方案连接无穷大的边,明确点的集合归属含义
  3. 根据点的集合归属含义,明确所有需要支付的成本

额外思路:

  1. 先假设能获得所有收益,然后把得不到的收益也记作成本,来解决最大化收益问题

棋子问题

有 N*M 的棋盘,上面有 K 个棋子,位于 Ai 行 Bi 列。

一次操作可以消除一行的棋子或者消除一列的棋子。

问最少要多少次操作,才能消灭所有的棋子?

1 ≤ N,M ≤ 100

思考过程:

  • 最少次操作 => 最小代价 => 最小割(把边看做代价)
  • 每一行,可以选择消除或不消除
  • 每一列,可以选择消除或不消除
  • 所以网络中的点是 行 与 列
  • 不合法的方案,表示有棋子没有被消除。

建模过程:

  • 行属于 S 集合表示不消除,属于 T 集合表示消除
  • 列属于 T 集合表示不消除,属于 S 集合表示消除
  • 不合法方案的边:
    • 对于为 1 的单元格,行不消除且列不消除非法
    • 对应单元格建立行指向列的无穷大流量边
  • 支付成本:
    • s 到行,流量为 1
    • 列到 t,流量为 1

设备采购问题

有 N 种设备,采购价格分别是 A1,A1,…AN

和 M 个项目,项目收益分别是 B1,B1,…BM

另外有 K 个约束条件,Ci,Di 表示完成 Di 号项目,必须要拥有 Ci 号设备。

问最高能获得的利润是多少(利润等于收益-成本)

思考过程:

  • 先假设能获得所有收益,然后把得不到的收益也记作成本
  • 设备:采购与不采购;项目:做与不做
  • 不合法方案:项目依赖的设备没有采购,但又要做对应项目

建图过程:

  • 设备属于 S 集合表示不采购,属于 T 集合表示采购
  • 项目属于 S 集合表示不做,属于 T 集合表示做
  • 不合法方案:
    • 项目依赖设备,但设备未采购,不合法
    • 有依赖时,从设备指向项目,流量无穷大
  • 支付成本:
    • 设备采购支付成本,s 点指向设备,流量为采购成本
    • 项目不做支付损失,项目指向 t 点,流量为项目收益

取数问题

在一个 M*N 的棋盘中,每个方格有一个正整数。现在要从方格中取若干个数,使任意 2 个数所在方格没有公共边,并使取出的数总和最大。试设计一个满足要求的取数算法。

思考过程:

  • 先假设能获得所有数,然后建图使方案合法
  • 每个数选择与不选择
  • 不合法的方案:相邻的格子不能同时选

建图过程:

  • 经过尝试和思考,得出结论,区分坐标奇偶性(横坐标和纵坐标之和的奇偶性)
  • 偶数格属于 S 集合表示选择,属于 T 集合表示不选择
  • 奇数格属于 T 集合表示选择,属于 S 集合表示不选择
  • 不合法方案:
    • 相邻的格子不能同时选
    • 相邻的格子,从偶数格向奇数格建边,流量无穷大
  • 支付代价
    • 偶数格不选择,s 向偶数格建边,流量为格子的值
    • 奇数格不选择,奇数格向 t 建边,流量为格子的值

另一个棋子问题

本题来自于AtCode ABC259

有 N*M 的棋盘,每个方格有一个数,其中有正数也有负数。要求选定其中的若干行和若干列,满足:

  • 要求负数的格子不能同时选择所在行和所在列。

如果方格所在的行或所在的列被选中,它的分数被加到总分上,不论是正数还是负数。如果行和列同时被选中,分数也只累加一次。

试设计一个算法,问能得到的最大得分是多少。

思考过程:

  • 记所有正数之和为最大收益,考虑需要支付的成本
  • 行:选择与不选择,列:选择与不选择
  • 不合法方案:负数格的行与列不能同时选择

建图过程:

  • 行选择:属于 S 集合;不选择:属于 T 集合
  • 列选择:属于 T 集合;不选择:属于 S 集合
  • 不合法方案:
    • 负数格不能同时选择所在行和所在列
    • 负数格从行向列建立流量无穷大的边
  • 支付成本:
    • 行选择,支付该行所有负数格成本,行到 t 连边,权值为该行所有负数的绝对值和
    • 列选择,支付该列所有负数格成本,s 到列连边,权值为该列所有负数的绝对值和
    • 正数格,行和列都不选择,支付放弃的成本,列到行建边,权值为该格的值

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com