河南多校联合训练　F 不是匹配

描述

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

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

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

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

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

输入

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

输出

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

样例输入

样例输出

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?cid=320&cpid=6

*******************************************************

题意：有n个人，m行x,y的信息，表达的是第x个人对第y个活动感兴趣。每个人都要去把自己感兴趣的活动参加完，且每个人参加一个活动需要花费一天的时间，而且当有一个人在参加某活动时，别人不可以同时参加，问你最后每个人都把自己感兴趣的活动参加完时花费的最短天数。

分析：对活动出现次数做标记，有几个人对XX活动感兴趣，则XX活动满足题目要求的天数就为几天，要求所有人都参加完，则所有活动天数最大值就是题目要求的最少天数。

AC代码：

 #include<stdio.h>

 #include<string.h>

 #include<math.h>

 #include<queue>

 #include<algorithm>

 #include<time.h>

 #include<stack>

 using namespace std;

 #define N 12000

 #define INF 0x3f3f3f3f

 int v[N];

 int main()

 {

     int T,n,m,x,y,i;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d %d", &n,&m);

         int ans=;

         memset(v,,sizeof(v));

         for(i=;i<m;i++)

         {

             scanf("%d %d", &x,&y);

             v[y]++;

             ans=max(ans,v[y]);

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

河南多校联合训练　F 不是匹配

最新文章

热门文章

巴特西

河南多校联合训练 F 不是匹配

最新文章

热门文章

河南多校联合训练　F 不是匹配