L 动物森友会 题解

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

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

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

可以用网络流

大概就是 和

然后在和 这两组点之间连流量为(或)的边

是否等于 即可

复杂度 其中为答案范围

#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;
}