騎士放置 Page435 最大獨立集
- 棋盤問題首先黑白染色
- 馬的哈密頓移動距離是3，必然是從白走到黑或者從黑走到白
- 這題折騰了倆小時，就因為遞回那里懶得寫int，直接用了個全域變數，根本檢查不出來，人傻了
代碼:
const int maxn=2e4+7;
const int INF=0x3f3f3f3f;
const ll INFF=1e18;
bool mark[120][120],vis[maxn];
int linker[maxn],n,m,t,x,y;
int xx[8]={1,1,-1,-1,2,2,-2,-2};
int yy[8]={2,-2,2,-2,1,-1,1,-1};
int f(int x,int y){return m*(x-1)+y;}
vector<int> V[maxn];
bool dfs(int x)
{
repp(i,0,V[x].size())
{
int y=V[x][i];//這邊一定要加int，遞回函式里面的變數得定義
if (vis[y])continue;
vis[y]=true;
if (!linker[y]||dfs(linker[y]))
{
linker[y]=x;
return true;
}
}
return false;
}
int count_()
{
int ans=0;
rep(i,1,n)
{
rep(j,1,m)
{
if ((i+j)%2==0)
{
mem(vis,false);
if (dfs(f(i,j)))ans++;
}
}
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
rep(T,1,t)
{
scanf("%d%d",&x,&y);
mark[x][y]=true;
}
rep(i,1,n)
{
rep(j,1,m)
{
if (mark[i][j])continue;
rep(k,0,7)
{
x=i+xx[k],y=j+yy[k];
if (x<1||y<1||x>n||y>m||mark[x][y])continue;
if ((i+j)%2==0)V[f(i,j)].pb(f(x,y));
}
}
}
W(n*m-t-count_());
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/154389.html
標籤：其他