[Wf2011]Chips Challenge

• problem
• solution
• code

problem

BZOJ2673

solution

.

首先得知道这是网络流，但真的看不出来啊！！我真的郁闷啊(￣﹏￣；)

在知道做法是网络流后，初读题，肯定会想到将行列分左右点，$[1,n]$表示行，$[n+1,2n]$表示列。

然后就发现举步维艰，因为题目要维护的两个条件都不是很好操作。

$i$ 行 $i$ 列零件数一样，且每行零件数不能超过总数的 $\frac{A}{B}$。

这两个限制条件都没有明确具体零件个数要求，是随着全局动态变化的。

所以无法变成网络流上的容量限制。

唯一知道的限制就是每行每列可放芯片的最大数量。

【可放指的是 . /C 的点】

注意到 $n$ 的限制很小，不妨考虑枚举每行可放零件的最大值个数 $Max$。

如果能通过网络流求出总零件数量 $tot$，就可以逆向判断 $Max\le \frac{A}{B}tot\Rightarrow Max\ast B\le A\ast tot$。

而网络流是最大流，是尽量做到流满的，所以 $tot$ 一定会尽可能的大。

增长同向平行，最大流就是在做尽量满足判断式子的过程。

所以如果最大流的结果还是不满足上面的不等式，只能说明 $Max$ 不是合法的。

自然地想到，对于可放芯片的位置 $(i,j)$ 进行 $i$ 行向 $j$ 列连边，容量为 $1$ 。

这样去跑网络流，跑出的最大流确实是最多能放的芯片数量，但是这样并没有考虑到 $i$ 行 $i$ 列相等的限制。

因为不能知道第 $i$ 行和第 $i$ 列具体放了多少个芯片，没有明确的容量限制。

但是转化一下，第 $i$ 行放了芯片的位置和第 $i$ 列没放芯片的位置加起来一共是等于 $n$ 的。

所以想到新建一个连接点 $k$，分别让行列点向 $k$ 连边。

行连接的边流过的流量来表示行放芯片的个数，列连接的边流过的流量来表示列不放芯片的个数。

行列与 $k$ 之间的边容量设为 $\infty$。

然后连接点向 $t$ 连边，容量为 $n$，保证 $k\to t$ 的边满流即可。

因为这样代表着第 $i$ 行放的个数和第 $i$ 列不放的个数加在一起是等于 $n$ 的，变相地满足第 $i$ 行和第 $i$ 列个数相同的限制。

但是怎么能一些边流了表示不选，一些边流了表示要选。最大流上面看到了是不能做到的，那就只能考虑最小费用了。

行 $i$ 流给连接点 $k$ 的表示要放的芯片，列 $i$ 流给 $k$ 的表示不放的芯片，所以 $i\to j$ 这种流给其它列点就应当表示 $(i,j)$ 不放芯片，所以只有 $i$ 行 $j$ 列是 . 才有选择不放的可能。

为了记录这样的边流了多少，就把这种边带上费用 $1$，跑最小费用就是尽可能减少不放的，即最大化放的芯片。

除了这样的边，其余边费用就为 $0$，属于要跑最大流。

别忘了，一开始枚举的每行放芯片个数的限制，所以行与连接点之间的容量应该修改为 $Max$。

注意到，现在的网络还有一个冗余的地方，列 $i$ 的出边只有连接点 $k$，且容量为 $\infty$，所以可以将列 $i$ 与连接点进行合并。

那么现在的网络，行 $i$ 的流量只有两种去向：经过列 $i$ 最多流 $Max$ 个，剩下的都是流到其他列 $j$ 地方，表示不放芯片，且带有费用 $1$。

最后最大流减去最小费用就是真正放的芯片个数，再减去一定放的 C 个数就是新放的芯片个数。

最后记得还有行列分别与源汇的连边。

通过 $s\to i$ 容量为第 $i$ 行可放的芯片数量来限制第 $i$ 行放置的个数。

通过 $j\to t$ 容量为第 $j$ 列可放的芯片数量来限制第 $j$ 列放置的个数。【准确来说是 $j+n\to t$，大家意会就行】

最后让这个网络满流即可。

总结一下建图过程：
$$\{\begin{array}{l}s\to iro{w}_i,0\\ i+n\to nco{l}_i,0\\ i\to j+n1,1(ch[i][j]{=}^{\prime }{.}^{\prime })\\ i\to i+nMax,0\end{array}$$

code

#include <bits/stdc++.h> using namespace std; #define maxn 105 #define maxm 5005 int n, a, b, s, t, cnt; bool vis[maxn]; char ch[maxn][maxn]; int dis[maxn], head[maxn], lst[maxn], row[maxn], col[maxn]; struct node { int to, nxt, flow, w; }E[maxm]; queue < int > q;void addedge( int u, int v, int flow, int w ) {E[cnt] = { v, head[u], flow, w };head[u] = cnt ++;E[cnt] = { u, head[v], 0, -w };head[v] = cnt ++; }bool spfa() {memset( dis, 0x7f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[s] = 0; q.push( s );while( ! q.empty() ) {int u = q.front(); q.pop(); vis[u] = 0;for( int i = head[u];~ i;i = E[i].nxt ) {int v = E[i].to;if( dis[v] > dis[u] + E[i].w and E[i].flow ) {dis[v] = dis[u] + E[i].w;lst[v] = i;if( ! vis[v] ) vis[v] = 1, q.push( v );}}}return ~ lst[t]; }void MCMF( int &flow, int &cost ) {flow = cost = 0;while( spfa() ) {int Min = 1e9;for( int i = lst[t];~ i;i = lst[E[i ^ 1].to] )Min = min( Min, E[i].flow );for( int i = lst[t];~ i;i = lst[E[i ^ 1].to] )cost += E[i].w * Min, E[i].flow -= Min, E[i ^ 1].flow += Min;flow += Min;} }int main() {int Case = 0;while( ~ scanf( "%d %d %d", &n, &a, &b ) ) {if( ! n and ! a and ! b ) break;memset( row, 0, sizeof( row ) );memset( col, 0, sizeof( col ) );s = 0, t = n << 1 | 1;int sum = 0, used = 0;for( int i = 1;i <= n;i ++ ) {scanf( "%s", ch[i] + 1 );for( int j = 1;j <= n;j ++ )if( ch[i][j] != '/' ) {sum ++, row[i] ++, col[j] ++;used += ch[i][j] == 'C';}}int ans = -1;for( int Max = 0, flow, cost;Max <= n;Max ++ ) {memset( head, -1, sizeof( head ) ); cnt = 0;for( int i = 1;i <= n;i ++ ) {addedge( s, i, row[i], 0 );addedge( i + n, t, col[i], 0 );addedge( i, i + n, Max, 0 );for( int j = 1;j <= n;j ++ )if( ch[i][j] == '.' ) addedge( i, j + n, 1, 1 );}MCMF( flow, cost );if( flow == sum and Max * b <= ( sum - cost ) * a )ans = max( ans, sum - cost );}printf( "Case %d: ", ++ Case );if( ~ ans ) printf( "%d\n", ans - used );else printf( "impossible\n" );}return 0; }

总结

以上是生活随笔为你收集整理的[Wf2011]Chips Challenge（最小费用最大流）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。