【NYOJ1291】不是匹配

╰+攻爆jí腚メ 2022-09-25 11:22 157阅读 0赞

## 不是匹配 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 2

描述

有N个人,N个活动， 每个人只会对2个或者3个活动感兴趣，

每个活动也只有两个人或者两个活动对它兴趣，每个人参加一个

感兴趣的活动需要一天 ，且当天该活动被参加时，其他的人不能参加

如果每个人都参加完自己有兴趣的活动，应当怎样安排使得所用总天数时间最短

2<= N <=1000， 1<=m<=1000;

输入

一个数T 表示T 组数据  
每组一个N表示人数，编号1 -- N , 一个数 m ,接下来m 行每个两个数  
x,y， 表示第 x 个人对第y个活动感兴趣

输出

每组输出一个整数，表示最少天数

样例输入

1
    3 6 
    1 1 
    1 2 
    2 2
    2 3 
    3 1 
    3 3

样例输出

来源

[某校校赛][Link 1]

上传者

[MQLYES][]

这道题告诉我们，任何题目不要先想算法，应该先从思维上入手，否则很容易陷入怪圈导致简单题做不出。

因为每个活动被参加后其他人不能参加，所以这道题就是求哪个活动匹配到的人最多，![委屈][wronged.gif]。。。。！！！果然不是匹配，哼╭(╯^╰)╮

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int ans[1005];
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		memset(ans,0,sizeof(ans));
    		int n,m;
    		scanf("%d%d",&n,&m);
    		for(int i=0; i<m; i++) {
    			int a,b;
    			scanf("%d%d",&a,&b);
    			ans[b]++;
    		}
    		printf("%d\n",*max_element(ans,ans+n));
    	}
    	return 0;
    }

[题目地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=1291][http_acm.nyist.net_JudgeOnline_problem.php_pid_1291]

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E6%9F%90%E6%A0%A1%E6%A0%A1%E8%B5%9B
[MQLYES]: http://acm.nyist.net/JudgeOnline/profile.php?userid=MQLYES
[wronged.gif]: /images/20220718/4afa4a19549b4bea9c0b6b2b9458b6b2.png
[http_acm.nyist.net_JudgeOnline_problem.php_pid_1291]: http://acm.nyist.net/JudgeOnline/problem.php?pid=1291