匈牙利算法实现二分匹配入门题目
以我初步了解就是不断找增广路,扩大匹配
#include <algorithm> #include <bitset> #include <cfloat> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <iostream> #include <iterator> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <utility> #include <vector> using namespace std; typedef pair<int,int> pii; typedef long long ll; char s[10]; int n,mp[1010][1010],vi[1010],match[1010]; int dfs(int k) { for(int i=0;i<n;i++) { if(mp[k][i]&&!vi[i]) { vi[i]=1;//标记为1之后无需标记为0回溯,因为增广路不可能再用到这个点了,否则超时。 int t=match[i]; match[i]=k; if(t==-1||dfs(t))return 1; match[i]=t; } } return 0; } int max_match() { int ans=0; memset(match,-1,sizeof(match)); for(int i=0;i<n;i++) { memset(vi,0,sizeof(vi)); if(dfs(i)) ans++; } return ans; } int main() { while(1==scanf("%d",&n)) { int a,b,c; memset(mp,0,sizeof(mp)); for(int i=0;i<n;i++) { scanf("%d: (%d)",&a,&b); for(int j=0;j<b;j++) { scanf("%d",&c); mp[a][c]=1; } } printf("%d\n",n-max_match()/2); } return 0; }