科大讯飞杯 - 动物森友会

传送门：科大讯飞杯 - 动物森友会

思路分析

二分日期，然后网络流判断
建图方式如下：

1. 超级源点 -> 每个任务，权值为需要次数c
2. 每个任务 -> 对应的星期几，权值INF
3. 每个星期 -> 超级汇点，权值为$day/7$+$($day%7>=i$)$

满足条件为最大流==总次数

样例输入

5 2
2 4 1 3 5 7
2 3 2 4 6
2 2 1 2
2 2 3 4
2 2 5 6

样例输出

5

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N= 1e3+10;

struct node {
    int v,w,next;
} e[N*N];

int head[N],dep[N],cnt,c[N];
int n,m,sum;
vector<int>v[N];


void add(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[++cnt].v=u;
    e[cnt].w=0;
    e[cnt].next=head[v];
    head[v]=cnt;

}

bool bfs(int s,int t) {
    queue<int>q;
    mem(dep,0); 
    dep[s]=1;   
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u]; i ; i=e[i].next) {
            int v=e[i].v;
            int w=e[i].w;
            if(w && !dep[v]) { 
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }

    return dep[t];
}

int dfs(int u,int f,int t) {
    int fl=0;
    if(u==t)
        return f;
    for(int i=head[u]; i && f ; i=e[i].next) {
        int v=e[i].v;
        if(dep[v]==dep[u]+1 && e[i].w) {  
            int nx=dfs(v,min(f,e[i].w),t);
            e[i].w-=nx;
            e[i^1].w+=nx;
            f-=nx;
            fl+=nx;
        }
    }
    if(!fl)
        dep[u]=-2;
    return fl;

}

int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t))
        ans+=dfs(s,INF,t); 
    return ans;
}

int judge(int day){
    cnt=1;
    mem(head,0);
    int s=0,t=N-1;
    for(int i=1;i<=n;i++){
        add(s,i,c[i]);
        for(auto x:v[i]) add(i,x+n,INF);
    }
    for(int i=1;i<=7;i++) add(i+n,t,(day/7+(day%7>=i))*m);
    int ans=dinic(s,t);
    return ans>=sum;
}


signed main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        sum+=c[i];
        int q;
        cin>>q;
        while(q--){
            int x;
            cin>>x;
            v[i].push_back(x);
        }
    }
    
    int l=0,r=INF;
    int ans=0;
    while(r>=l){
        int mid=l+r>>1;
        if(judge(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
        
    }
    cout<<ans<<endl;
    




    return 0;
}