社区讨论
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 条回复,欢迎继续交流。
正在加载回复...