当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 计蒜客实践题 - A1542

计蒜客实践题 - A1542

2020年08月05日  | 移动技术网IT编程  | 我要评论

计蒜客 - 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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网