计蒜客 - A1542
#include<map> #include<set> #include<list> #include<cmath> #include<queue> #include<stack> #include<cstdio> #include<string> #include<vector> #include<cstdlib> #include<cstring> #include<fstream> #include<iomanip> #include<sstream> #include<iostream> #include<algorithm> #define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define lowbit(x) (x&-x) #define debug cout<<"What fuck!!"<<endl using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=1e3+10; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; int k,n,m; int vis[maxn]; int man[maxn]; int love[maxn][maxn]; bool find(int x){ for(int j=1;j<=n;++j){ if(love[x][j]==1&&vis[j]==0){ vis[j]=1; if(man[j]==0||find(man[j])){ man[j]=x;//与男生j匹配的为女生j; return true; } } } return false; } void floyd(){ for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(love[i][k]&&love[k][j]) love[i][j]=1; } } } } int main(){ fcio; int T; while(cin>>T){ while(T--){ cin>>n>>m; memset(man,0,sizeof man); memset(love,0,sizeof love); int ans=0; for(int i=0;i<m;++i){ int x,y; cin>>x>>y; love[x][y]=1; } floyd(); for(int i=1;i<=n;++i){ memset(vis,0,sizeof vis); if(find(i)) ans++; } cout<<n-ans<<endl; } } return 0; } 本文地址：https://blog.csdn.net/xgz__/article/details/107771837
