社区讨论

ACdalao帮忙查个错儿~

P2472[SCOI2007] 蜥蜴参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi6tvndf
此快照首次捕获于
2025/11/20 10:44
4 个月前
此快照最后确认于
2025/11/20 10:44
4 个月前
查看原帖

请dalao帮忙查错 =_=

C
#include <cstdio>
#include <cstring>//must
#include <cmath>
#include <algorithm>
#define min(a,b)	((a)<(b)?(a):(b))
#define Sinl 0.000001
#define inf 0x7f7f7f7f
using namespace std;

inline int wread(){
	char c=getchar ();int flag=1,wans=0;
	while (c<'0'||c>'9'){if (c=='-') flag=-1;c=getchar ();}
	while (c>='0'&&c<='9'){wans=wans*10+c-'0';c=getchar ();}
	return wans*=flag;
}
struct node{int nxt,v,c,ot;}e[10000];
int T1,n,m,a[27][27],S,T,K,hed[10000],len;//n->line m->step 
//bool b[27][27];
void ad (int u,int v,int c){
	e[++K].v=v;e[K].c=c;e[K].nxt=hed[u];hed[u]=K;
	e[++K].v=u;e[K].c=0;e[K].nxt=hed[v];hed[v]=K;
	e[K].ot=K-1;e[K-1].ot=K;
}
int que[10000],hed1,tal1,d[10000];
bool bfs (){
	memset (d,0,sizeof d);
	hed1=tal1=0;
	que[++hed1]=S;
	d[S]=1;
	while (tal1<hed1){
		int x=que[++tal1];
		for (int i=hed[x];i!=-1;i=e[i].nxt){
			int v=e[i].v;
			if (!d[v]&&e[i].c>0){
				que[++hed1]=v;
				d[v]=d[x]+1;
			}
		}
	} 
	if (d[T])	return true;
	return false;
}
int dfs (int x,int limit){
	if (x==T)	return limit;
	int wng=0;
	for (int i=hed[x];i!=-1;i=e[i].nxt){
		int v=e[i].v;
		if (e[i].c>0&&d[v]==d[x]+1){
			int flow=dfs(v,min(e[i].c,limit-wng));
			wng+=flow;
			e[i].c-=flow;
			e[e[i].ot].c+=flow;
			if (wng==limit)	break;
		}
	}
	if(!wng)	d[x]=0;
	return wng;
	
}
int main (){
		memset (hed,-1,sizeof hed);
		n=wread();len=wread();m=wread();S=0;
		//
		T=n*len*3+1;
		for (int i=1;i<=n;++i){
			for (int j=1;j<=len;++j){
				scanf ("%1d",&a[i][j]);
				ad((i-1)*len+j+n*len,(n*len*2)+(i-1)*len+j,a[i][j]);
			}
		} 
		//
		int num=0;
		for (int i=1;i<=n;++i){
			scanf ("%s",c+1);
			for (int j=1;j<=len;++j){
				if (c[j]=='L'){
					num++;
					ad(S,(i-1)*len+j,1);
					for (int i1=1;i1<=n;++i1){
						for (int j1=1;j1<=len;++j1){
								double x=sqrt((i1-i)*1.0*(i1-i)+(j1-j)*1.0*(j1-j));
								if (x>m)	continue;
								int dian=(i-1)*len+j,dian1=n*len+(i1-1)*len+j1;
								ad(dian,dian1,inf);
						}
					}
				}
			}
		}
		//
		for (int i=1;i<=m;++i){
			for (int j=1;j<=len;++j){
				ad((n*len*2)+(i-1)*len+j,T,inf);
			}
		}
		for (int i=m+1;i<=n-m;++i){
			for (int j=1;j<=m;++j){
				ad((n*len*2)+(i-1)*len+j,T,inf);
			}
			for (int j=len-m+1;j<=len;++j)
				ad((n*len*2)+(i-1)*len+j,T,inf);
		}
		for (int i=n-m+1;i<=n;++i){
			for (int j=1;j<=len;++j){
				ad((n*len*2)+(i-1)*len+j,T,inf);
			}
		}
		int ans=0;
		while (bfs())	ans+=dfs(S,inf);
		printf("%d\n",num-ans);
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...