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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 1500;
const int INF = 1e9;
struct MAX_FLOW{
struct Edge{
int nxt, to;
LL flow;
}edge[200005];
int head[N], edgeNum = 1;
void addEdge(int from, int to, LL flow){
edge[++edgeNum].nxt = head[from];
edge[edgeNum].to = to;
edge[edgeNum].flow = flow;
head[from] = edgeNum;
}
int s, t, n;
bool inq[N];
LL dep[N];
void init(){
edgeNum = 1;
for(int i = 1; i <= n + 5; i++)
head[i] = 0;
}
bool bfs(){
for(int i = 1; i <= n; i++)
dep[i] = INF, inq[i] = 0;
queue<int> q;
q.push(s);
inq[s] = 1;
dep[s] = 0;
while(!q.empty()){
int cur = q.front(); q.pop();
inq[cur] = 0;
for(int i = head[cur]; i; i = edge[i].nxt){
if(dep[edge[i].to] > dep[cur] + 1 && edge[i].flow){
dep[edge[i].to] = dep[cur] + 1;
if(!inq[edge[i].to]){
q.push(edge[i].to);
inq[edge[i].to] = 1;
}
}
}
}
if(dep[t] != INF) return 1;
return 0;
}
LL dfs(int x, LL minFlow){
LL flow = 0;
if(x == t) return minFlow;
for(int i = head[x]; i; i = edge[i].nxt){
if(dep[edge[i].to] == dep[x] + 1 && edge[i].flow){
flow = dfs(edge[i].to, min(minFlow, edge[i].flow));
if(flow){
edge[i].flow -= flow;
edge[i^1].flow += flow;
return flow;
}
}
}
return 0;
}
LL Dinic(){
LL maxFlow = 0, flow = 0;
while(bfs()){
while(flow = dfs(s, INF))
maxFlow += flow;
}
return maxFlow;
}
}dinic;
int n, e, c[N], m[N], a[N][10];
LL tot;
inline bool check(LL mid){
dinic.s = n + 8, dinic.t = n + 9, dinic.n = n + 9;
dinic.init();
for(int i = 1; i <= 7; i++){
dinic.addEdge(dinic.s, n + i, mid / 7 * e + (mid % 7 >= i) * e);
dinic.addEdge(n+i, dinic.s, 0);
}
for(int i = 1; i <= n; i++){
dinic.addEdge(i, dinic.t, c[i]), dinic.addEdge(dinic.t, i, 0);
for(int j = 1; j <= m[i]; j++)
dinic.addEdge(n + a[i][j], i, INF), dinic.addEdge(i, n + a[i][j], 0);
}
return dinic.Dinic() >= tot;
}
int main(){
read(n, e);
for(int i = 1; i <= n; i++){
scanf("%d%d", &c[i], &m[i]);
tot += c[i];
for(int j = 1; j <= m[i]; j++)
scanf("%d", &a[i][j]);
}
LL l = 0, r = 2000000000;
while(l < r){
LL mid = (r - l) / 2 + l;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%lld\n", l);
return 0;
}
|