Solution [SCOI2007]蜥蜴
题目大意:给定一个(n)行(m)列的地图,每个点有一个经过次数限制,可以从一个点跳到与它距离不超过(d)的另一个点.问有多少只蜥蜴不能从地图中出去
最大流
题目分析:有多少只蜥蜴不能从地图中出去,可以转化成最多有多少只蜥蜴可以从地图中出去.然后从一个点跳到另一个点我们自然而然想到连有向边,每个点的经过次数限制可以看做是流量上限.最多有多少只蜥蜴可以出去,就是求最大流量.这不就是一个最大流么.然后我们来看核心——建图
首先,普通的最大流问题是每条边有流量限制,但是这个题是每个点有流量限制 .对于这个问题,拆点成边是基本操作.对于每个流量限制为(d)的点(A),连一条流量限制为(d)的边((a,a'))
然后对于从一个点跳到另一个点,如果它们间的距离小于题中所给的(d),设这两个点为(A),(B).拆点后它们对应的两条边应该是((a,a')),((b,b')).我们连一条边((a',b)),权值为(INF)(一个点经过次数由拆点后的边的流量限制来限制)
然后如果一个点(A)可以跳出地图,我们就建一个虚拟汇点(T),连边((a',T)),边权为(INF)
我们再建一个虚拟节点(S),从(S)向每一个有蜥蜴的点连一条边权为(1)的边.因为题目中限制同一个点上只能有一个蜥蜴(之前不读题调了好久)
拆点之后,原图中两个点之间有双向边是不影响答案的(并不会超流量),具体画画图很容易想,这里不再赘述
然后我们跑一遍(S),(T)最大流即可得出答案
献上码风丑陋的代码:
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int maxn = 4040;
const int INF = 0x7fffffff;
const int maxm = 444444;
struct Point{//存点的结构体,x,y为坐标,z为石柱可以经过的次数(高度),mark为该点是否有蜥蜴
int x,y,z,mark;
}point[maxn];
inline double calc(const Point &a,const Point &b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
struct Edge{//存图
int from,to,cap,flow;
Edge(){}
Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d){}
}Edges[maxm];
int head[maxn],nxt[maxm],tot = 1;
inline void addedge(int from,int to,int cap){
Edges[++tot] = Edge(from,to,cap,0);
nxt[tot] = head[from];
head[from] = tot;
Edges[++tot] = Edge(to,from,0,0);
nxt[tot] = head[to];
head[to] = tot;
}
int a[maxn],pre[maxn];
inline int maxflow(int s,int t){//蒟蒻为了省事直接上EK了,紫书的模板
int ret = 0;
while(true){
memset(a,0,sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = 0x7fffffff;
while(!Q.empty()){
int u = Q.front();Q.pop();
for(int i = head[u];i;i = nxt[i]){
Edge &e = Edges[i];
int v = Edges[i].to;
if(!a[v] && e.flow < e.cap){
a[v] = min(a[u],e.cap - e.flow);
pre[v] = i;
Q.push(v);
}
}
if(a[t])break;
}
if(!a[t])break;
for(int i = pre[t];i;i = pre[Edges[i].from])
Edges[i].flow += a[t],Edges[i ^ 1].flow -= a[t];
ret += a[t];
}
return ret;
}
char str[maxn];
int n,m,d,cnt;//cnt表示一共有多少只蜥蜴
inline int get(int x,int y){return (x - 1) * m + y;}//根据每个点的坐标计算出它的编号
int main(){
scanf("%d %d %d",&n,&m,&d);
for(int i = 1;i <= n;i++){//读入
scanf("%s",str + 1);
for(int j = 1;j <= m;j++){
int p = get(i,j);
point[p].x = i;
point[p].y = j;
point[p].z = str[j] - '0';
}
}
for(int i = 1;i <= n;i++){
scanf("%s",str + 1);
for(int j = 1;j <= m;j++){
point[get(i,j)].mark = (str[j] == 'L') ? 1 : 0;
if(str[j] == 'L')cnt++;
}
}
for(int i = 1;i <= n;i++)//拆点,所以新的点的编号就是原来点的编号乘2与乘2加1
for(int j = 1;j <= m;j++)
if(point[get(i,j)].z)addedge(2 * get(i,j),2 * get(i,j) + 1,point[get(i,j)].z);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++){
if(!point[get(i,j)].z)continue;
for(int k = 1;k <= n;k++)
for(int w = 1;w <= m;w++){//处理从一个点调到另一个点的情况
if(point[get(k,w)].z && calc(point[get(i,j)],point[get(k,w)]) <= d && !(i == k && j == w))addedge(2 * get(i,j) + 1,2 * get(k,w),INF);
}
}
for(int i = 1;i <= n * m;i++)//虚拟源点,向每个有蜥蜴的点连边
if(point[i].mark)addedge(2 * n * m + 2,i * 2,1);
for(int i = 1;i <= n * m;i++)//虚拟汇点
if(min(min(point[i].x,n - point[i].x + 1),min(point[i].y,m - point[i].y + 1)) <= d && point[i].z)addedge(i * 2 + 1,2 * n * m + 3,INF);
printf("%d
",cnt - maxflow(2 * n * m + 2,2 * n * m + 3));//跑S-T最大流即为答案
return 0;
}