链接
http://acm.hdu.edu.cn/showproblem.php?pid=1281
题意
对一个 $N*M$ 的棋盘,在格子里放尽量多国际象棋里的“车”,并且使得他们不能互相攻击,但是限制了只有某些格子才可以放。
某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点。
求有多少个这样的重要点?
思路
先对行列求二分图最大匹配。
每次删除一条匹配边,重新匹配,若匹配数小于原先匹配数,说明删除边对应的点是重要点。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include <bits/stdc++.h> #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(),(x).end() #define PB push_back #define EB emplace_back #define MP make_pair #define FI first #define SE second using namespace std; typedef double DB; typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<PII> VPII;
const int N=205; int n,m,k,match[N],oldmatch[N]; bool st[N],vis[N][N]; VI g[N]; bool dfs(int u) { for(int v=1;v<=m;v++) { if(!vis[u][v]||st[v]) continue; st[v]=true; if(match[v+n]==-1||dfs(match[v+n])) { match[u]=v+n; match[v+n]=u; return true; } } return false; } int hungary() { for(int i=1;i<=n+m;i++) match[i]=-1; int res=0; for(int i=1;i<=n;i++) { if(match[i]!=-1) continue; for(int j=1;j<=n+m;j++) st[j]=false; if(dfs(i)) res++; } return res; } int main() { int cs=0; while(~scanf("%d%d%d",&n,&m,&k)) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) vis[i][j]=false; for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); vis[x][y]=true; } int mx=hungary(),res=0; for(int i=1;i<=n+m;i++) oldmatch[i]=match[i]; for(int i=1;i<=n;i++) { vis[i][oldmatch[i]-n]=false; if(hungary()<mx) res++; vis[i][oldmatch[i]-n]=true; } printf("Board %d have %d important blanks for %d chessmen.\n",++cs,res,mx); } return 0; }
|