首页 > 代码库 > BZOJ 3175 Tjoi2013 攻击装置 二分图最大匹配
BZOJ 3175 Tjoi2013 攻击装置 二分图最大匹配
题目大意:给定一个n*n的网格图,要在0的位置上放置一些攻击装置,其中一个攻击装置的攻击范围是周围8个“日”字形区域,要求不能互相攻击,求最多放置多少个攻击装置
每两个能互相攻击且能放置的点连一条双向边,然后跑二分图最大点独立集即可
4W个点n^2居然没TLE 是数据太弱还是匈牙利算法太强了?
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 210 using namespace std; struct abcd{ int to,next; }table[M*M<<3]; int head[M*M],tot; int n,m,ans; int map[M][M]; int state[M*M],result[M*M],T; const int dx[]={1,1,2,2}; const int dy[]={2,-2,1,-1}; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } bool Hungary(int x) { int i; for(i=head[x];i;i=table[i].next) { if(state[table[i].to]==T) continue; state[table[i].to]=T; if( !result[table[i].to] || Hungary(result[table[i].to]) ) { result[table[i].to]=x; return true; } } return false; } int main() { int i,j,k; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%1d",&map[i][j]); if(map[i][j]==1) map[i][j]=-1; else map[i][j]=++m; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(~map[i][j]) for(k=0;k<4;k++) { int xx=i+dx[k]; int yy=j+dy[k]; if(xx<=0||yy<=0||xx>n||yy>n) continue; if(map[xx][yy]==-1) continue; Add(map[i][j],map[xx][yy]); Add(map[xx][yy],map[i][j]); } ans=m<<1; for(i=1;i<=m;i++) { ++T; if( Hungary(i) ) --ans; } cout<<(ans>>1)<<endl; }
BZOJ 3175 Tjoi2013 攻击装置 二分图最大匹配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。