题目链接：https://ac.nowcoder.com/acm/contest/5278/L
解题思路：需要用到二分加网络流，二分我们需要的天数，然后就是建图
我们考虑到每天只能完成一定量的任务，因此我们可以在原点和星期几之间进行连线，边的容量是
二分出的天数包含的周次，和最后是否包含这一天，乘以这一星期的上限即可。然后就是在边和任务之间连线，
当然，我们可以完成无数次这个任务，因此链接为inf，最后是在任务和终点之间连线，这个是限制此任务最多完成多少次
#include<bits/stdc++.h> using namespace std; const int maxn=2e3+10; const int inf=1e9+10; struct no { int next; int to; int val; }edge[maxn]; int cnt; int head[maxn]; int belong[maxn]; int dep[maxn]; int a[maxn]; int n,m,s,t; int sum; void add(int u,int v,int w) { edge[cnt].to=v,edge[cnt].val=w,edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].to=u,edge[cnt].val=0,edge[cnt].next=head[v]; head[v]=cnt++; } bool bfs() { memset(dep,0,sizeof(dep)); dep[s]=1; queue<int>q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!dep[v]&&edge[i].val>0) { dep[v]=dep[u]+1; q.push(v); } } } return dep[t]; } int dfs(int u,int maxflow) { int tempflow; if(u==t) { return maxflow; } int add=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dep[v]==dep[u]+1&&edge[i].val>0&&(tempflow=dfs(v,min(maxflow-add,edge[i].val)))) { edge[i].val-=tempflow; edge[i^1].val+=tempflow; add+=tempflow; if(maxflow==add) break; } } return add; } int dicnic() { int ans=0; while(bfs()) { int temp; while(temp=dfs(s,inf)) ans+=temp; } return ans; } vector<int>q[maxn]; int c[maxn]; int check(int mid) { if(m*mid<sum) return 0; memset(head,-1,sizeof(head)); cnt=0; int vc=0; s=++vc; t=++vc; for(int i=1;i<=7;i++) add(s,++vc,(mid/7+(mid%7>=i))*m); for(int i=1;i<=n;i++) { vc++; add(vc,t,c[i]); for(int j=0;j<q[i].size();j++) { add(q[i][j]+2,vc,inf); } } return dicnic()==sum; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { int qq; cin>>c[i]>>qq; sum+=c[i]; for(int j=1;j<=qq;j++) { int ss; cin>>ss; q[i].push_back(ss); } } int l=1,r=1e9/m; int res; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) r=mid-1,res=mid; else l=mid+1; } cout<<res<<endl; return 0; }