题解：UVA1104 芯片难题 Chips Challenge
liujiaxi123456 · · 题解
思路：
首先是由于总数在变，所以每列的最大值不好确定，考虑枚举
考虑建模：
-
P.S. 参考了 73983 题解，建模方式是一样的，但多解释了一下，并加了个图。
-
建立
a_i 表示行，建立b_i 表示列。 -
从
s 向a_i 连容量为该行可放置芯片数量和已经放好的芯片数量的和，费用为 0 的有向边。 -
从
b_i 向t 连容量为该行可放置芯片数量和已经放好的芯片数量的和，费用为 0 的有向边， -
从
a_i 向b_i 连容量为枚举的最大数量，费用为 0 的有向边，流过这条边的流量代表i 行/列放置的芯片数量。 -
如果一个位置
(i,j) 可以放置芯片，那么从a_i 向 b_j 连容量为 1，费用为 1 的有向边，如果流过这条边表示这个位置不放置芯片。
每次判是否满流，然后最小费用表示最小不能放的芯片数量，相当于最大能放的数量。
Code：
#define ll long long
using namespace std;
const int Maxn = 100, Maxm = 3005, INF = INT_MAX/2-5;
namespace Josh_zmf {
int N, A, B, left_x[Maxn], left_y[Maxn]; string s[Maxn];
int pi[Maxn], fa[Maxn], fa_e[Maxn], bj[Maxn], now = 1;
namespace EDGE {
int sz = 1, head[Maxn];
struct Edge { int next, to, flow, cost; } edge[Maxm<<1]; // flow: 剩余流量，cost: 单价
inline void Add_edge(int u, int v, int w, int c) {
// printf("Add_edge(%d, %d, %d, %d)\n", u, v, w, c);
edge[++sz] = {head[u], v, w, c};
head[u] = sz;
edge[++sz] = {head[v], u, 0, -c};
head[v] = sz;
}
} using namespace EDGE;
inline void init(int u) { // 随便找一棵生成树
bj[u] = 1;
for(int i=head[u], v; i; i=edge[i].next) {
v = edge[i].to;
if(bj[v] or !edge[i].flow) continue;
fa[v] = u, fa_e[v] = i, init(v);
}
}
inline int phi(int u) {
if(bj[u] == now) return pi[u];
bj[u] = now, pi[u] = phi(fa[u]) + edge[fa_e[u]].cost;
return pi[u];
}
inline int pushflow(int e) {
static int stk[Maxn]; now++;
for(int u=edge[e^1].to; u; u=fa[u]) bj[u] = now;
int lca = edge[e].to;
for(; bj[lca]!=now; lca=fa[lca]) bj[lca] = now;
// 找到替换边（剩余流量最小的）
int mn = edge[e].flow, top = 0, id = 0, type = 0;
for(int u=edge[e^1].to; u!=lca; u=fa[u]) {
stk[++top] = fa_e[u];
if(edge[fa_e[u]].flow < mn) {
mn = edge[fa_e[u]].flow, id = u, type = 1;
}
}
for(int v=edge[e].to; v!=lca; v=fa[v]) {
stk[++top] = fa_e[v]^1;
if(edge[fa_e[v]^1].flow < mn) {
mn = edge[fa_e[v]^1].flow, id = v, type = 2;
}
}
stk[++top] = e;
// 延环推送流量
int cost = 0;
for(int i=1; i<=top; i++) {
cost += edge[stk[i]].cost*mn;
edge[stk[i]].flow -= mn;
edge[stk[i]^1].flow += mn;
}
if(!type) return cost; // 最小的就是当前边，不用加入生成树
// 加入树上，反转一条链的方向
if(type == 2) e ^= 1;
int u = edge[e^1].to, v = edge[e].to;
for(; v!=id; ) {
e ^= 1, bj[u] = 0, swap(fa_e[u], e); // u 链上的信息过期
int tmp = fa[u];
fa[u] = v, v = u, u = tmp; // 反转方向
}
return cost;
}
inline pair<int, int> Simplex(int s, int t) {
memset(fa_e, 0, sizeof(fa_e));
Add_edge(t, s, INF, -INF), init(t), fa[t] = fa_e[t] = 0;
bj[t] = now = 2; int flow = 0, cost = 0;
while(1) {
bool flag = 0;
for(int i=2; i<=sz; i++) {
if(!edge[i].flow) continue;
if(edge[i].cost+phi(edge[i^1].to)-phi(edge[i].to) >= 0) continue; // 没负环
cost += pushflow(i), flag = 1;
}
if(!flag) break;
}
flow = edge[sz].flow;
return {flow, cost+flow*INF};
}
inline int main() {
for(int Case=1; 1; Case++) {
cin>> N>> A>> B;
if(!N) break;
for(int i=1; i<=N; i++) left_x[i] = left_y[i] = 0;
int Can = 0, Had = 0;
for(int i=1; i<=N; i++) {
cin>> s[i], s[i] = ' ' + s[i];
for(int j=1; j<=N; j++) {
if(s[i][j] == '.') Can++, left_x[i]++, left_y[j]++;
else if(s[i][j] == 'C') Had++, left_x[i]++, left_y[j]++;
}
}
int S = 2*N+1, T = 2*N+2, ans = -1;
// for(int limit=N; ~limit; limit--) {
for(int limit=1ll*(Can+Had)*A/B; ~limit; limit--) {
memset(head+1, 0, (2*N+2)<<2), sz = 1;
for(int i=1; i<=N; i++) {
Add_edge(S, i, left_x[i], 0), Add_edge(i+N, T, left_y[i], 0);
Add_edge(i, i+N, limit, 0);
}
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) if(s[i][j] == '.') Add_edge(i, j+N, 1, 1);
}
auto res = Simplex(S, T);
if(res.first == Can+Had and (Can+Had-res.second)*A/B>=limit) ans = max(ans, Can-res.second);
// if(res.first == Can+Had and (Can+Had-res.second)*A/B>=limit) printf("limit:%d, ans:%d, res:{%d, %d}\n", limit, ans, res.first, res.second);
// puts("_______________________");
}
if(ans == -1) cout<< "Case "<< Case<< ": impossible\n";
else cout<< "Case "<< Case<< ": "<< ans<< '\n';
}
return 0;
}
}
int main() {
Josh_zmf::main();
return 0;
}