【洛谷P4382】劈配

……no zuo no die,考场就想到正解了,但是不敢打,结果一轮就gg了,也算是报应qwq,也许以后我应该大胆一点了……
这个题目第一问我们可以动态建边,贪心的做一遍就好,并在匹配的同时记录剩余网络,便于处理第二问
第二问如果本来就满足期望值就不管,否则二分第几名才能满足这个人要求,然后每次用(二分答案-1)的剩余网络+重新建边,跑一下就可以了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

typedef long long lo;

typedef long double ld;

const lo mo = 1000000007;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')    
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, m, e, t, c, tot = -1, te, he, lx;

int pos[220][220][220], ta[220], lin[220], head[880], ta1[220], ta2[220];

int q[1010], de[1010], fir[220][880], a2[220], num[220], hop[220];

struct in
{
    int to, ne, co;
}ter[80080], wb[220][80080];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de));
    q[te = he = 0] = 0, de[0] = 1;
    while(he <= te)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[to] = de[qaq] + 1, q[++ te] = to;
        }
    }
    return de[e] > 0;
}

int dfs(int no, int fl)
{
    if(no == e)
        return fl;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co > 0)
        {
            int rt = dfs(to, min(fl, ter[i].co));
            if(rt > 0)
            {
                ter[i].co -= rt, ter[i ^ 1].co += rt;
                if(no >= 1 && no <= n && to > n)
                    lin[no] = to - n;
                return rt;
            }
        }
    }
    return 0;
}

int main()
{
    re(t), re(c);
    for(ri ci = 1; ci <= t; ci ++)
    {
        memset(pos, 0, sizeof(pos)), memset(fir, -1, sizeof(fir));
        memset(head, -1, sizeof(head)), memset(ta, 0, sizeof(ta));
        memset(ta2, 63, sizeof(ta1)), memset(lin, 63, sizeof(lin));
        re(n), re(m), e = n + m + 5, tot = -1;
        for(ri i = 1; i <= m; i ++)
            re(num[i]), build(i + n, e, num[i]);
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= m; j ++)//pos[i][j][0]表示第i个人第j志愿一共选了多少导师 
                re(lx), pos[i][lx][++ pos[i][lx][0]] = j, lx = (lx == 0) ? 1000000007 : lx, ta2[i] = min(ta2[i], lx);
        for(ri i = 1; i <= n; i ++)//第m + 1志愿设为m + 1位导师(没匹配成功) 
            re(hop[i]), pos[i][m + 1][++ pos[i][m + 1][0]] = m + 1;
        for(ri i = 0; i <= e; i ++)//fir[i][j]表示当前匹配到i号学员的head[j] 
            fir[0][i] = head[i];
        for(ri i = 0; i <= tot; i ++)//wb[i][j]表示当前匹配到i号学员,第j条边的情况,记录残余网络 
            wb[0][i] = ter[i];
        ta1[0] = tot;
        for(ri i = 1; i <= n; i ++)
        {
            build(0, i, 1);
            int ll = tot;
            while(++ ta[i] <= m + 1)//动态加边 
            {
                head[i] = ll;//每回合将之前这个点连的边基本踢掉,只留从它到起点的 
                if(pos[i][ta[i]][0] == 0)
                    continue;
                for(ri j = 1; j <= pos[i][ta[i]][0]; j ++)//建边 
                    build(i, pos[i][ta[i]][j] + n, 1);
                if(bfs())//如果可以增广,说明可以匹配了 
                {
                    while(int ret = dfs(0, 1000000007));
                    break;
                }
            }
            for(ri j = 0; j <= e; j ++)//记录每次的残余网络 
                fir[i][j] = head[j];
            for(ri j = 0; j <= tot; j ++)
                wb[i][j] = ter[j];
            ta1[i] = tot;//记录到此时用的边 
        }
        for(ri i = 1; i <= n; i ++)
            ta[i] = (ta[i] > m + 1) ? m + 1 : ta[i], printf("%d ", ta[i]);
        printf("\n");
        for(ri i = 1; i <= n; i ++)//然后接下来二分答案,第几名才能满足第i个人的要求 
        {
            int lia = 0;
            if(ta[i] <= hop[i])
                a2[i] = 0;
            else
            {
                int l = 1, r = i - 1, mid;
                while(l <= r)
                {
                    mid = (l + r) >> 1;
                    for(ri j = 0; j <= e; j ++)//替换成原来的剩余网络 
                        head[j] = fir[mid - 1][j];
                    for(ri j = 0; j <= ta1[mid - 1]; j ++)
                        ter[j] = wb[mid - 1][j];
                    int rr = tot;
                    build(0, i, 1);
                    for(ri j = 1; j <= hop[i]; j ++)//然后把期望值之前的志愿连边就行,任意一个能匹配就可以 
                        for(ri k = 1; k <= pos[i][j][0]; k ++)
                            build(i, pos[i][j][k] + n, 1);
                    bool fl = bfs() && dfs(0, 1000000007);
                    if(fl == 1)
                        l = mid + 1, lia = mid;
                    else
                        r = mid - 1;
                    tot = rr;
                }
                a2[i] = i - lia;
            }
        }
        for(ri i = 1; i <= n; i ++)
            printf("%d ", a2[i]);
        printf("\n");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注