HNU 11979 Roll call 二分图匹配

题意：

　　众所周知，老师经常在班级上点名。点名是从名单上叫一个人的名字或者id来判断名单上这个人是否在场。学生们总是有各种各样的理由不来，所以他们需要其他人帮他们答到。但是打到工作不是这么简单，出于各种考虑，他们答道遵循以下原则。

1. 每个来上课的人必须给自己达到；

2. 每个来上课的人，只能帮另外一个人达到；

3. 如果一个人想帮助另外一个人答道，那么他们id的差至少大于等于K。

　　现在老师又要点名了，请问是否存在一种情况，使老师相信每个人都到场了。

输入：

　　第一行有一个整数T，表示接下来会有T组数据。

　　对于每组数据，第一行包含三个整数N, M, K (1<=N<=10^9,2<=M,K<=150)，告诉你一共有N个学生，有M个学生到场了，K是id的最小差。第二行有M个整数，表示到场学生的id。

思路：
二分图匹配

代码：用的增广路算法，还没学MK

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int MAXN = ;

 bool vis[MAXN];

 bool present[MAXN];

 int id[MAXN];

 int matched[MAXN];

 int N, M, K;

 inline int myAbs(int x) {

     return x> ? x : -x;

 }

 bool dfs(int v) {

     vis[v] = true;

     for (int u = ; u <= N; u++) if ((present[u]^present[v]) && (myAbs(u-v)>=K)) {

         int w = matched[u];

         if (w< || (!vis[w] && dfs(w))) {

             matched[v] = u;

             matched[u] = v;

             return true;

         }

     }

     return false;

 }

 int Match() {

     int res = ;

     memset(matched, -, sizeof(matched));

     for (int v = ; v <= N; v++) {

         if (matched[v]<) {

             memset(vis, false, sizeof(vis));

             if (dfs(v)) {

                 res++;

             }

         }

     }

     return res;

 }

 int main() {

     #ifdef Phantom01

         freopen("HNU11979.txt", "r", stdin);

     #endif // Phantom01

     int T;

     scanf("%d", &T);

     while (T--) {

         scanf("%d%d%d", &N, &M, &K);

         for (int i = ; i < M; i++) {

             scanf("%d", &id[i]);

         }

         if (N>(M<<)) {

             puts("N");

             continue;

         }

         memset(present, false, sizeof(present));

         for (int i = ; i < M; i++)

             present[id[i]] = true;

         if ((N-M)==Match()) puts("Y");

         else puts("N");

     }

     return ;

 }

HNU11979

巴特西

HNU 11979 Roll call 二分图匹配

最新文章

热门文章