首页 > 代码库 > [ZJOI2009]假期的宿舍

[ZJOI2009]假期的宿舍

2024-09-26 19:14:39   219人阅读

1433: [ZJOI2009]假期的宿舍

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2870  Solved: 1213
[Submit][Status][Discuss]

Description

技术分享

Input

技术分享

Output

技术分享

Sample Input

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

Sample Output

ˆ ˆ

HINT

对于30% 的数据满足1 ≤ n ≤ 12。
对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。

 

左边：在校的不回家的，和不在校的

右边：在校的人的床

最大匹配

#include<cstdio>#include<cstring>#define N 51using namespace std;int T,n,ans,sum;bool in[N],home[N],know[N][N],live[N][N];bool v[N];int match[N];bool go(int u){    for(int i=1;i<=n;i++)     if(in[i]&&live[u][i]&&!v[i])     {         v[i]=true;         if(!match[i]||go(match[i]))         {             match[i]=u;             return 1;        }     }    return 0;}int main(){    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        ans=sum=0;        memset(live,0,sizeof(live));        memset(match,0,sizeof(match));        for(int i=1;i<=n;i++)  scanf("%d",&in[i]);        for(int i=1;i<=n;i++) scanf("%d",&home[i]);        for(int i=1;i<=n;i++)         for(int j=1;j<=n;j++)          scanf("%d",&know[i][j]);        for(int i=1;i<=n;i++)        {            //if(!in[i]||home[i]) continue;            if(in[i]&&home[i]) continue;            sum++;            for(int j=1;j<=n;j++)             live[i][j]=know[i][j];            live[i][i]=1;        }        for(int i=1;i<=n;i++)        {            if(in[i]&&home[i]) continue;            memset(v,0,sizeof(v));            if(go(i)) ans++;        }        if(ans==sum) puts("^_^");        else puts("T_T");    }}

 

[ZJOI2009]假期的宿舍


联系
我们