POJ2239简单二分匹配
简单 匹配 二分
2023-09-11 14:14:00 时间
题意：
一周有7天，每天可以上12节课，现在给你每科课的上课时间，问你一周最多可以上几科课，一科课只要上一节就行了。
思路：
简单题目，直接二分就行了，好久没写二分匹配了，练习下手而已。
#include<stdio.h>
#include<string.h>
#define N_node 400
#define N_edge 27000
typedef struct
{
int to ,next;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int mk_dfs[N_node] ,mk_gx[N_node];
void add(int a ,int b)
{
E[++tot].to = b;
E[tot].next = list[a];
list[a] = tot;
}
int DFS_XYL(int x)
{
for(int k = list[x] ;k ;k = E[k].next)
{
int to = E[k].to;
if(mk_dfs[to]) continue;
mk_dfs[to] = 1;
if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to]))
{
mk_gx[to] = x;
return 1;
}
}
return 0;
}
int main ()
{
int i ,n ,Ans ,a ,b ,nn;
while(~scanf("%d" ,&n))
{
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= n ;i ++)
{
scanf("%d" ,&nn);
while(nn--)
{
scanf("%d %d" ,&a ,&b);
add(i ,n + (a - 1) * 12 + b);
}
}
Ans = 0;
memset(mk_gx ,255 ,sizeof(mk_gx));
for(i = 1 ;i <= n ;i ++)
{
memset(mk_dfs ,0 ,sizeof(mk_dfs));
Ans += DFS_XYL(i);
}
printf("%d\n" ,Ans);
}
return 0;
}
一周有7天，每天可以上12节课，现在给你每科课的上课时间，问你一周最多可以上几科课，一科课只要上一节就行了。
思路：
简单题目，直接二分就行了，好久没写二分匹配了，练习下手而已。
#include<stdio.h>
#include<string.h>
#define N_node 400
#define N_edge 27000
typedef struct
{
int to ,next;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int mk_dfs[N_node] ,mk_gx[N_node];
void add(int a ,int b)
{
E[++tot].to = b;
E[tot].next = list[a];
list[a] = tot;
}
int DFS_XYL(int x)
{
for(int k = list[x] ;k ;k = E[k].next)
{
int to = E[k].to;
if(mk_dfs[to]) continue;
mk_dfs[to] = 1;
if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to]))
{
mk_gx[to] = x;
return 1;
}
}
return 0;
}
int main ()
{
int i ,n ,Ans ,a ,b ,nn;
while(~scanf("%d" ,&n))
{
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= n ;i ++)
{
scanf("%d" ,&nn);
while(nn--)
{
scanf("%d %d" ,&a ,&b);
add(i ,n + (a - 1) * 12 + b);
}
}
Ans = 0;
memset(mk_gx ,255 ,sizeof(mk_gx));
for(i = 1 ;i <= n ;i ++)
{
memset(mk_dfs ,0 ,sizeof(mk_dfs));
Ans += DFS_XYL(i);
}
printf("%d\n" ,Ans);
}
return 0;
}