程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3175【TJOI2013】攻擊裝置

bzoj3175【TJOI2013】攻擊裝置

編輯:關於C++

Description

給定一個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)
求在裝置互不攻擊的情況下,最多可以放置多少個裝置。

Input

第一行一個整數N,表示矩陣大小為N*N。接下來N行每一行一個長度N的01串,表示矩陣。 

Output

一個整數,表示在裝置互不攻擊的情況下最多可以放置多少個裝置。

Sample Input

3
010
000
100 

Sample Output

HINT

100%數據 N<=200 

二分圖最大點獨立集裸題

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 40005
using namespace std;
int n,cnt,ans,head[maxn],match[maxn];
int dx[8]={-1,-2,1,2,-1,-2,1,2},dy[8]={-2,-1,-2,-1,2,1,2,1};
bool f[205][205],vst[maxn];
char s[205];
struct edge_type{int next,to;}e[maxn*8];
inline int num(int x,int y)
{
	return (x-1)*n+y;
}
inline void add_edge(int x,int y)
{
	e[++cnt]=(edge_type){head[x],y};
	head[x]=cnt;
}
inline bool dfs(int x)
{
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if (!vst[y])
		{
			vst[y]=true;
			if (!match[y]||dfs(match[y]))
			{
				match[y]=x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d",&n);
	F(i,1,n)
	{
		scanf("%s",s+1);
		F(j,1,n) f[i][j]=s[j]=='0';
	}
	F(i,1,n) F(j,1,n) if (f[i][j]&&(i+j)%2) F(k,0,7)
	{
		int x=i+dx[k],y=j+dy[k];
		if (x<1||y<1||x>n||y>n) continue;
		if (!f[x][y]) continue;
		add_edge(num(i,j),num(x,y));
	}
	F(i,1,n) F(j,1,n) if (f[i][j]) ans++;
	F(i,1,n) F(j,1,n) if (f[i][j]&&(i+j)%2)
	{
		memset(vst,false,sizeof(vst));
		if (dfs(num(i,j))) ans--;
	}
	printf("%d\n",ans);
	return 0;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved