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
| #include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
int inf=0x3f3f3f3f;
const int N=1e5+10;
const int M=5e6+10;
struct edge {
int u, v, c, val, nxt;
edge(int u = 0, int v = 0, int c = 0, int val = 0, int nxt = 0): u(u), v(v), c(c), val(val), nxt(nxt) {}
}e[M];
int head[N];
int now[N];
int cnt=1;
void ADD(int u,int v,int c){
cnt++;
e[cnt]=edge(u,v,c,0,head[u]);
head[u]=cnt;
}
void add_edge(int u,int v,int c){
ADD(u,v,c);
ADD(v,u,0);
}
int dep[N];
bool bfs(){
memset(dep,0,sizeof dep);
memcpy(now,head,sizeof head);
dep[s]=1;
queue<int>q;q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
int c=e[i].c;
if(!c||dep[v]!=0) continue;
dep[v]=dep[u]+1;
q.push(v);
}
}
return dep[t]!=0;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
int nowflow=0;
for(int i=now[u];i&&nowflow<flow;i=e[i].nxt){
now[u]=i;
int v=e[i].v;
int c=e[i].c;
if(!c||dep[v]!=dep[u]+1)continue;
int ff=dfs(v,t,min(c,flow-nowflow));
if(ff) e[i].c-=ff,e[i^1].c+=ff,nowflow+=ff;
else dep[v]=inf;
}
return nowflow;
}
int maxflow(){
int ans=0;
while(bfs()){
int nowflow;
while((nowflow=dfs(s,t,inf))) ans+=nowflow;
}
return ans;
}
int main()
{
cin>>n>>m;
s=n+m+1,t=s+1;
int sum=0;
for(int i=1;i<=n;i++){
int x,tt;
cin>>x>>tt;
sum+=x;
add_edge(s,i,x);
while(tt--){
int aa,bb;
cin>>aa>>bb;
add_edge(i,n+aa,bb);
}
}
for(int i=1;i<=m;i++){
int vv;
cin>>vv;
add_edge(n+i,t,vv);
}
cout<<sum-maxflow();
}
|