#include<iostream>
#define MAXN 105
#include"queue"
#define big_num 100000000
using namespace std; int _m[MAXN][MAXN];
int Ford_fulkerson(int n, int s, int t, int &F,int g[][MAXN]);
int main()
{
//freopen("acm.acm","r",stdin);
int point;
int np;
int nc;
int edge;
char left;
char right;
char space;
int flow;
int u;
int v;
int i;
int node;
while(cin>>point>>np>>nc>>edge)
{
memset(_m,,sizeof(_m));
for(i = ; i < edge; ++ i)
{
cin>>left;
cin>>u;
cin>>space;
cin>>v;
cin>>right;
cin>>flow;
++ u;
++ v;
_m[u][v] = flow;
}
for(i = ; i < np; ++ i)
{
cin>>left;
cin>>u;
cin>>right;
cin>>flow;
++ u;
_m[][u] = flow;
}
for(i = ; i < nc; ++ i)
{
cin>>left;
cin>>u;
cin>>right;
cin>>flow;
++ u;
_m[u][point+] = flow;
}
int F = ;
while(Ford_fulkerson(point+,,point + ,F,_m));
cout<<F<<endl;
}
} int find_path(int m, int s,int t,int pre[MAXN],int g[][MAXN])
{
queue<int> q;
int * mark = new int[m];
memset(mark,,sizeof(int)*m);
int x;
mark[s] = ;
int i;
q.push(s);
while(!q.empty())
{
x = q.front();
for(i = ; i < m; i++)
{
if(g[x][i] > && mark[i] == )
{
mark[i] = ;
pre[i] = x;
if(i == t)
return ;
q.push(i);
}
}
q.pop();
}
delete [] mark;
return ;
}
int Ford_fulkerson(int n, int s, int t, int &F,int g[][MAXN])
{
int i;
int min;
int * pre = new int[n];
if(find_path(n,s,t,pre, g) == )
{
delete [] pre;
return ;
}
min = big_num;
for(i = t; i != s; i = pre[i])
if(g[pre[i]][i] < min)
{
min = g[pre[i]][i];
}
for(i = t; i != s; i = pre[i])
{
g[pre[i]][i] -= min;
g[i][pre[i]] += min;
}
F += min;
delete []pre;
return ;
}
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com