「RQNOJ140」寻找代表元
题目描述
温中一共有n个社团，分别用1到n编号。
温中一共有m个人，分别用1到m编号。每个人可以参加一个或多个社团，也可以不参加任何社团。
每个社团都需要选一个代表。我们希望更多的人能够成为代表。
输入格式第一行输入两个数n和m。以下n行每行若干个数，这些数都是不超过m的正整数。其中第i行的数表示社团i的全部成员。每行用一个0结束。
数据范围：
n,m<=200
输出格式输出最多的能够成为代表的人数。
样例输入
4 4
1 2 0
1 2 0
1 2 0
1 2 3 4 0
样例输出
3
代码
匈牙利算法，但是注意，不能用link命名数组，否则报错
|
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 |
//其中n,m分别为2部图两边节点的个数，两边的节点分别用1..n,1..m编号 //g[x][y]表示x,y两个点之间有边相连 //y[i]记录的是y中的i节点是否被访问过. //lk[y]记录的是当前与y节点相连的x节点 #include<iostream> #include<cstring> using namespace std; int n,m,y[201],g[201][201],lk[201],x,ans=0; bool find(int v) { for(int i=1;i<=m;i++) if(g[v][i]&&!y[i]) { y[i]=1; if(lk[i]==0||find(lk[i])) { lk[i]=v; return 1; } } return 0; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>x; while(x!=0){g[i][x]=1;cin>>x;} } for(int i=1;i<=n;i++) { memset(y,0,sizeof(y)); if(find(i))ans++; } cout<<ans; return 0; } |
Subscribe
计数器 9318365
OI 课件=>
OI 课件=>