L 动物森友会题解

$description:$

有 $n$ 个任务需要完成 $,$ 其中第 $i$ 个任务需要做 $c_i$ 次 $,$ 它可能在周一到周日 $7$ 天内的若干天开放 $.$

每天只能做 $e$ 次任务,求出完成所有任务需要多少天

$solution:$

显然答案具有可二分性 $,$ 于是二分答案 $x$ 转化为判定性问题 $.$

$check$ 可以用网络流 $.$

大概就是 $(S,i,e*(x\div7+[i\leq$ $(x$ $mod$ $7)$ $]))$ 和 $(j+7,T,c_i)$

然后在 $1 -- 7$ 和 $8-(7+n)$ 这两组点之间连流量为 $INF$ (或 $c_i$ )的边

$check$ $Maxflow$ 是否等于 $\sum c_i$ 即可 $.$

复杂度 $O(Dinic(n,7*n)*log(L))$ 其中 $L$ 为答案范围 $.$

$code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T> void read(T &x){
    x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

const int N = 1050,M = 7+2,V = N + 50,E = 200050;
int To[E],Ne[E],Flow[E],He[V],_k = 1;
inline void add(int x,int y,int flow){
    ++_k; To[_k] = y,Flow[_k] = flow,Ne[_k] = He[x],He[x] = _k;
    ++_k; To[_k] = x,Flow[_k] = 0,Ne[_k] = He[y],He[y] = _k;
}
inline void init(){ _k = 1;memset(He,0,sizeof(He)); }
int n,K;
int qwq[7+5],sumn;
int need[N],len[N],a[N][M];

int S,T,Now[V];
inline void initNow(){
    int i;
    for (i = 1; i <= T; ++i) Now[i] = He[i];
}
int dis[V],Q[V],ql,qr;
inline bool Bfs(){
    int i,x,y,p;
    for (i = 1; i <= T; ++i) dis[i] = 0;
    dis[S] = 1; Q[ql=qr=1]=S;
    while (ql <= qr){
        x = Q[ql],++ql;
        for (p = He[x]; p ; p = Ne[p]) if (Flow[p] && !dis[y=To[p]])
            dis[y] = dis[x] + 1,Q[++qr] = y;
    }
    return dis[T] > 0;
}
inline int Dfs(int x,int flow){
    if (!flow || x == T) return flow;
    int y,p,f,rest = flow;
    for (p = Now[x]; p ; p = Ne[p]){
        Now[x] = p;
        if (Flow[p] && dis[y=To[p]] == dis[x] + 1){
            f = Dfs(y,min(rest,Flow[p]));
            rest -= f,Flow[p] -= f,Flow[p^1] += f;
            if (!rest) return flow;
        }
    }
    dis[x] = -1;
    return flow - rest;
}
inline int Dinic(){
    int sum = 0;
    while (Bfs()) initNow(),sum += Dfs(S,sumn);
    return sum;
}
inline bool check(int days){
    int i,j;
    init();
    S = n+8,T = n+9;
    for (i = 1; i <= 7; ++i){
        qwq[i] = min(1ll * sumn,1ll * K * ( days / 7 + ( (i<=days%7) ? 1 : 0) ));
    }
    for (i = 1; i <= 7; ++i) add(i,T,qwq[i]);
    for (i = 1; i <= n; ++i){
        add(S,i+7,need[i]);
        for (j = 1; j <= len[i]; ++j) add(i+7,a[i][j],need[i]);
    }
    return Dinic() >= sumn;
}

signed main(){
    int i,j;
    read(n),read(K);
    sumn = 0;
    for (i = 1; i <= n; ++i){
        read(need[i]),read(len[i]);
        sumn += need[i];
        for (j = 1; j <= len[i]; ++j) read(a[i][j]);
    }
    int L = 0,R = 2000000000,Mid,Ans = 2000000000;
    while (L <= R){
        Mid = L+R>>1; if (check(Mid)) Ans = Mid,R = Mid - 1; else L = Mid + 1;
    }
    cout << Ans << '\n';
    return 0;
}

L 动物森友会 题解

L 动物森友会题解