Chips Challenge[WF2011]

发表于 分类于

题目链接

luogu

题解

可以通过连 $\infty/ -\infty$ 的边来实现强制相等。

首先，每个格子选的总数难以确定，那么我们可以枚举格子选的总数 $k$，然后最后看看这时候的答案是否和这个 $k$ 相等。枚举以后，每行和每列的限制就确定了，设 $mx=\lfloor k\times \frac{a}{b}\rfloor$。

根据网络流的套路，我们将行列分别建点。然后连边。

首先建一个源点 $s$ 和汇点 $t$，$s$ 向每行的点连一条 $[0,mx]$ 的边，每列向 $t$ 连一条 $[0,mx]$ 的边，表示不超过 $mx$ 的限制。

对于每个格子 $(i,j)$ ：可选连 $[0,1]$，必选连 $[1,1]$，不选啥都不干。

然后跑最大流就好了。

但是，有个很恶心的是他要求行和列选择的要相同。

这时候需要考虑增设一个费用，把每选一个格子就增设费用 $1$，即考虑行和列之间连边时的费用是 $1$。

还需要强制满足 $i$ 行和 $i$ 列选的个数相同。那么增设一条从 $i$ 行连向 $i$ 列，容量 $[0,\infty]$，费用为 $0$ 的边。那么它最后一定是要满流的（不满流就不是最大流了），且除了这条边以外的流量之和相等（否则就不满流了）。

这样就可以了，最后求个最大费用最大流。

程序

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
98
99
100
101
102
103
104
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N=1000;
const int M=100000;
const int inf=1e8;
int s,t;
namespace MCMF{
	int ver[M],ne[M],cost[M],val[M],head[N],tot=1;
	inline void add(int x,int y,int v,int c)
	{
		ver[++tot]=y; val[tot]=v; cost[tot]=c; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; cost[tot]=-c;ne[tot]=head[y]; head[y]=tot;
	}
	int d[N],pre[N],mi[N];
	bool vis[N];
	queue<int> q;
	inline bool spfa()
	{
		fo(i,0,t) d[i]=inf,pre[i]=mi[i]=0;
		d[s]=0; mi[s]=inf; q.push(s);
		for(int u;!q.empty();)
		{
			u=q.front(); q.pop(); vis[u]=0;
			for(int i=head[u],v;i;i=ne[i])
				if(val[i]&&d[v=ver[i]]>d[u]+cost[i])
				{
					d[v]=d[u]+cost[i];
					pre[v]=i; mi[v]=min(mi[u],val[i]);
					if(!vis[v]) vis[v]=1,q.push(v);
				}
		}
		return mi[t]!=0;
	}
	inline int work()
	{
		int ans=0;
		for(;spfa();ans+=d[t]*mi[t])
		{
			for(int v=t;v!=s;v=ver[pre[v]^1]) val[pre[v]]-=mi[t],val[pre[v]^1]+=mi[t];
		}
		return ans;
	}
}
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
int n,m,a[N][N];
char ss[N][N];
inline int id(int x,int y,int opt)
{
	return (x-1)*m+y+opt*n*m;
}
int main()
{
	scanf("%d%d",&n,&m);
	fo(i,1,n)
	{
		scanf("%s",ss[i]+1);
		fo(j,1,m)
			if(ss[i][j]=='R') a[i][j]=0;
			else if(ss[i][j]=='L') a[i][j]=1;
			else if(ss[i][j]=='D') a[i][j]=2;
			else a[i][j]=3;
	}
	s=0; t=n*m*2+1;
	fo(i,1,n) fo(j,1,m)
	{
		int u=id(i,j,0),x,y;
		fo(k,0,3)
		{
			x=i+fx[k],y=j+fy[k];
			if(x==0) x=n; if(x>n) x=1;
			if(y==0) y=m; if(y>m) y=1;
			MCMF::add(u,id(x,y,1),1,1-(a[i][j]==k));
		}
	}
	fo(i,1,n) fo(j,1,m) MCMF::add(s,id(i,j,0),1,0),MCMF::add(id(i,j,1),t,1,0);
	printf("%d",MCMF::work());
	return 0;
}