#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
struct Edge{
int to,nxt,w;}e[maxn<<
1];
int head[maxn],tot,n,m,np,nc,s,t;
void init(){
memset(head,-
1,
sizeof head);
tot=
0;
}
void add(
int u,
int v,
int w){
e[tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot++
;
e[tot].to=u;e[tot].w=
0;e[tot].nxt=head[v];head[v]=tot++
;
}
int d[maxn];
int bfs(){
memset(d,0,
sizeof d);
queue<
int>
q;
q.push(s);d[s]=
1;
while(q.size()){
int x=
q.front();q.pop();
for(
int i=head[x];i!=-
1;i=
e[i].nxt){
int y=
e[i].to;
if(e[i].w==
0 || d[y])
continue;
d[y]=d[x]+
1;
q.push(y);
if(y==t)
return 1;
}
}
return 0;
}
int dfs(
int x,
int flow){
if(x==t)
return flow;
int rest=
flow;
for(
int i=head[x];i!=-
1 && rest; i=
e[i].nxt){
int y=
e[i].to;
if(d[y]!=d[x]+
1 || e[i].w==
0)
continue;
int k=
dfs(y,min(rest,e[i].w));
if(!k)d[y]=
0;
rest-=k;e[i].w-=k;e[i^
1].w+=
k;
}
return flow-
rest;
}
int dinic(){
int ans=
0;
while(bfs())
while(
int flow=
dfs(s,inf))
ans+=
flow;
return ans;
}
int main(){
while(cin>>n>>np>>nc>>
m){
init();
s=
0;t=n+
1;
for(
int i=
1;i<=m;i++
){
int u,v,w;
scanf("\n(%d,%d)%d",&u,&v,&
w);
u++,v++
;
add(u,v,w);
}
for(
int i=
1;i<=np;i++
){
int u,w;
scanf("\n(%d)%d",&u,&
w);
++
u;
add(s,u,w);
}
for(
int i=
1;i<=nc;i++
){
int u,w;
scanf("\n(%d)%d",&u,&
w);
++
u;
add(u,t,w);
}
cout<<dinic()<<
'\n';
}
}
转载于:https://www.cnblogs.com/zsben991126/p/11004195.html
