BZOJ 1066[SCOI 2007]トカゲ

1066:[SCOI 2007]トカゲ
Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 2356  Solved: 1148[Submit][Status][Discuss]
Description
r行c列のグリッドマップには高さの異なる石柱があり、いくつかの石柱にはトカゲが立っています.あなたの任務はできるだけ多くのトカゲを境界の外に逃がすことです.各行の各列の隣接する石柱の距離は1であり、トカゲのジャンプ距離はdであり、すなわちトカゲは平面距離がdを超えないいずれかの石柱にジャンプすることができる.石柱は不安定で、トカゲがジャンプするたびに離れた石柱の高さが1(地図の内部に落ちている場合は到達した石柱の高さが変わらない)減少し、その石柱の元の高さが1であればトカゲは離れて消えてしまう.その後他のトカゲは足を踏み入れることができない.いつでも2匹のトカゲが同じ石柱にいることはできない.
Input
第1の挙動の3つの整数r,c,d,すなわち地図の規模と最大ジャンプ距離を入力する.以下rは石竹の初期状態を示し、0は石柱がないことを示し、1~3は石柱の初期高さを示す.以下rはトカゲの位置を表し、「L」はトカゲを表す.トカゲがいないことを示す.
Output
出力は1行のみで、脱出できないトカゲの総数の最小値を含む整数です.
Sample Input
5 8 2 00000000 02000000 00321100 02000000 00000000 ........ ........ ..LLLL.. ........ ........
Sample Output
1
HINT
 
100%のデータ満足:1<=r,c<=20,1<=d<=4
 
Source
标题:面白いネットの流れですよ.以前のモデリングは問題そのものに対して行われていましたが、今回のモデリングはネットワークストリームそのものに対して行われたのでしょうか...
トカゲが飛び出すと、ある杭が1つ減って、巣萌は杭ごとに1つの辺だと考えることができるのではないでしょうか.それぞれのトカゲの選択は流量で、1匹のトカゲの流量をプラスして、実は残量のネットワークの中で容量が1つ減らして、完全にネットワークの流れに合って、いいですね.の
それからどのように図を建てるべきか.
この问题は何発も出して、间违いを分かち合います...
1.長い間探していた最も深刻なエラー:

int id1(int x,int y){return (x-1)*m+y;}int id2(int x,int y){return (x-1)*m+y+sizn;}

xの下标は1から、それではxは1减らないで死んでしまいます...
2.これが正方形ではないことを忘れて、cを無視しました...
3.飛び出すと判断するinメソッドに等号を付けるかどうかをはっきり考えていない
4.1つのtipは、最初はユークリッド距離を使い、doubleとepsを持って計算したが、後で浮動小数点演算をできるだけ避けなければならない.の

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<stack>
 6 #include<queue>
 7 #include<cstring>
 8 #define PAU putchar(' ')
 9 #define ENT putchar('
')
10 #define MSE(a,b) memset(a,b,sizeof(a))
11 #define REN(x) for(ted*e=fch[x];e;e=e->nxt)
12 #define TIL(x) for(int i=1;i<=x;i++)
13 #define ALL(x) for(int j=1;j<=x;j++)
14 using namespace std;
15 const int maxt=20+5,maxn=800+10,maxm=320000+10,inf=-1u>>1;
16 int n,m,d,map[maxt][maxt];bool b[maxt][maxt];char s[maxt];
17 struct isap{
18     struct ted{int x,y,w;ted*nxt,*re;}adj[maxm],*fch[maxn],*cur[maxn],*ms;
19     int d[maxn],gap[maxn],ret[maxn],S,T,n;
20     void init(int n){this->n=n;ms=adj;MSE(d,-1);return;}
21     void add(int x,int y,int w){
22         *ms=(ted){x,y,w,fch[x],ms+1};fch[x]=ms++;
23         *ms=(ted){y,x,0,fch[y],ms-1};fch[y]=ms++;
24         return;
25     }
26     void bfs(){
27         queue<int>Q;Q.push(T);d[T]=0;
28         while(!Q.empty()){
29             int x=Q.front();Q.pop();REN(x){int v=e->y;
30                 if(d[v]<0)d[v]=d[x]+1,Q.push(v);
31             }
32         }return;
33     }
34     int mxflow(int S,int T){
35         this->S=S;this->T=T;bfs();int flow=0,k=S;ted*e;TIL(n)gap[d[i]]++,cur[i]=fch[i];
36         while(d[S]<n){
37             if(k==T){int mi=inf,p;
38                 for(int i=S;i!=T;i=cur[i]->y)if(cur[i]->w&&cur[i]->w<mi)mi=cur[i]->w,p=i;
39                 for(int i=S;i!=T;i=cur[i]->y)cur[i]->w-=mi,cur[i]->re->w+=mi;flow+=mi;k=p;
40             }for(e=cur[k];e;e=e->nxt)if(e->w&&d[k]==d[e->y]+1)break;
41             if(e)cur[k]=e,k=e->y,ret[k]=e->x;
42             else{if(--gap[d[k]]==0)break;cur[k]=fch[k];int mi=n;
43                 REN(k)if(e->w&&d[e->y]<mi)mi=d[e->y];d[k]=mi+1;gap[d[k]]++;if(k!=S)k=ret[k];
44             }
45         }return flow;
46     }
47 }sol;
48 int sizn;int id1(int x,int y){return (x-1)*m+y;}int id2(int x,int y){return (x-1)*m+y+sizn;}
49 inline int read(){
50     int x=0;bool sig=true;char ch=getchar();
51     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=false;
52     for(;isdigit(ch);ch=getchar())x=10*x+ch-'0';return sig?x:-x;
53 }
54 inline void write(int x){
55     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
56     int len=0;static int buf[20];while(x)buf[len++]=x%10,x/=10;
57     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
58 }
59 bool in(int x,int y){return (x-1<d)||(y-1<d)||(n-x<d)||(m-y<d);}
60 int dist(int x,int y,int x1,int y1){return (x-x1)*(x-x1)+(y-y1)*(y-y1);}
61 int S,T,cnt;
62 int main(){
63     n=read();m=read();d=read();sizn=n*m;sol.init(sizn*2+2);S=sizn*2+1;T=sizn*2+2;
64     TIL(n){scanf("%s",s);ALL(m)map[i][j]=s[j-1]-'0';}
65     TIL(n){scanf("%s",s);ALL(m)if(s[j-1]=='L')b[i][j]=true,cnt++;}
66     TIL(n)ALL(m)if(map[i][j])sol.add(id1(i,j),id2(i,j),map[i][j]);
67     TIL(n)ALL(m)if(b[i][j])sol.add(S,id1(i,j),1);
68     TIL(n)ALL(m)if(map[i][j]&&in(i,j))sol.add(id2(i,j),T,inf);
69     TIL(n)ALL(m)if(map[i][j])for(int i2=1;i2<=n;i2++)for(int j2=1;j2<=m;j2++)if(((i^i2)||(j^j2))&&map[i2][j2]&&dist(i,j,i2,j2)<=(d*d))sol.add(id2(i,j),id1(i2,j2),inf);
70     write(cnt-sol.mxflow(S,T));
71     return 0;
72 }

でも书くと爽やかです...