注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1565][NOI2009]植物大战僵尸  

2014-12-10 19:10:55|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1565: [NOI2009]植物大战僵尸

最近光顾着颓,懒得发blog都快长草了……
这个题因为一点问题搞了好久
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 30+5;
const int P = N*N;
const int M = P*P*2;
const int MAX = 1E9;
typedef long long ll;
int n,m,T,start,end,large;
ll all;
int level[P],area[N][N],data[P],du[P];
short v[P];
struct Point{
Point(){next = NULL;}
Point *next;int d;
void push(int a){
Point *l = new Point;
l->d =a ;
l->next = next;next = l;
}
}point[P],map[P],*cur[P];
struct Edge{
int from,to,cap,flow;
Edge(){}
Edge(int f,int t,int c,int fl):from(f),to(t),cap(c),flow(fl){}
}edges[M];
void AddEdge(int from, int to, int cap){
map[from].push(T);
edges[T++] = Edge(from,to,cap,0);
map[to].push(T);
edges[T++] = Edge(to,from,0,0);
}
queue<int>dui;
bool bfs(){
for(int i=1;i<=large;i++)level[i] = 0;
level[start] = 1;
dui.push(start);
while(!dui.empty()){
int now = dui.front();dui.pop();
for(Point *i = map[now].next;i!=NULL;i=i->next){
Edge &e = edges[i->d];
if(!v[e.to])continue;
if(!level[e.to] && e.cap > e.flow){
level[e.to] = level[now] + 1;
dui.push(e.to);
}
}
}return level[end]!=0;
}
int dfs(int now,int a){
if(now == end || !a)return a;
int flow=0,l;
for(Point *&i = cur[now];i!=NULL;i=i->next){
Edge &e = edges[i->d];
if(!v[e.to])continue;
if(level[e.to]-1 == level[now] && (l=dfs(e.to,min(e.cap - e.flow,a)))){
a -= l;
e.flow += l;
edges[i->d^1].flow -= l;
flow += l;
if(!a)break;
}
}return flow;
}
int dinic(){
int flow=0;
while(bfs()){
int flag;
for(int i=1;i<=large;i++)cur[i] = map[i].next;
while((flag = dfs(start,MAX)))
flow += flag;
}return flow;
}
int scan(){int i=0;scanf("%d",&i);return i;}
int calc(int i, int j){return (i-1)*m+j;}
int main(){
//freopen("in.in","r",stdin);
int i,j,a,b,PP=0,k,kn;
n = scan();m = scan();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
PP++;
//if(PP == 16)printf("haha");
if(j>1){
point[PP].push(PP-1);
//point[PP-1].push(PP);
//du[PP]++;
du[PP-1]++;
//printf("%d\n",PP);
AddEdge(PP-1,PP,MAX);
/*
point[PP].push(PP-1);
du[PP-1]++;
//printf("%d\n",PP);
AddEdge(PP,PP-1,MAX);*/
}

data[PP] = scan();
kn = scan();
for(k=1;k<=kn;k++){
a = scan()+1;b = scan()+1;
a=calc(a,b);
point[PP].push(a);
//point[a].push(PP);
//du[PP]++;
du[a]++;
AddEdge(a,PP,MAX);
}
}
//for(i=1;i<=n*m;i++) printf("%d ",du[i]);printf("\n");
//TP sort(
for(i=1;i<=n*m;i++)
if(!du[i])dui.push(i);
while(!dui.empty()){
int now = dui.front();dui.pop();
//printf("[%d]\n",data[now]);
v[now] = 1;
if(data[now] > 0)all += data[now];
for(Point *i = point[now].next;i!=NULL;i=i->next){
du[i->d]--;
if(!du[i->d])dui.push(i->d);
}
}
//for(i=1;i<=n*m;i++) printf("%d ",du[i]);printf("\n");
//for(i=1;i<=n*m;i++) printf("%d ",du[i]);
start = calc(n,m)+1;
large = end = start + 1;
for(i=1;i<=n*m;i++)
if(v[i]){
if(data[i] > 0)AddEdge(start,i,data[i]);
else if(data[i] < 0)AddEdge(i,end,-data[i]);
}
v[start] = v[end] = 1;
a = dinic();
//printf("%d\n",a);
printf("%lld",all-a);
return 0;
}

题解:
拓扑排序+网络流。
首先可以转化为最大权闭合子图的模型,但是这个图里有环,所以通过拓扑排序先去掉环。
需要注意的是,拓扑排序的图需要是网络流的反图,自己想想为什么。
  评论这张
 
阅读(158)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017