BZOJ1565 植物大战僵尸 题解

题目内容:

BZOJ1565 植物大战僵尸 题解

题目分析:有选A则必须选B这样的限制条件,可以发现这是最大权闭合子图模型,考虑环的情况,可以推测需要拓扑判环。

代码:

#include<bits/stdc++.h>
using namespace std; struct edge{
int from,to,flow;
}e[]; const int maxn = ,inf = ;
int n,m,num,tmp = ;
int sc[maxn][maxn];
vector <int> at[maxn][maxn];
vector <int> g[maxn*maxn+];
vector <int> ng[maxn*maxn+]; void AddEdge(int from,int to,int w){
e[num++] = (edge){from,to,w}; g[from].push_back(num-);
e[num++] = (edge){to,from,}; g[to].push_back(num-);
} int tp[maxn*maxn+],in[maxn*maxn+];
void topu(){
for(int i=;i<=n;i++) for(int j=;j<=m;j++){
if(j < m)ng[(i-)*m+j+].push_back((i-)*m+j),in[(i-)*m+j]++;
for(int k=;k<at[i][j].size();k++){
int now = at[i][j][k];
ng[(i-)*m+j].push_back(now);
in[now] ++;
}
}
queue <int> q;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)if(!in[(i-)*m+j])q.push((i-)*m+j);
while(!q.empty()){
int k = q.front();q.pop();
tp[k] = ;
for(int i=;i<ng[k].size();i++){
in[ng[k][i]]--;
if(!in[ng[k][i]])q.push(ng[k][i]);
}
}
for(int i=;i<=n*m;i++)ng[i].clear();
for(int i=;i<=n;i++) for(int j=;j<=m;j++){
if(j < m)ng[(i-)*m+j+].push_back((i-)*m+j);
for(int k=;k<at[i][j].size();k++){
int now = at[i][j][k],now2 = (i-)*m+j;
ng[now2].push_back(now);
}
}
for(int i=;i<=n*m;i++) if(tp[i] == ) q.push(i);
while(!q.empty()){
int k = q.front();q.pop();
for(int i=;i<ng[k].size();i++){
if(tp[ng[k][i]]==)continue;
tp[ng[k][i]]=;q.push(ng[k][i]);
}
}
} void build_graph(){
topu();
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(tp[(i-)*m+j]==)continue;
if(sc[i][j] > )AddEdge(,(i-)*m+j,sc[i][j]);
else AddEdge((i-)*m+j,tmp,-sc[i][j]);
for(int k=;k<at[i][j].size();k++){
int now = at[i][j][k];
if(tp[now]==)continue;
AddEdge(now,(i-)*m+j,inf);
}
if(j < m && tp[(i-)*m+j+])AddEdge((i-)*m+j,(i-)*m+j+,inf);
}
}
} void read(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
for(int j=,x;j<=m;j++){
scanf("%d%d",&sc[i][j],&x);
for(int k=,p1,q1;k<=x;k++) {
scanf("%d%d",&p1,&q1);p1++;q1++;
at[i][j].push_back((p1-)*m+q1);
}
}
}
build_graph();
} int dis[maxn*maxn+],cur[maxn*maxn+];
int BFS(){
queue <int> q;
memset(dis,-,sizeof(dis));
q.push(); dis[] = ;
while(!q.empty()){
int k = q.front();q.pop();
for(int i=;i<g[k].size();i++){
edge nxt = e[g[k][i]];
if(nxt.flow > && (dis[nxt.to]==-)){
dis[nxt.to] = dis[k]+; q.push(nxt.to);
}
}
}
return dis[tmp];
} int dfs(int x,int a){
if(x == tmp || a == ) return a;
int flow = ,f;
for(int &i=cur[x];i<g[x].size();i++){
edge &eg = e[g[x][i]];
if(dis[eg.to] > dis[x] && ((f = dfs(eg.to,min(eg.flow,a)))>)){
eg.flow -= f;
e[g[x][i]^].flow += f;
a -= f; flow += f;
if(a == ) break;
}
}
return flow;
} void work(){
int flow;
while(BFS()!=-){
memset(cur,,sizeof(cur));
flow = dfs(,inf);
}
int ans = ;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(dis[(i-)*m+j]!=-) ans += sc[i][j];
}
}
printf("%d",ans);
} int main(){
read();
work();
return ;
}
上一篇:JS-怎么得到局部域中的数据


下一篇:PHP+mysql常用类库