luogu2763 试题库问题 二分匹配

关键词：二分匹配

本题用有上下界的网络流可以解决，但编程复杂度有些高。

每个类需要多少题，就设置多少个类节点。每个题节点向其所属的每一个类节点连一条边。这样就转化成了二分匹配问题。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;

#define LOOP(i,n) for(int i=1; i<=n; i++)
const int MAX_X = 1010, MAX_Y = 1010, MAX_EDGE = MAX_X*MAX_Y;

struct Hungary
{
    struct Xnode;
    struct Ynode;
    struct Edge;

    struct Xnode
    {
        Edge *Head;
        int Id;
    }_xNodes[MAX_X];
    int _xCnt;

    struct Ynode
    {
        Xnode *Match;
        bool Vis;
        Ynode():Vis(false){}
    }_yNodes[MAX_Y];
    int _yCnt;

    struct Edge
    {
        Xnode *X;
        Ynode *Y;
        Edge *Next;
        Edge(Xnode *x, Ynode *y, Edge *next):X(x),Y(y),Next(next){}
    }*_edges[MAX_EDGE];
    int _eCnt;

    void Init(int xCnt, int yCnt)
    {
        _xCnt = xCnt;
        _yCnt = yCnt;
        _eCnt = 0;
    }

    void Build(int xId, int yId)
    {
        //printf("xId %d yId %d
", xId, yId);
        Xnode *x = xId + _xNodes;
        Ynode *y = yId + _yNodes;
        x->Id = xId;
        Edge *e = _edges[++_eCnt] = new Edge(x, y, x->Head);
        x->Head = e;
    }

    bool Dfs(Xnode *x)
    {
        for (Edge *e = x->Head; e; e = e->Next)
        {
            if (!e->Y->Vis)
            {
                e->Y->Vis = true;
                if (!e->Y->Match || Dfs(e->Y->Match))
                {
                    e->Y->Match = x;
                    return true;
                }
            }
        }
        return false;
    }

    int GetMatchCnt()
    {
        int ans = 0;
        LOOP(xId, _xCnt)
        {
            LOOP(yId, _yCnt)
                _yNodes[yId].Vis = false;
            ans += Dfs(xId + _xNodes);
        }
        return ans;
    }
}g;

int main()
{
#ifdef _DEBUG
    freopen("c:\noi\source\input.txt", "r", stdin);
#endif
    int totSort, totQuest, sortNeedCnt[MAX_X], sortPrevCnt[MAX_Y], yCnt = 0, matchCnt;
    memset(sortPrevCnt, 0, sizeof(sortPrevCnt));
    memset(sortNeedCnt, 0, sizeof(sortNeedCnt));
    scanf("%d%d", &totSort, &totQuest);
    LOOP(i, totSort)
    {
        scanf("%d", i + sortNeedCnt);
        sortPrevCnt[i + 1] = (yCnt += sortNeedCnt[i]);
    }
    g.Init(totQuest, yCnt);
    LOOP(xId, totQuest)
    {
        int sortInCnt;
        scanf("%d", &sortInCnt);
        LOOP(i, sortInCnt)
        {
            int sortIn;
            scanf("%d", &sortIn);
            LOOP(j, sortNeedCnt[sortIn])
                g.Build(xId, j + sortPrevCnt[sortIn]);
        }
    }
    matchCnt = g.GetMatchCnt();
    if (matchCnt < yCnt)
    {
        printf("No Solution!
");
        return 0;
    }
    LOOP(curSort, totSort)
    {
        printf("%d: ", curSort);
        for (int yId = sortPrevCnt[curSort] + 1; yId <= sortPrevCnt[curSort] + sortNeedCnt[curSort]; yId++)
            printf("%d ", g._yNodes[yId].Match->Id);
        printf("
");
    }
    return 0;
}