洛谷 - 假期的宿舍

题目链接：https://www.luogu.com.cn/problem/P2055

思路：匈牙利算法，二分图最大匹配

#include 
using namespace std;
const int N=55;
int n,m,ans;//m记录除去回家的人的人数，ans记录最大匹配数
int match[N];//第i个节点匹配的节点
bool sch[N],ned[N];//标记是否属于学校，是否需要床位
bool g[N][N],vis[N];//g标记i节点和j节点是否存在关系，即可以匹配

bool dfs(int x)//匈牙利算法
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&g[x][i])
        {
            vis[i]=true;
            if(match[i]==-1||dfs(match[i]))
            {
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int T;
    cin>>T;

    while(T--)
    {
        m=0,ans=0;
        memset(sch,0,sizeof sch);
        memset(ned,0,sizeof ned);
        memset(match,-1,sizeof match);
        memset(g,0,sizeof g);
        cin>>n;

        for(int i=1;i<=n;i++)
        {
            cin>>sch[i];
        }

        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            if(sch[i]==0||sch[i]==1&&x==0)
            {
                ned[i]=1;
                m++;
            }
        }

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                cin>>g[i][j];
                if(i==j&&sch[j]) g[i][j]=1;
                if(sch[j]==0) g[i][j]=0;
            }

        for(int i=1;i<=n;i++)//用人去匹配床位
        {
            if(ned[i]==0) continue;//回家的人不需要床位
            memset(vis,0,sizeof vis);
            if(dfs(i)) ans++;
        }

        if(ans==m)//匹配数相等，说明可以分配
        {
            cout<<"^_^"<<endl;
        }
        else cout<<"T_T"<<endl;
    }

    return 0;
}

Bye~