題意：
? ? ? 一周有7天，每天可以上12節(jié)課，現(xiàn)在給你每科課的上課時間，問你一周最多可以上幾科課，一科課只要上一節(jié)就行了。


思路：
? ? ? 簡單題目，直接二分就行了，好久沒寫二分匹配了，練習(xí)下手而已。


#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;
}

總結(jié)

以上是生活随笔為你收集整理的POJ2239简单二分匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。