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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3175][Tjoi2013]攻击装置  

2014-12-15 17:45:55|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3175: [Tjoi2013]攻击装置

大水题……
感觉会T结果A了
结果还WA了一次
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
using namespace std;
const int N = 200+10;
const int P = N*N;
const int M = P*10*2;
const int MAX = 1E9;
const int dir[8][2] = {{-1,-2},{-1,2},{1,-2},{1,2},{-2,-1},{-2,1},{2,-1},{2,1}};
int n,m,T,start,end,large,level[P];
short map[N][N];
int min(const int &a,const int &b){return a>b?b:a;}
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];
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],*cur[P];
void AddEdge(int from,int to,int cap){
//printf("%d->%d\n",from,to);
point[from].push(T);
edges[T++] = Edge(from,to,cap,0);
point[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;
dui.push(start);
level[start] = 1;
while(!dui.empty()){
int now = dui.front();dui.pop();
for(Point *i = point[now].next;i!=NULL;i=i->next){
//printf("jaj");
Edge &e = edges[i->d];
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(level[e.to] == level[now]+1 && (l=dfs(e.to,min(a,e.cap-e.flow)))){
e.flow += l;
edges[i->d^1].flow -= l;
a -= l;
flow += l;
if(!a)break;
}
}return flow;
}
int dinic(){
int flow=0;
while(bfs()){
//printf("once");
int flag;
for(int i=1;i<=large;i++)cur[i] = point[i].next;
while((flag = dfs(start,MAX)))
flow += flag;
}return flow;
}
int calc(int i,int j){return (i-1)*n + j;}
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j,k,a,b=0;char cc;
n = scan();
//memset(map,-1,sizeof(map));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf(" %c",&cc);
map[i][j] = !(cc-'0');
if(map[i][j])b++;
}
a=0;
start = n*n + 1;
large = end = start + 1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(map[i][j]){
a = calc(i,j);
if((i^j)&1)AddEdge(start,a,1);
else AddEdge(a,end,1);
for(k=0;k<8;k++){
int x,y;
x = i+dir[k][0];y = j+dir[k][1];
if(!(1<=x && x<=n && 1<=y && y<=n))continue;
if(!map[x][y])continue;
//printf("%d %d %d %d\n",i,j,x,y);
//if(a == calc(x,y)) printf("%d %d %d %d\n",i,j,x,y);
if((i^j)&1)AddEdge(a,calc(x,y),MAX);
//else AddEdge(calc(x,y),a,MAX);
}
}
a = b-dinic();
printf("%d\n",a);
return 0;
}

题解:
很显然是最大独立集……
但是直接用匈牙利是n^6,显然会T
所以考虑用复杂度非常奇怪的网络流来做


我居然忘了最大独立集建图是单向边了
弱到一定境界……

好奇怪[BZOJ3175][Tjoi2013]攻击装置 - 时光机 - 时光机TimeMachine
  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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