首页 > 代码库 > 【最大独立集】BZOJ3175- [Tjoi2013]攻击装置
【最大独立集】BZOJ3175- [Tjoi2013]攻击装置
【题目大意】
给定一个01矩阵，其中你可以在0的位置放置攻击装置。每一个攻击装置（x,y）都可以按照“日”字攻击其周围的 8个位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1), (x+1,y+2),(x+2,y+1)。
求在装置互不攻击的情况下，最多可以放置多少个装置。
【思路】
最大独立集=总点数-最大二分图匹配
我们都知道最大独立集一般用在二分图里…所以把每个点看作两个点，一个是从它出发，一个是抵达它。实际操作的时候因为会连正反边，不需要进行拆点。最大独立集=总点数-最大二分图匹配/2。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=205; 4 int n,maps[MAXN][MAXN]; 5 int lk[MAXN*MAXN],vis[MAXN*MAXN]; 6 vector<int> E[MAXN*MAXN]; 7 8 int check(int x,int y) 9 {10 if (x>=1 && x<=n && y>=1 && y<=n && maps[x][y]) return 1;else return 0;11 }12 13 int id(int x,int y){return ((x-1)*n+y);}14 15 void addedge(int u,int v)16 {17 E[u].push_back(v);18 }19 20 int find(int u)21 {22 for (int i=E[u].size()-1;i>=0;i--)23 {24 int v=E[u][i];25 if (!vis[v])26 {27 vis[v]=1;28 if (!lk[v]|| find(lk[v]))29 {30 lk[v]=u;31 return 1;32 }33 }34 }35 return 0;36 }37 38 void init()39 {40 scanf("%d",&n);41 for (int i=1;i<=n;i++)42 {43 char str[MAXN];44 scanf("%s",str);45 for (int j=0;j<n;j++)46 if (str[j]==‘0‘) maps[i][j+1]=1;else maps[i][j+1]=0;47 }48 for (int i=1;i<=n;i++)49 for (int j=1;j<=n;j++)50 if (maps[i][j]==1)51 {52 if (check(i-1,j-2)) addedge(id(i,j),id(i-1,j-2));53 if (check(i-2,j-1)) addedge(id(i,j),id(i-2,j-1));54 if (check(i+1,j-2)) addedge(id(i,j),id(i+1,j-2));55 if (check(i+2,j-1)) addedge(id(i,j),id(i+2,j-1));56 if (check(i-1,j+2)) addedge(id(i,j),id(i-1,j+2));57 if (check(i-2,j+1)) addedge(id(i,j),id(i-2,j+1));58 if (check(i+1,j+2)) addedge(id(i,j),id(i+1,j+2));59 if (check(i+2,j+1)) addedge(id(i,j),id(i+2,j+1));60 }61 }62 63 void solve()64 {65 memset(lk,0,sizeof(lk));66 int sum=0,ans=0;67 for (int i=1;i<=n;i++)68 for (int j=1;j<=n;j++)69 {70 if (maps[i][j]==1)71 {72 int x=id(i,j);73 memset(vis,0,sizeof(vis));74 sum++;75 if (find(x)) ans++;76 }77 }78 printf("%d",sum-ans/2);//不要忘记了除以2 79 }80 81 int main()82 {83 init();84 solve();85 }
【最大独立集】BZOJ3175- [Tjoi2013]攻击装置
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。