题目链接

P2055 [ZJOI2009]假期的宿舍

解题思路

因为懒，提供一种不连边，直接根据题目给出的邻接矩阵进行匈牙利算法的思路。

\(a[i][j]\)表示\(i\)能不能睡\(j\)的床，需要根据具体情况在读入的时候适当调整。

\(inv[i]\)表示第\(i\)个需要在学校睡觉的人（可能是在校学生也可能是校外人员）

AC代码

#include<stdio.h>
#include<string.h>
int a[60][60],is[60],leave[60],vis[60],mt[60];
//a[i][j]:i能不能睡j的床 
int inv[60],cnt,n;
//inv[i]:第i个要在学校睡觉的人 
int dfs(int p,int t){
    int i;
    for(i=1;i<=n;i++){
        if(a[inv[p]][i]&&vis[i]!=t){
            vis[i]=t;
            if(!mt[i]||dfs(mt[i],t))return mt[i]=p;
        }
    }
    return 0;
}
int main(){
    int i,j,t;
    scanf("%d",&t);
    while(t--){
        int ans=0;cnt=0;
        memset(vis,0,sizeof(vis));
        memset(mt,0,sizeof(mt));
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&is[i]);
        for(i=1;i<=n;i++){
            scanf("%d",&leave[i]);
            if(!is[i]||!leave[i])inv[++cnt]=i;
            //如果这人不是学校的或者不回家那就要在学校睡觉 
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
                if(i==j&&is[i]&&!leave[i])a[i][j]=1;
                //如果在校没回家那可以睡自己的床 
                if(!is[j])a[i][j]=0;
                //如果不是学校的没床可以给别人睡 
            }
        for(i=1;i<=cnt;i++)
            if(dfs(i,i))ans++;
            else break;
        if(ans!=cnt)printf("T_T\n");
        else printf("^_^\n");
    }
    return 0;
}