1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,k,s,t,d[N],cur[N],cnt,tot;
vector<int> G[N];
struct Edge {
int u,v,w;
}edges[N*10];
vector<Edge> e;
void addedge(int u,int v,int w) {
e.push_back({u,v,w});
e.push_back({v,u,0});
G[u].push_back(e.size()-2);
G[v].push_back(e.size()-1);
}
void build(int days) {
e.clear();
for(int i=1;i<=n+9;i++) G[i].clear();
for(int i=1;i<=cnt;i++) addedge(edges[i].u,edges[i].v,edges[i].w);
for(int i=1;i<=7;i++) addedge(i+n,t,(days/7+(days%7>=i))*k);
}
bool bfs() {
for(int i=1;i<=n+9;i++) d[i]=0;
queue<int>q;
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
for(auto x:G[u]) {
if(e[x].v==s||d[e[x].v]||e[x].w<=0) continue;
d[e[x].v]=d[u]+1;
q.push(e[x].v);
}
}
if(d[t]) return true;
return false;
}
int dfs(int u,int a) {
if(u==t) return a;
int f,flow=0;
for(int &i=cur[u];i<G[u].size();i++) {
if(d[e[G[u][i]].v]!=d[u]+1||e[G[u][i]].w<=0||(f=dfs(e[G[u][i]].v,min(a,e[G[u][i]].w)))<=0) continue;
e[G[u][i]].w-=f;
e[G[u][i]^1].w+=f;
a-=f;
flow+=f;
if(a==0) break;
}
return flow;
}
int Dinic(int days) {
build(days);
int flow=0;
while(bfs()) {
for(int i=1;i<=n+9;i++) cur[i]=0;
flow+=dfs(s,0x7fffffff);
}
return flow;
}
void solve() {
s=n+8,t=s+1;
int l=1,r=7*tot/k+100;
while(l<r) {
int mid=l+r>>1;
if(Dinic(mid)==tot) r=mid;
else l=mid+1;
}
printf("%d\n",l);
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
int w,p;
scanf("%d%d",&w,&p);
edges[++cnt]={n+7+1,i,w};
tot+=w;
for(int j=1;j<=p;j++) {
int v;
scanf("%d",&v);
edges[++cnt]={i,v+n,w};
}
}
solve();
return 0;
}
|