"蔚来杯"2022牛客暑期多校训练营10 E.Reviewer Assignment

E.eviewer Assignment

题目大意

有m篇论文和n个审稿人，给出每个审稿人能审论文的集合，要求给没个审稿人安排一篇论文。令f(i)表示被至少i个审稿人审过的论文数量，要求求出一种分配方案，使得(f(1),f(1),...,f(n))的字典序最大。

分析

不知道，有没有跟我一样理解错题意的。我说一下我理解的错误题意，只要尽量让审稿人最少的稿子数量尽量大即可，其他的随便。

这导致一开始，我的方向就是考虑二分+网络流。我考虑的是，直接二分审稿人最少的审稿人数量，得到一个值之后，其余的随便选就行了。给我WA麻了。

其实题目的意思是，我们先满足审稿人为1的数量，如果还有就再满足审稿人2的，一步步递推下去，直到容量i下我们可以分配给所有的审稿人了，就结束。

我们考虑建图

• 从源点向所有审稿人连一条容量为1的边
• 从审稿人向所有可审稿件连一条容量为1的边
• 从稿件向汇点连容量为i的边（i是我们逐步递推的容量）

我们知道，因为我们只改变了某些边的容量，根据网络流的性质，我们只需要在之前跑完的图中将那个改变的容量加上，继续跑就行。

考虑-1的情况，只要有某次，我们增大了容量限制后，不能给更多的审稿人用了，即无新增审稿人了，那就说明有一些审稿人一个稿子都审不了，直接结束。

看代码吧。

Ac_code

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
using namespace std;
const int N =  810,M = (N + 410*410)*2,INF = 0x3f3f3f3f;

int h[N],ne[M],e[M],f[M],idx;
int cur[N],d[N],q[N];
int n,m,S,T;

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],f[idx] = c,h[a] = idx++;
    e[idx] = a,ne[idx] = h[b],f[idx] = 0,h[b] = idx++;
}

bool bfs()
{
    int hh = 0,tt = -1;
    memset(d,0x3f,sizeof d);
    q[++tt] = S,d[S] = 1,cur[S] = h[S];
    while(hh<=tt)
    {
        auto t = q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==INF&&f[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q[++tt] = j;
            }
        }
    }
    return 0;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int j = e[i];
        cur[u] = i;
        if(d[j]==d[u]+1&&f[i])
        {
            int t = find(j,min(limit-flow,f[i]));
            if(!t) d[j] = -1;
            f[i] -= t,f[i^1] += t,flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0,flow;
    while(bfs()) if(flow = find(S,INF)) r += flow;
//     cout<<mid<<" "<<r<<endl;
    return r;
}
 
int main() 
{
    ios;
    cin>>n>>m;
    S = 0,T = n + m + 1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) add(S,i,1);
    for(int j=n+1;j<=n+m;j++) add(j,T,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;cin>>c;
            if(c=='1') add(i,j+n,1);
        }
    }
    int now = 0;
    while(now<n)
    {
        for(int i=n*2;i<(n+m)*2;i+=2) f[i]++;
        int delta = dinic();
        if(!delta) 
        {
            puts("-1");
            return 0;
        }
        now += delta;
    }
    // cout<<l<<endl;
    vector<int> ans(n+1,-1);
    for(int i=h[S];~i;i=ne[i])
    {
        int j = e[i];
        for(int k=h[j];~k;k=ne[k])
        {
            int u = e[k];
            if(!f[k])
            {
                ans[j] = u-n;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}