记录编号 | 238917 | 评测结果 | AAAAAAAAAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [国家集训队2011]部落战争 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 0.043 s | ||
提交时间 | 2016-03-19 15:27:31 | 内存使用 | 2.28 MiB | ||
#include<cstdio> #include<iostream> #include<vector> #include<deque> using namespace std; const int SIZEN=60,SIZEM=6000,INF=0x7fffffff/2; int N,M; char c[SIZEN][SIZEN]; int id[SIZEN][SIZEN]={0}; int tot=0; vector<int> s[SIZEM]; int R,C; int dx[]={1,1},dy[]={-1,1}; class miku { public: int fr,to,cap,flow; miku(){} miku(int a,int b,int c,int d) { fr=a,to=b,cap=c,flow=d; } }E[SIZEM*20]; int S,T; void read() { scanf("%d%d%d%d",&N,&M,&R,&C); S=0; for(int i=0;i<N;i++) scanf("%s",c[i]); for(int i=0;i<N;i++) { for(int j=0;j<M;j++) id[i][j]=++tot; } } bool on(int x,int y) { if(x<0||y<0) return 0; if(x>=N||y>=M) return 0; if(c[x][y]=='x') return 0; return 1; } int totw=0; void add(int fr,int to,int cap) { s[fr].push_back(totw);E[totw++]=miku(fr,to,cap,0); s[to].push_back(totw);E[totw++]=miku(to,fr,0,0); } deque<int> Q; int ans=0; int H[SIZEM]={0},e[SIZEM]={0}; void push(int x,int t) { miku &v=E[t]; int flow=min(e[x],v.cap-v.flow); e[x]-=flow;v.flow+=flow; e[v.to]+=flow;E[t^1].flow-=flow; if(v.to!=S&&v.to!=T&&e[v.to]) Q.push_back(v.to); } void use_up(int x) { int mi; while(e[x]) { mi=INF; for(int i=0;i<s[x].size();i++) { miku &v=E[s[x][i]]; if(v.cap<=v.flow) continue; if(H[v.to]==H[x]-1) { push(x,s[x][i]); if(!e[x]) break; } else mi=min(mi,H[v.to]); } if(!e[x]) break; H[x]=mi+1; } } void maxflow() { H[0]=T;if(H[0]>100) H[0]=100; e[0]=INF; for(int i=0;i<s[0].size();i++) push(0,s[0][i]); while(!Q.empty()) { int x=Q.front(); //cout<<x<<endl; Q.pop_front(); use_up(x); } ans-=e[T]; printf("%d\n",ans); } void makegragh() { S=0;T=2*tot+1; //cout<<T<<endl; for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { if(c[i][j]=='x') continue; //cout<<c[i][j]<<endl; add(S,id[i][j],1); //add(id[i][j],id[i][j]+tot,1); add(id[i][j]+tot,T,1); ans++; for(int k=0;k<2;k++) { int x=i+dx[k]*R,y=j+dy[k]*C; if(on(x,y)) add(id[i][j],id[x][y]+tot,1); } if(R==C) continue; for(int k=0;k<2;k++) { int x=i+dx[k]*C,y=j+dy[k]*R; if(on(x,y)) add(id[i][j],id[x][y]+tot,1); } } } } int main() { freopen("lanzerb.in","r",stdin); freopen("lanzerb.out","w",stdout); read(); makegragh(); //cout<<"arrive"<<endl; maxflow(); return 0; }