网站设计框架图,中国纪检监察报电子版官网,超链接html代码,建网站多少钱可以卖货的原题链接#xff1a;E. Matrix Problem 题目大意#xff1a; 给出一个 n n n 行 m m m 列的 0 / 1 0/1 0/1 矩阵#xff0c;再给出一些限制条件#xff1a;一个长为 n n n 的数组 a a a#xff0c;和一个长为 m m m 的数组 b b b 。
其中 a i a_{i} ai 表示第 …原题链接E. Matrix Problem 题目大意 给出一个 n n n 行 m m m 列的 0 / 1 0/1 0/1 矩阵再给出一些限制条件一个长为 n n n 的数组 a a a和一个长为 m m m 的数组 b b b 。
其中 a i a_{i} ai 表示第 i i i 行要有 恰好 a i a_{i} ai 个 1 1 1 b j b_{j} bj 表示第 j j j 列要有 恰好 b j b_{j} bj 个 1 1 1 保证 1 ≤ a i ≤ m , 1 ≤ b j ≤ n 1 \leq a_{i} \leq m,1 \leq b_{j} \leq n 1≤ai≤m,1≤bj≤n 。
你可以使用 任意多次 操作将一个 0 0 0 翻转成 1 1 1 或将 1 1 1 翻转成 0 0 0 。
问最少的操作次数是多少才能使得这个矩阵满足以上 a , b a,b a,b 限制如果怎么操作都不能满足以上限制则输出 − 1 -1 −1 。
解题思路 套路的我们将行和列看成点行为左部列为右部而每个位置 ( i , j ) (i,j) (i,j) 的信息看成是一条 i i i 和 j j j 的边这样我们的矩阵就会形成一张天然的二分图。
回到这一题首先要是连 ∑ i 1 n a i ≠ ∑ i 1 m b i \sum_{i1}^{n} a_{i} \neq \sum_{i1}^{m} b_{i} ∑i1nai∑i1mbi 了那肯定无论如何都不会满足的但只有这个条件是不够的而且很容易找出反例但我们可以先判掉使得接下来 ∑ i 1 n a i ∑ i 1 m b i \sum_{i1}^{n} a_{i} \sum_{i1}^{m} b_{i} ∑i1nai∑i1mbi 方便后续讨论。
考虑全是 0 0 0 我们怎么做本质上就是每条边流量为 1 1 1 源点 S → [ 1 , 2 , . . . , n ] S \rightarrow [1,2,...,n] S→[1,2,...,n] 连一条流量为 a i a_{i} ai 的边 [ 1 , 2 , . . . , m ] → [1,2,...,m] \rightarrow [1,2,...,m]→ 汇点 T T T 连一条流量为 b i b_{i} bi 的边然后跑一个最大流即可。
当我们发现最大流和 ∑ i 1 n a i \sum_{i1}^{n} a_{i} ∑i1nai 不等那么显然无论如何操作也是不行的。
其实本质上就是在做一个匹配的操作点 A A A 可以匹配 a i a_{i} ai 个人点 B B B 可以匹配 b i b_{i} bi 个人看是否使得每个人都能匹配完全
但是这一题是带操作次数的条件的我们要最小操作次数而且矩阵初始值也不是全为 0 0 0 这要怎么办
首先考虑 0 0 0 的位置的影响如果某个地方的 0 0 0 无论如何都要翻转为 1 1 1 的那么这个 0 0 0 对操作的贡献是固定为 1 1 1 的我们直接操作就好。而其他无所谓的 0 0 0 显然去操作只会让操作数变多不优。
再考虑 1 1 1 的位置的影响无论如何我们都要把多余的 1 1 1 给删掉我们不妨先全部删除了操作数就是 1 1 1 的个数。再考虑哪些 1 1 1 是可以作为选择的然后反悔我们的删除操作把这个 1 1 1 加回来即可这样对我们操作的贡献是为 − 1 -1 −1 的。
按照上面的转化假设矩阵为 g n , m g_{n,m} gn,m 那么
先假设矩阵全为 0 0 0 统计 1 1 1 的个数。当 g i , j 1 g_{i,j}1 gi,j1 时我们添加边 i → j i \rightarrow j i→j 流量为 1 1 1费用为 − 1 -1 −1 反悔。当 g i , j 0 g_{i,j}0 gi,j0 时我们添加边 i → j i \rightarrow j i→j 流量为 1 1 1费用为 1 1 1 固定。 S S S 向 i i i 连上流量为 a i a_{i} ai费用为 0 0 0 的边 j j j 向 T T T 连上流量为 b j b_{j} bj费用为 0 0 0 的边。这里的 i , j i,j i,j 分别指的是 左部 的点的编号和 右部 的点的编号。
如果最大流不为 ∑ i 1 n a i \sum_{i1}^{n} a_{i} ∑i1nai 说明不能匹配完全输出 − 1 -1 −1 。
否则我们所需要的最小操作次数就是 ∑ i 1 n ∑ j 1 m g i , j \sum_{i1}^{n}\sum_{j1}^{m}g_{i,j} ∑i1n∑j1mgi,j 最小费用 固定 反悔的和。
代码使用的是 S p f a D i n i c SpfaDinic SpfaDinic 的费用流。
时间复杂度 O ( n 3 m 3 ) O(n^{3}m^{3}) O(n3m3) 伪多项式复杂度可以通过
AC代码
#include bits/stdc.h
using namespace std;using PII pairint, int;
using i64 long long;templateclass Ty
struct MCmaxFlow {const Ty INF numeric_limitsTy::max();int S, T, n; Ty MF 0, MC 0;struct Edge {int v, nxt; Ty f, w;Edge() : Edge(0, 0, 0, 0) {};Edge(int v, int nxt, Ty f, Ty w) : v(v), nxt(nxt), f(f), w(w) {};};vectorTy dist;vectorint cur, h;vectorbool vis;vectorEdge E;MCmaxFlow(int _) : n(_) { init(_); };void init(int _) {dist.resize(_ 1);vis.resize(_ 1);cur.resize(_ 1);h.resize(_ 1);E.resize(2);}void add(int u, int v, Ty f, Ty w) {E.emplace_back(v, h[u], f, w), h[u] int(E.size()) - 1;}void addEdge(int u, int v, Ty f, Ty w) {add(u, v, f, w), add(v, u, 0, -w);}bool SPFA() {dist.assign(n 1, INF);queueint que;dist[S] 0, cur[S] h[S];que.push(S);while (que.size()) {int u que.front(); que.pop();vis[u] false;for (int i h[u]; i; i E[i].nxt) {auto [v, nxt, f, w] E[i];if (f dist[v] dist[u] w) {dist[v] dist[u] w;if (!vis[v]) {vis[v] true;cur[v] h[v];que.push(v);}}}}return dist[T] ! INF;}Ty DFS(int u, Ty flow) {if (u T) return flow;Ty last flow;vis[u] true;for (int i cur[u]; i last; i E[i].nxt) {cur[u] i;auto [v, nxt, f, w] E[i];if (f !vis[v] dist[v] dist[u] w) {Ty cost DFS(v, min(f, last));if (!cost) dist[v] INF;E[i].f - cost, E[i ^ 1].f cost;last - cost;}}vis[u] false;return flow - last;}void work() {while (SPFA()) {Ty flow DFS(S, INF);MC dist[T] * flow;MF flow;}}
};void solve() {int n, m;cin n m;MCmaxFlowint G(n m 2);vector g(n 1, vectorint(m 1));int ans 0;// i - j 连边for (int i 1; i n; i) {for (int j 1; j m; j) {cin g[i][j];if (g[i][j]) {G.addEdge(i, n j, 1, -1);ans;} else {G.addEdge(i, n j, 1, 1);}}}G.S n m 1, G.T G.S 1;int suma 0, sumb 0;// S - i 连边for (int i 1; i n; i) {int x; cin x;G.addEdge(G.S, i, x, 0);suma x;}// j - T 连边for (int i 1; i m; i) {int x; cin x;G.addEdge(n i, G.T, x, 0);sumb x;}//先特判 sum a ! sum bif (suma ! sumb) {cout -1 \n;return;}G.work();//再特判 maxFlow ! sum aif (G.MF ! suma) {cout -1 \n;return;}//答案就是 sum g[i][j] minCostcout ans G.MC \n;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t 1; //cin t;while (t--) solve();return 0;
}
