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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2150]部落战争  

2015-01-07 23:02:11|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2150: 部落战争

比较水的题……但是一开始又RE又TLE
然后好像又写麻烦了?为啥我又跑得异常慢……倒数第三QAQ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 50+10;
const int P = N*N*2;
const int M = P*30;
const int MAX = 1E9+10;
int n,m,T,start,end,large,st,all;
int flows[P],dis[P],fa[P];
short map[N][N],v[P];
struct Edge{
int from,to,cap,flow,cost;
Edge(int f=0,int t=0,int c=0,int fl=0,int co=0)
:from(f),to(t),cap(c),flow(fl),cost(co){}
}edges[M];
int scan(){int i=0;scanf("%d",&i);return i;}
struct list{
list(){next = NULL;}
list *next;int d;
void push(int);
}house[M],point[P];int hn;
list *newlist(){
if(hn < M){house[hn]=list();return &house[hn++];}
return new list;
}
void list::push(int a){
list *l = newlist();
l->d = a;
l->next = next;next = l;
}
void AddEdge(int from,int to,int cap,int cost){
point[from].push(T);
edges[T++] = Edge(from,to,cap,0,cost);
point[to].push(T);
edges[T++] = Edge(to,from,0,0,-cost);
}
queue<int>dui;
bool spfa(int &flow,int &cost){
for(int i=1;i<=large;i++)dis[i] = -MAX;
dis[start] = 0;
flows[start] = MAX;
dui.push(start);
v[start] = 1;
while(!dui.empty()){
int now = dui.front();dui.pop();
for(list *i = point[now].next;i!=NULL;i=i->next){
Edge &e = edges[i->d];
if(e.cap > e.flow && dis[now]+e.cost > dis[e.to]){
dis[e.to] = dis[now] + e.cost;
flows[e.to] = min(flows[now],e.cap - e.flow);
fa[e.to] = i->d;
if(!v[e.to]){
v[e.to]=1;
dui.push(e.to);
}
}
}v[now]=0;
}
if(dis[end] == -MAX)return 0;
cost += dis[end]*flows[end];
flow += flows[end];
int now = end;
while(now!=start){
Edge &e = edges[fa[now]];
e.flow += flows[end];
edges[fa[now]^1].flow -= flows[end];
now = e.from;
}
return 1;
}
int calc(int i,int j){return (i-1)*m+j;}
int check(int nn,int mm){
int i,j,G=n*m,now=0;hn = T = 0;
AddEdge(start,st,0,0);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(map[i][j]){
now = calc(i,j);
AddEdge(st,now,1,0);
AddEdge(now,now+G,1,1);
AddEdge(now+G,end,1,0);
int x,y;
x = i+nn;y = j+mm;
if(1<=x&&x<=n&&1<=y&&y<=m&&map[x][y])AddEdge(now+G,calc(x,y),MAX,0);
x = i+mm;y = j+nn;
if(1<=x&&x<=n&&1<=y&&y<=m&&map[x][y])AddEdge(now+G,calc(x,y),MAX,0);
x = i+nn;y = j-mm;
if(1<=x&&x<=n&&1<=y&&y<=m&&map[x][y])AddEdge(now+G,calc(x,y),MAX,0);
x = i+mm;y = j-nn;
if(1<=x&&x<=n&&1<=y&&y<=m&&map[x][y])AddEdge(now+G,calc(x,y),MAX,0);
}
int flow,cost;
flow=cost=0;
while(cost < all){
edges[0].cap++;
spfa(flow,cost);
}
return edges[0].cap;
}
int main(){
//freopen("in.txt","r",stdin);
//printf("%f\n",sizeof(edges)/1024.0/1024);
int i,j,nn,mm;char cc;
n = scan();m = scan();
nn = scan();mm = scan();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);
if(cc=='.')map[i][j] = 1,all++;
}
if(all == 0){printf("%d\n",0);return 0;}
st = n*m*2+1;
start = st+1;
large = end = start + 1;
int ans = 0;
ans=check(nn,mm);
printf("%d\n",ans);
return 0;
}

题解:
费用流
其实就相当于K取方格数的变形,只不过这个题我们需要设置一个超级源点来限制流量。
本来我是想二分答案,然后限制流量检查一下最大流是否等于城市数。
结果T了……
然后发现二分答案实际上完全没有必要,因为跑费用流的时候每次都要进行maxflow次spfa,所以干脆从小往大一边增加流限制一边check,满足了就输出即可。
  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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