CH - 6802 車的放置(二分图最大匹配)

题目链接：点击查看

题目大意：给出一个n*m的棋盘，其中有t个点是禁止放置的，我们需要在其余的点上尽可能多的放置车，并且互不冲突，车的攻击规则和中国象棋中的车一样，只能攻击同一行和同一列中的所有棋子，问满足的情况下最多能放多少车

题目分析：首先对于每一个车，我们只能放在(x,y)这样一个点，并不能既放在x1行，也放在x2行，所以这样行和列就组成了一个二分图，我们对于所有可以放置的点对其行和列建边然后跑一遍匈牙利就好了

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=210;int n,m,t;int match[N];bool maze[N][N],vis[N],can[N][N];bool dfs(int x) {for(int i=1;i<=m;i++){if(maze[x][i]&&!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d%d",&n,&m,&t);while(t--){int x,y;scanf("%d%d",&x,&y);can[x][y]=true;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(can[i][j])continue;maze[i][j]=true;}int ans=0;for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}printf("%d\n",ans);return 0; }

 

总结

以上是生活随笔为你收集整理的CH - 6802 車的放置(二分图最大匹配)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。