【wikioi】1922 骑士共存问题（网络流/二分图匹配）

时间：2023-03-08 17:04:00

用匈牙利tle啊喂？和网络流不都是n^3的吗（匈牙利O(nm)， isap O(n^2m) 但是isap实际复杂度很优的（二分图匹配中，dinic是O(sqrt(V)*E)，不知道isap是不是一样。。。）。。）。。。。 （更新：what！！！！！！发现个无语的问题，。！！！！结构比数组快啊orz，这节奏不对啊。。。。以后图都写结构的节奏啊。。。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define read(a) scanf("%d", &a)

#define print(a) printf("%d", a)

#define num(i, j) ((i-1)*n+j)

#define who(i, j) (i%2==j%2)

#define arr(a, n) for1(i, 1, n) { for1(j, 1, n) print(a[i][j]); printf("\n"); }

#define arr2(a, n) for1(i, 1, n) print(a[i]); printf("\n")

inline int getnum() { int ret=0; char c; int k=1; for(c=getchar(); c<'0' || c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }

const int fx[8]={1, 1, 2, 2, -1, -1, -2, -2}, fy[8]={-2, 2, -1, 1, -2, 2, -1, 1};

const int N=205*205, M=N*8+100;

int ihead[N], inext[M], to[M], cnt, x[N], cont, ly[N], n, m, mm[205][205];

bool vis[N];

inline void add(const int &u, const int &v) {

	inext[++cnt]=ihead[u]; ihead[u]=cnt; to[cnt]=v;

}

bool ifind(const int &x) {

	vis[x]=true;

	for(int i=ihead[x]; i; i=inext[i]) if(!vis[to[i]]) {

		vis[to[i]]=true;

		if(!ly[to[i]] || ifind(ly[to[i]])) {

			ly[to[i]]=x;

			return true;

		}

	}

	return false;

}

int main() {

	read(n); read(m);

	int a, b, nx, ny, ans=0;

	rep(i, m) read(a), read(b), mm[a][b]=1;

	for1(i, 1, n) for1(j, 1, n) if(!mm[i][j] && who(i, j)) {

		rep(k, 8) {

			nx=i+fx[k], ny=j+fy[k];

			if(mm[nx][ny] || nx<1 || nx>n || ny<1 || ny>n) continue;

			add(num(i, j), num(nx, ny));

		}

		x[++cont]=num(i, j);

	}

	for1(i, 1, cont) {

		CC(vis, 0);

		if(ifind(x[i])) ans++;

	}

	print(n*n-ans-m);

	return 0;

}

囧，，只能码网络流了。

tle了无数次的ac orz（和上面一样，数组和结构的问题。。。

【wikioi】1922 骑士共存问题（网络流/二分图匹配）

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define read(a) a=getnum()

#define print(a) printf("%d", a)

#define num(i, j) ((i-1)*n+j)

#define who(i, j) (!((i+j)%2))

#define arr(a, n) for1(i, 1, n) { for1(j, 1, n) print(a[i][j]); printf("\n"); }

#define arr2(a, n) for1(i, 1, n) print(a[i]); printf("\n")

inline int getnum() { int ret=0; char c; int k=1; for(c=getchar(); c<'0' || c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }

const int fx[8]={1, 1, 2, 2, -1, -1, -2, -2}, fy[8]={2, -2, 1, -1, 2, -2, 1, -1};

const int N=205*205, M=500001, oo=~0u>>1;

int ihead[N], cnt=1, n, m;

int gap[N], p[N], d[N], cur[N];

bool mm[205][205];

struct dd { int to, from, cap, next; }e[M];

inline void add(const int &u, const int &v, const int &c) {

	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].from=u; e[cnt].to=v; e[cnt].cap=c;

	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].from=v; e[cnt].to=u; e[cnt].cap=0;

}

int isap(const int &s, const int &t, const int &n) {

	int flow=0, u=s, f, i, v;

	for1(i, 0, n) cur[i]=ihead[i];

	gap[0]=n;

	while(d[s]<n) {

		for(i=cur[u]; i; i=e[i].next) if(e[i].cap && d[u]==d[v=e[i].to]+1) break;

		if(i) {

			cur[u]=i; p[v]=i; u=v;

			if(u==t) {

				for(f=oo; u!=s; u=e[p[u]].from) f=min(f, e[p[u]].cap);

				for(u=t; u!=s; u=e[p[u]].from) e[p[u]].cap-=f, e[p[u]^1].cap+=f;

				flow+=f;

			}

		}

		else {

			if(!(--gap[d[u]])) break;

			d[u]=n;

			cur[u]=ihead[u];

			for(i=cur[u]; i; i=e[i].next) if(e[i].cap && d[u]>d[e[i].to]+1)

				d[u]=d[e[i].to]+1;

			++gap[d[u]]; if(u!=s) u=e[p[u]].from;

		}

	}

	return flow;

}

int main() {

	read(n); read(m);

	int a, b, nx, ny, s=0, t=n*n+5;

	rep(i, m) read(a), read(b), mm[a][b]=1;

	for1(i, 1, n) for1(j, 1, n) if(!mm[i][j]) {

		if(who(i, j)) {

			rep(k, 8) {

				nx=i+fx[k], ny=j+fy[k];

				if(mm[nx][ny] || nx<1 || nx>n || ny<1 || ny>n) continue;

				add(num(i, j), num(nx, ny), oo);

			}

			add(s, num(i, j), 1);

		}

		else add(num(i, j), t, 1);

	}

	print(n*n-isap(s, t, t+1)-m);

	return 0;

}

题目描述 Description

在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。

【wikioi】1922 骑士共存问题（网络流/二分图匹配）

对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
士，使得它们彼此互不攻击。

输入描述
Input Description

第一行有2 个正整数n 和m (1<=n<=200, 0<=m<n^2)，
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
碍的方格坐标。

输出描述
Output Description

将计算出的共存骑士数输出

样例输入
Sample Input

3 2

1 1

3 3

样例输出
Sample Output

5

数据范围及提示
Data Size & Hint

详见试题

相关文章