等我研究出来链式前向星的写法再回来更新，先贴看了其他博客的
（棋盘的长宽 为集合A 和 集合B）
为保证 车不相互打架 集合AB二分匹配
删除其中一条边 如果与标准的结果相同 则不是重要边，反之sum++；
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<map> #include<cmath> #include<cstdio> #include<queue> typedef long long ll; const int mod = 1e9+7; const int maxn = 1000000; const int inf = 0x3f3f3f3f; using namespace std; int mp[202][202],n,m,k; int l[202],r[202]; int path[202]; bool vis[202]; bool dfs(int u) { for(int i=1;i<=m;i++) { if(mp[u][i]) { if(!vis[i]) { vis[i] = true; if(path[i]==-1||dfs(path[i])) { path[i] = u; return true; } } } } return false; } int hungary() { int ret = 0; memset(path,-1,sizeof(path)); for(int i = 1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ret++; } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int cas = 1; while(cin>>n>>m>>k) { memset(mp,0,sizeof(mp)); for(int i=0;i<k;i++) { cin>>l[i]>>r[i]; mp[l[i]][r[i]] = 1; } int bz = hungary(); int ans = 0; for(int i = 0;i<k;i++) { mp[l[i]][r[i]] = 0; //删边 int tmp = hungary(); if(tmp != bz)ans++; //如果！= 那此边为重要边 mp[l[i]][r[i]] = 1; } printf("Board %d have %d important blanks for %d chessmen.\n",cas++,ans,bz); } }
原文：https://www.cnblogs.com/lightWh1te/p/13414368.html
