题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=746
好吧，我承认我看的是题解……
推荐这家的题解：https://oi.men.ci/cogs-746/
自己来说的话，就是搞一搞二分图？
染色之后，发现有冲突的点都在不同的集合内
于是连边，跑最小割即可
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 40000+9;
const int M = N*10;
const int L = 200+9;
const int INF = 10000000;
int head[N],nxt[M],to[M],flow[M],cur[N],dis[N];
int n,m,mat[L][L],vout,S,T;
int dx[]={0,2,1,-1,-2,-2,-1,1,2};
int dy[]={0,1,2,2,1,-1,-2,-2,-1};
queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
#define id(x,y) ((x)+((y)-1)*n)
inline void Add_Edge(int u, int v, int f){
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}
inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
dis[to[i]] = dis[w] + 1, que.push(to[i]);
}
return ~dis[T];
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
if (!f) break;
}
return ret;
}
}
inline int Dinic(){
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(head));
ret += DFS(S,INF);
}
return ret;
}
int main(){
freopen("knight.in","r",stdin);
freopen("knight.out","w",stdout);
n = read(); m = read(); S = 0; T = N-1; vout = n*n;
for (int i=1,x,y;i<=m;i++) x = read(), y = read(), mat[x][y] = 1, vout--;
for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) if (!mat[i][j])
if ((i+j)&1) {
Add_Edge(S,id(i,j),1);
for (int k=1,x,y;k<=8;k++) {
x = i + dx[k]; y = j + dy[k];
if (1 <= x && x <= n && 1 <= y && y <= n && !mat[x][y])
Add_Edge(id(i,j),id(x,y),INF);
}
} else Add_Edge(id(i,j),T,1);
vout -= Dinic();
printf("%d\n",vout);
return 0;
}
Hey there! I know this is somewhat off topic but
I was wondering which blog platform are you using for this website?
I’m getting fed up of WordPress because I’ve had issues with hackers and I’m looking at alternatives for another platform.
I would be fantastic if you could point me in the direction of a good platform.
I delight in, cause I found just what I used to be taking a look for.
You have ended my four day long hunt! God Bless you man. Have a great day.
Bye
Hello! I simply wish to offer you a big thumbs
up for the excellent info you have right here on this post.
I’ll be returning to your blog for more soon.
My brother recommended I might like this blog. He was totally right.
This post actually made my day. You cann’t imagine simply how much time I
had spent for this info! Thanks!
Yes! Finally something about ps4 games.
Terrific article! This is the kind of info that are supposed to be shared across the
net. Disgrace on Google for no longer positioning this submit higher!
Come on over and visit my website . Thank you =)
It’s remarkable to pay a quick visit this web
page and reading the views of all colleagues regarding this article, while
I am also eager of getting knowledge.
Wow, amazing weblog format! How lengthy have you been blogging for?
you made blogging glance easy. The full look of your site is
fantastic, as smartly as the content material!
Can I just say what a relief to discover somebody that actually understands what
they’re talking about over the internet.
You definitely realize how to bring an issue to light and make it important.
A lot more people must read this and understand
this side of your story. It’s surprising you are not more popular since you definitely have
the gift.
My brother suggested I might like this web site. He was entirely right.
This post truly made my day. You cann’t imagine just how much
time I had spent for this info! Thanks!
Wow, this post is fastidious, my sister is analyzing these things, therefore I am going to let know her.
It’s very easy to find out any topic on net as compared to textbooks, as I found this piece of writing at this site.
Very shortly this website will be famous amid all blogging and
site-building visitors, due to it’s pleasant articles or reviews
For most up-to-date news you have to visit world wide web and on internet I found
this website as a most excellent website for latest updates.
Hi, just wanted to say, I loved this blog post. It was practical.
Keep on posting!
There is definately a lot to know about this issue.
I really like all of the points you made.
Can you tell us more about this? I’d care to find out some
additional information.
Howdy are using WordPress for your site platform?
I’m new to the blog world but I’m trying to get started and create my own. Do you
require any coding expertise to make your own blog?
Any help would be greatly appreciated!
I visited multiple blogs but the audio feature for audio songs existing at this site is truly superb.
I was wondering if you ever thought of changing the layout of your website?
Its very well written; I love what youve got to say. But maybe you could a little more
in the way of content so people could connect with it better.
Youve got an awful lot of text for only having one or 2 pictures.
Maybe you could space it out better?
Truly no matter if someone doesn’t understand after that its up to other users that
they will help, so here it happens.