This is not the end.

0%

HDU3840 【WF2011】Chips Challenge

Posted on Edited on

Sol

2016年集训队论文的第二篇讲到了这道题，但是论文中的建图方式似乎会出现负环（也有可能是我写炸了？）。下面的建图方法是从KIDGIN7439的这篇博客中看到的，因为觉得原文的阐述十分不清楚，重新阐述如下。

首先枚举$lim$为每一行、每一列的部件数量的最大值。求出在$lim$限制下能个放的最大零件数$tot’$，只要判断$lim \le \lfloor tot’ \cdot \frac{A}{B} \rfloor$是否成立，就能限制为$lim$时是否存在合法的方案，并更新答案。

建图方法：

  1. 对第$i$行建一个点$A_i$，对第$i$列建一个点$B_i$
  2. 从$S$向$A_i$连容量下界为$0$，上界为$lim$，费用为$0$的边
  3. 从$B_i$向$T$连容量下界为$0$，上界为$lim$，费用为$0$的边
  4. 从$A_i$向$B_i$连容量下界为$0$，上界为$\infty$，费用为$0$的边
  5. 如果$(i,j)$这个位置是.，就从$A_i$向$B_j$连一条容量下界为$0$，上界为$1$，费用为$1$的边
  6. 如果$(i,j)$这个位置是C，就从$A_i$向$B_j$连一条容量下界为$1$，上界为$1$，费用为$1$的边

这张图的最大费用最大流 - C的个数就是答案。

考虑如何满足题目中的几个限制：

  • 一个观察是，$S$到$A_i$、$B_i$到$T$的边都会满流
    • 流量大小 = $S$到$A_i$的边的流量和 = $B_i$到$T$的流量和
    • 存在方案使这些边都满流：只流第2，3，4类边，不流第5类边
    • 我们求的是最大费用最大流
  • 第二观察是，从$A_i$流出的第5，6类边的流量，等于流入$B_i$的第5，6类边的流量，这样就满足了“第$i$行的零件数量等于第$i$列的零件数量
    • 从$A_i$流出的总流量 = 流入$B_i$的总流量 = $lim$
    • 从$A_i$通过第4类边流出的流量 =通过第4类边流入$B_i$的流量
    • 两式相减即得出上面的观察
  • 从第二个观察也可看出，每个$A_i$流出的第5，6类边的流量不超过$lim$，流入$B_i$的第5，6类边的流量不超过$lim$，也就满足了每行、每列的部件数量不超过$lim$的限制

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=110;
int S,T;
namespace Flow {
    int head[N],cur[N],dis[N],vis[N];
    struct ed { int to,next,f,w; };
    vector<ed> e;
    void init() { memset(head,-1,sizeof(head)); }
    void ad(int x,int y,int f,int w) {
        e.PB((ed){y,head[x],f,w}); head[x]=e.size()-1;
        e.PB((ed){x,head[y],0,-w}); head[y]=e.size()-1;
    }
    bool bfs() {
        memset(dis,-0x3f,sizeof(dis));
        memcpy(cur,head,sizeof(cur));
        queue<int> q;
        q.push(S),vis[S]=1,dis[S]=0;
        while(!q.empty()) {
            int u=q.front(); q.pop(),vis[u]=0;
            for(int k=head[u];~k;k=e[k].next) if(e[k].f) {
                int v=e[k].to;
                if(dis[v]<dis[u]+e[k].w) {
                    dis[v]=dis[u]+e[k].w;
                    if(!vis[v]) vis[v]=1,q.push(v);
                }
            }
        }
        return dis[T]>-1e9;
    }
    int dfs(int u,int f) {
        if(u==T||!f) return f; int ret=0,tmp;
        vis[u]=1;
        for(int &k=cur[u];~k;k=e[k].next) if(e[k].f) {
            int v=e[k].to;
            if(!vis[v]&&dis[v]==dis[u]+e[k].w&&(tmp=dfs(v,min(f,e[k].f)))) {
                e[k].f-=tmp,e[k^1].f+=tmp;
                ret+=tmp,f-=tmp;
                if(!f) break;
            }
        }
        vis[u]=0;
        return ret;
    }
    int work() { int ans=0; while(bfs()) ans+=dis[T]*dfs(S,1e9); return ans; }
}
int n,A,B;
char mp[55][55];
int main() {
	int ts=0;
	while(~scanf("%d%d%d",&n,&A,&B)) {
		if(!n&&!A&&!B) break;
		for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
		S=2*n+1,T=2*n+2;
		int M=n*n*n+10; // shoule be larger than length of any possible path
		int mx=-1;
		for(int lim=n;lim>=0;--lim) {
			Flow::init();
			for(int i=1;i<=n;++i)
				Flow::ad(S,i,lim,0),
				Flow::ad(i,i+n,1e9,0),
				Flow::ad(i+n,T,lim,0);
			int tot=0;
			for(int i=1;i<=n;++i)
				for(int j=1;j<=n;++j) {
					if(mp[i][j]=='.') Flow::ad(i,j+n,1,1);
					if(mp[i][j]=='C') Flow::ad(i,j+n,1,M+1),tot++;
				}
			int ans=Flow::work();
			if(ans<tot*(M+1)) continue;
			ans%=M;
			if(ans*A<lim*B) continue;
			mx=max(mx,ans-tot);
		}
		printf("Case %d: ",++ts);
		if(mx<=-1) printf("impossible\n");
		else printf("%d\n",mx);
	}
	return 0;
}