#6226. 「網絡流 24 題」騎士共存問題

題目描述

在一個?n×n\text{n} \times \text{n}n×n?個方格的國際象棋棋盤上，馬（騎士）可以攻擊的棋盤方格如圖所示。棋盤上某些方格設置了障礙，騎士不得進入。

對于給定的?n×n\text{n} \times \text{n}n×n?個方格的國際象棋棋盤和障礙標志，計算棋盤上最多可以放置多少個騎士，使得它們彼此互不攻擊。

輸入格式

第一行有兩個正整數?n\text{n}n?和?m\text{m}m?(1≤n≤200,0≤m≤n2?1)( 1 \leq n \leq 200, 0 \leq m \leq n^2 - 1 )(1≤n≤200,0≤m≤n?2???1)?分別表示棋盤的大小和障礙數。

輸出格式

輸出計算出的共存騎士數。

樣例

樣例輸入

3 2 1 1 3 3

樣例輸出

5

數據范圍與提示

1≤n≤2001\leq n\leq 2001≤n≤200

0≤m≤n2?10 \leq m \leq n^2-10≤m≤n?2???1

?

?

/*加了當前弧優化和讀入優化，快了不少 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define maxn 40010 #define INF 1000000000 int n,m,head[maxn],dis[maxn],num=1,S,T,cur[maxn]; bool vis[maxn],mark[maxn]; struct node{int to,pre,v;}e[maxn*50]; using namespace std; int count(int x,int y){return n*(x-1)+y;} void Insert(int from,int to,int v){e[++num].to=to;e[num].v=v;e[num].pre=head[from];head[from]=num;e[++num].to=from;e[num].v=0;e[num].pre=head[to];head[to]=num; } bool bfs(){for(int i=S;i<=T;i++)dis[i]=-1,cur[i]=head[i];queue<int>q;q.push(S);dis[S]=0;while(!q.empty()){int now=q.front();q.pop();for(int i=head[now];i;i=e[i].pre){int to=e[i].to;if(e[i].v>0&&dis[to]==-1){dis[to]=dis[now]+1;if(to==T)return 1;q.push(to);}}}return dis[T]!=-1; } int dinic(int x,int flow){if(x==T||flow==0){return flow;}int rest=flow;for(int &i=cur[x];i;i=e[i].pre){int to=e[i].to;if(dis[to]==dis[x]+1&&e[i].v>0){int delta=dinic(to,min(rest,e[i].v));e[i].v-=delta;e[i^1].v+=delta;rest-=delta;}}return flow-=rest; } bool check(int x,int y){if(x<=n&&x>=1&&y<=n&&y>=1&&!mark[count(x,y)])return 1;return 0; } int qread(){int i=0,j=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')j=-1;ch=getchar();}while(ch<='9'&&ch>='0'){i=i*10+ch-'0';ch=getchar();}return i*j; } int main(){n=qread();m=qread();S=0,T=n*n+1;int x,y;for(int i=1;i<=m;i++){x=qread();y=qread();mark[count(x,y)]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mark[count(i,j)])continue;if((i+j)&1){Insert(S,count(i,j),1);if(check(i-1,j-2))Insert(count(i,j),count(i-1,j-2),1);if(check(i-1,j+2))Insert(count(i,j),count(i-1,j+2),1);if(check(i+1,j-2))Insert(count(i,j),count(i+1,j-2),1);if(check(i+1,j+2))Insert(count(i,j),count(i+1,j+2),1);if(check(i-2,j-1))Insert(count(i,j),count(i-2,j-1),1);if(check(i-2,j+1))Insert(count(i,j),count(i-2,j+1),1);if(check(i+2,j-1))Insert(count(i,j),count(i+2,j-1),1);if(check(i+2,j+1))Insert(count(i,j),count(i+2,j+1),1);}else Insert(count(i,j),T,1);}}int ans=0;while(bfs())ans+=dinic(S,INF);printf("%d",n*n-ans-m); }

?

轉載于:https://www.cnblogs.com/thmyl/p/8939760.html

總結

以上是生活随笔為你收集整理的loj #6226. 「网络流 24 题」骑士共存问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。