struct Edge {
int to, rev;
int cap;
bool is_cut; // 标记是否为割边
};
class MinCut {
private:
std::vector<Edge> G[MAXN];
int level[MAXN];
int iter[MAXN];
public:
// 添加一条从from到to,容量为cap的边
void addEdge(int from, int to, int cap) {
G[from].push_back({to, (int)G[to].size(), cap, false});
G[to].push_back({from, (int)G[from].size() - 1, 0, false});
}
// 构建层次图
bool bfs(int s, int t) {
memset(level, -1, sizeof(level));
std::queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (const auto& e : G[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
// 在层次图上寻找增广路
int dfs(int v, int t, int upTo) {
if (v == t) return upTo;
for (int &i = iter[v]; i < G[v].size(); ++i) {
Edge &e = G[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
int d = dfs(e.to, t, std::min(upTo, e.cap));
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
// 求最大流
int maxFlow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
memset(iter, 0, sizeof(iter));
int f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}
// 获取最小割的割边集合
std::vector<std::pair<int, int>> getMinCutEdges(int s) {
std::vector<std::pair<int, int>> cutEdges;
bool vis[MAXN] = {0};
std::queue<int> q;
q.push(s);
vis[s] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
for (const auto& e : G[v]) {
if (e.cap > 0 && !vis[e.to]) {
vis[e.to] = true;
q.push(e.to);
}
}
}
// 割边:从S集合到T集合的满流边
for (int u = 0; u < MAXN; ++u) {
if (vis[u]) {
for (const auto& e : G[u]) {
if (!vis[e.to] && G[e.to][e.rev].cap > 0) {
cutEdges.emplace_back(u, e.to);
}
}
}
}
return cutEdges;
}
// 清空图
void clear(int n) {
for (int i = 0; i <= n; ++i) G[i].clear();
}
};#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e4+5,M=1e5+5,inf=2147483647;
int x,y,z,n,m,s,t,st,ed;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Dinic{
int o,h,t,Q[N],dis[N],cur[N],head[N];LL maxflow;
Dinic(){o=1;}
struct QAQ{int to,next,flow;}a[M<<1];
inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=0,cur[i]=head[i];
h=1,t=0,Q[++t]=st,dis[st]=1;
while(h<=t){
Re x=Q[h++];
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&!dis[to=a[i].to]){
dis[to]=dis[x]+1,Q[++t]=to;
if(to==ed)return 1;
}
}
return 0;
}
inline int dfs(Re x,Re flow){
if(x==ed||!flow)return flow;
Re tmp=0,to,f;
for(Re i=cur[x];i;i=a[i].next){
cur[x]=i;
if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
if(flow==tmp)break;
}
}
return tmp;
}
inline void dinic(Re st,Re ed){while(bfs(st,ed))maxflow+=dfs(st,inf);}
}T1;
int main(){
in(n),in(m),in(s),in(t),st=n+1,ed=st+1;
while(m--)in(x),in(y),in(z),T1.add(x,y,z);
T1.add(st,s,inf),T1.add(t,ed,inf),T1.dinic(st,ed);
printf("%lld",T1.maxflow);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+3,M=1e5+3,inf=2e9;
int x,y,z,o=1,n,m,h,t,st,ed,Q[N],cyf[N],pan[N],pre[N],head[N];long long maxflow;
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=n;++i)pan[i]=0;
h=1,t=0,pan[st]=1,Q[++t]=st,cyf[st]=inf;
while(h<=t){
Re x=Q[h++];
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&!pan[to=a[i].to]){
cyf[to]=min(cyf[x],a[i].flow);
Q[++t]=to,pre[to]=i,pan[to]=1;
if(to==ed)return 1;
}
}
return 0;
}
inline void EK(Re st,Re ed){
while(bfs(st,ed)==1){
Re x=ed;maxflow+=cyf[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
int main(){
in(n),in(m),in(st),in(ed);
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,0);
EK(st,ed);
printf("%lld",maxflow);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4003,M=6e4+3,inf=2e9;
int n,m,x,y,z,st,ed;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Dinic{
int o,h,t,Q[N],dis[N],cur[N],head[N];
struct QAQ{int to,next,flow;}a[M<<1];
inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=n;++i)dis[i]=0,cur[i]=head[i];
h=1,t=0,dis[st]=1,Q[++t]=st;
while(h<=t){
Re x=Q[h++];
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&!dis[to=a[i].to]){
dis[to]=dis[x]+1,Q[++t]=to;
if(to==ed)return 1;
}
}
return 0;
}
inline int dfs(Re x,Re flow){
if(x==ed||!flow)return flow;
Re tmp=0,to,f;
for(Re i=cur[x];i;i=a[i].next){
cur[x]=i;
if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
if(flow==tmp)break;
}
}
return tmp;
}
int Q_o,dfn_O,ip[N],dfn[N],low[N],pan[N];
inline void tarjan(Re x){
dfn[x]=low[x]=++dfn_O,Q[++t]=x,pan[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow){
if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
else if(pan[to])low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x]){
++Q_o;
while(1){
ip[Q[t]]=Q_o,pan[Q[t]]=0;
if(x==Q[t--])break;
}
}
}
inline void sakura(){
while(bfs(st,ed))dfs(st,inf);
for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);
for(Re i=2;i<=o;i+=2)printf("%d %d\n",
(!a[i].flow&&ip[a[i^1].to]!=ip[a[i].to]),
(!a[i].flow&&ip[st]==ip[a[i^1].to]&&ip[a[i].to]==ip[ed]));
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(st),in(ed),T1.o=1;
while(m--)in(x),in(y),in(z),T1.add(x,y,z);
T1.sakura();
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5005,M=5e4+5,inf=2e9;
int x,y,z,w,n,m,s,t,st,ed;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct MCMF{
int o,h,t,cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost,maxflow;
MCMF(){o=1;}
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void add_(Re x,Re y,Re flow,Re w){a[++o].w=w,a[o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
inline void add(Re a,Re b,Re flow,Re w){add_(a,b,flow,w),add_(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(s),in(t),st=n+1,ed=st+1;
while(m--)in(x),in(y),in(z),in(w),T1.add(x,y,z,w);
T1.add(st,s,inf,0),T1.add(t,ed,inf,0),T1.EK(st,ed);
printf("%lld %lld\n",T1.maxflow,T1.mincost);
}
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5,M=2e6+5,inf=2e9;
int T,x,y,z,w,G,o=1,p,n,m,h,t,st,ed,maxp,cyf[N],pan[N],pre[N],dis[N],head[N],Map[11][11][11][11];LL mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;vector<int>key[11][11];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline int P(Re x,Re y,Re k){return (x-1)*m+y+k*n*m;}
int main(){
in(n),in(m),in(p),maxp=(1<<p)-1;st=(maxp+1)*n*m+1,ed=st+1;
in(T);while(T--)in(x),in(y),in(z),in(w),in(G),Map[x][y][z][w]=Map[z][w][x][y]=G?G:-1;
in(T);while(T--)in(x),in(y),in(G),key[x][y].push_back(G);
add_(st,P(1,1,0),1,0);
for(Re k=0;k<=maxp;++k)add_(P(n,m,k),ed,1,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
if(!key[i][j].empty())
for(Re O=0;O<key[i][j].size();++O){
Re KEY=key[i][j][O];
for(Re k=0;k<=maxp;++k){
if(!((k>>KEY-1)&1))add_(P(i,j,k),P(i,j,k|(1<<KEY-1)),inf,0);
else{
if(i<n&&Map[i][j][i+1][j]!=-1){
if(!Map[i][j][i+1][j])add_(P(i,j,k),P(i+1,j,k),inf,1);
else if((k>>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1);
}
if(j<m&&Map[i][j][i][j+1]!=-1){
if(!Map[i][j][i][j+1])add_(P(i,j,k),P(i,j+1,k),inf,1);
else if((k>>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1);
}
if(i>1&&Map[i][j][i-1][j]!=-1){
if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1);
else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1);
}
if(j>1&&Map[i][j][i][j-1]!=-1){
if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1);
else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1);
}
}
}
}
else
for(Re k=0;k<=maxp;++k){
if(i<n&&Map[i][j][i+1][j]!=-1){
if(!Map[i][j][i+1][j])add_(P(i,j,k),P(i+1,j,k),inf,1);
else if((k>>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1);
}
if(j<m&&Map[i][j][i][j+1]!=-1){
if(!Map[i][j][i][j+1])add_(P(i,j,k),P(i,j+1,k),inf,1);
else if((k>>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1);
}
if(i>1&&Map[i][j][i-1][j]!=-1){
if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1);
else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1);
}
if(j>1&&Map[i][j][i][j-1]!=-1){
if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1);
else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1);
}
}
EK(st,ed);
if(maxflow)printf("%lld",mincost);
else printf("-1");
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1200,M=1865,inf=2e9;
int o=1,n,m,h,t,st,ed,O,Poi[23][43],A[23][43],cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline void TAT1(){
for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,1,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j){
add_(Poi[i][j],Poi[i][j]+O,1,A[i][j]);
if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],1,0),add_(Poi[i][j]+O,Poi[i+1][j+1],1,0);
}
EK(st,ed);
printf("%lld\n",maxcost);
}
inline void TAT2(){
for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,inf,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j){
add_(Poi[i][j],Poi[i][j]+O,inf,A[i][j]);
if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],1,0),add_(Poi[i][j]+O,Poi[i+1][j+1],1,0);
}
EK(st,ed);
printf("%lld\n",maxcost);
}
inline void TAT3(){
for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,inf,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j){
add_(Poi[i][j],Poi[i][j]+O,inf,A[i][j]);
if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],inf,0),add_(Poi[i][j]+O,Poi[i+1][j+1],inf,0);
}
EK(st,ed);
printf("%lld\n",maxcost);
}
inline void CL(){
memset(head,0,sizeof(head));
memset(cyf,0,sizeof(cyf));
memset(pre,0,sizeof(pre));
memset(a,0,sizeof(a));
maxflow=maxcost=0,o=1;
}
int main(){
in(m),in(n);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j)
in(A[i][j]),Poi[i][j]=++O;
st=O<<1|1,ed=st+1;
TAT1(),CL(),TAT2(),CL(),TAT3();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=3e4+5,inf=2e9;
int x,n,m,h,t,o=1,T,st,ed,ans,maxflow,Q[N],cur[N],dis[N],head[N],wi[4]={0,0,1,-1},wj[4]={1,-1,0,0};
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re z){add(x,y,z),add(y,x,0);}
inline int bfs(Re st,Re ed){//bfs求源点到所有点的最短路
for(Re i=0;i<=ed;++i)cur[i]=head[i],dis[i]=0;//当前弧优化cur=head
h=1,t=0,dis[st]=1,Q[++t]=st;
while(h<=t){
Re x=Q[h++],to;
for(Re i=head[x];i;i=a[i].next)
if(a[i].flow&&!dis[to=a[i].to]){
dis[to]=dis[x]+1,Q[++t]=to;
if(to==ed)return 1;
}
}
return 0;
}
inline int dfs(Re x,Re flow){//flow为源点到x的路径上的最小边权
if(!flow||x==ed)return flow;//发现没有流了或者到达终点即可返回
Re tmp=0,to,f;
for(Re i=cur[x];i;i=a[i].next){
cur[x]=i;//当前弧优化cur=i
if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
//若边权为0,不满足增广路性质,此时dfs返回值f为0,不必执行下面了
a[i].flow-=f,a[i^1].flow+=f;
tmp+=f;//记录终点已经有了多少流
if(!(flow-tmp))break;//前面那些儿子都是最短路,这些最优路径已经榨干了从x出来的所有流,后面的都不用管了
}
}
return tmp;
}
inline void Dinic(Re st,Re ed){
Re flow=0;maxflow=0;
while(bfs(st,ed))maxflow+=dfs(st,inf);
}
inline int Poi(Re i,Re j){return (i-1)*m+j;}
int main(){
in(n),in(m),st=n*m+1,ed=st+1;
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j){
in(x),ans+=x;
if((i+j)%2)add_(st,Poi(i,j),x);
else add_(Poi(i,j),ed,x);
}
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
if((i+j)%2)for(Re k=0;k<4;++k){
Re ni=i+wi[k],nj=j+wj[k];
if(ni>=1&&ni<=n&&nj>=1&&nj<=m)add_(Poi(i,j),Poi(ni,nj),inf);
}
Dinic(st,ed);
printf("%d\n",ans-maxflow);
}#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=11e4+5,M=6e5+5,inf=2e9;
int x,y,z,w,o=1,n,m,h,t,A,B,C,K,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline int P(Re x,Re y,Re k){return (x-1)*n+y+k*n*n;}
int main(){
in(n),in(K),in(A),in(B),in(C),st=(K+1)*n*n+1,ed=st+1;
add_(st,P(1,1,0),1,0);
for(Re k=1;k<=K;++k)add_(P(n,n,k),ed,1,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=n;++j){
in(x);
if(x){
for(Re k=1;k<=K;++k)add_(P(i,j,k),P(i,j,0),inf,A);
if(i<n)add_(P(i,j,0),P(i+1,j,1),inf,0);
if(j<n)add_(P(i,j,0),P(i,j+1,1),inf,0);
if(i>1)add_(P(i,j,0),P(i-1,j,1),inf,B);
if(j>1)add_(P(i,j,0),P(i,j-1,1),inf,B);
}
else{
for(Re k=0;k<K;++k){
if(i<n)add_(P(i,j,k),P(i+1,j,k+1),inf,0);
if(j<n)add_(P(i,j,k),P(i,j+1,k+1),inf,0);
if(i>1)add_(P(i,j,k),P(i-1,j,k+1),inf,B);
if(j>1)add_(P(i,j,k),P(i,j-1,k+1),inf,B);
}
add_(P(i,j,K),P(i,j,0),1,A+C);
}
}
EK(st,ed);
printf("%lld",mincost);
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=260,M=1540,inf=2e9;
int x,y,z,o=1,n,m,h,t,Q1,Q2,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline int Poi(Re x,Re y){return (x-1)*m+y;}
int main(){
in(Q1),in(Q2),in(n),in(m),++n,++m,st=n*m+1,ed=st+1;
for(Re i=1;i<=n;++i)
for(Re j=1;j<m;++j)
in(x),add_(Poi(i,j),Poi(i,j+1),1,x),add_(Poi(i,j),Poi(i,j+1),inf,0);
for(Re j=1;j<=m;++j)
for(Re i=1;i<n;++i)
in(x),add_(Poi(i,j),Poi(i+1,j),1,x),add_(Poi(i,j),Poi(i+1,j),inf,0);
while(Q1--)in(z),in(x),in(y),add_(st,Poi(x+1,y+1),z,0);
while(Q2--)in(z),in(x),in(y),add_(Poi(x+1,y+1),ed,z,0);
EK(st,ed);
printf("%lld",maxcost);
}
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<queue>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=40000,inf=2e9;
int x,y,o=1,n,m,h,t,st,ed,flag,cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;string CH,ch[N];map<string,int>ip;
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){//�·
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline void dfs1(Re x){
pan[x]=1;
cout<<ch[x-n]<<endl;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)<=n&&!a[i].flow){dfs1(to+n);break;}
}
inline void dfs2(Re x){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)<=n&&!a[i].flow&&!pan[to+n])dfs2(to+n);
cout<<ch[x-n]<<endl;
}
int main(){
cin>>n>>m;st=1,ed=n<<1;
for(Re i=1;i<=n;++i)cin>>ch[i],ip[ch[i]]=i;
for(Re i=2;i<n;++i)add_(i,n+i,1,1);
add_(1,1+n,2,1),add_(n,n+n,2,1);
while(m--){
cin>>CH;x=ip[CH];
cin>>CH;y=ip[CH];
if(x>y)swap(x,y);
flag|=x==1&&y==n;
add_(x+n,y,1,0);
}
EK(st,ed);
if(maxflow==2)printf("%d\n",maxcost-2);
else if(maxflow==1&&flag){
printf("2\n");
cout<<ch[1]<<endl<<ch[n]<<endl<<ch[1]<<endl;
return 0;
}
else return !printf("No Solution!\n");
for(Re i=1;i<=n+2;++i)pan[i+n]=0;
dfs1(1+n),dfs2(1+n);
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=103,inf=2e9;
int o=1,n,h,t,S,st,ed,A[N],cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost;
struct QAQ{int w,to,next,flow;}a[N<<3];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=n;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
int main(){
in(n);st=n+1,ed=n+2;
for(Re i=1;i<=n;++i)in(A[i]),S+=A[i];S/=n;
for(Re i=1;i<=n;++i){
if(i>1)add_(i,i-1,inf,1),add_(i-1,i,inf,1);
if(A[i]>S)add_(st,i,A[i]-S,0);
else if(A[i]<S)add_(i,ed,S-A[i],0);
}
add_(1,n,inf,1),add_(n,1,inf,1);
n+=2;EK(st,ed);
printf("%lld",mincost);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=205,M=10205,inf=2e9;
int o=1,n,m,h,t,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N],Flow[N][2],Cost[N][N];LL mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
int main(){
in(n),in(m),st=n+m+1,ed=st+1;
for(Re i=1;i<=n;++i)in(Flow[i][0]),add_(st,i,Flow[i][0],0);
for(Re i=1;i<=m;++i)in(Flow[i][1]),add_(n+i,ed,Flow[i][1],0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
in(Cost[i][j]),add_(i,n+j,inf,Cost[i][j]);
EK(st,ed);
printf("%lld\n",mincost);
memset(head,0,sizeof(head));
memset(cyf,0,sizeof(cyf));
memset(pre,0,sizeof(pre));
memset(a,0,sizeof(a));
o=1;maxflow=mincost=0;
for(Re i=1;i<=n;++i)add_(st,i,Flow[i][0],0);
for(Re i=1;i<=m;++i)add_(n+i,ed,Flow[i][1],0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
add_(i,n+j,inf,-Cost[i][j]);
EK(st,ed);
printf("%lld\n",-mincost);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=2e9;
int x,y,n,m,o=1,h,t,st,ed,ans,maxflow,Q[N],dis[N],head[N];
struct QAQ{int to,next,flow;}a[N*N*2+N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=n+2;++i)dis[i]=0;
h=1,t=0,dis[st]=1,Q[++t]=st;
while(h<=t){
Re to,x=Q[h++];
for(Re i=head[x];i;i=a[i].next)
if(a[i].flow&&!dis[to=a[i].to]){
dis[to]=dis[x]+1,Q[++t]=to;
if(to==ed)return 1;
}
}
return 0;
}
inline int dfs(Re x,Re flow){
if(!flow||x==ed)return flow;
Re tmp=0,to,f;
for(Re i=head[x];i;i=a[i].next)
if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
if(flow==tmp)break;
}
return tmp;
}
inline void Dinic(Re st,Re ed){
Re flow=0;while(bfs(st,ed))while(flow=dfs(st,inf))maxflow+=flow;
}
int main(){
in(m),in(n),st=n+1,ed=n+2;
while(1){
in(x),in(y);
if(x==-1)break;
add(x,y,1),add(y,x,0);
}
for(Re i=1;i<=m;++i)add(st,i,1),add(i,st,0);
for(Re i=m+1;i<=n;++i)add(i,ed,1),add(ed,i,0);
Dinic(st,ed);
printf("%d\n",maxflow);
for(Re x=1;x<=m;++x)
for(Re i=head[x];i;i=a[i].next)
if(!(i&1)&&a[i].to!=st&&!a[i].flow)printf("%d %d\n",x,a[i].to);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=2e9;
int x,y,n,m,o=1,h,t,st,ed,ans,maxflow,cyf[N],Q[N],pre[N],pan[N],head[N];
struct QAQ{int to,next,flow;}a[N*N*2+N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=n+2;++i)pan[i]=0;
h=1,t=0,pan[st]=1,cyf[st]=inf,Q[++t]=st;
while(h<=t){
Re to,x=Q[h++];
for(Re i=head[x];i;i=a[i].next)
if(a[i].flow&&!pan[to=a[i].to]){
cyf[to]=min(cyf[x],a[i].flow);
pan[to]=1,pre[to]=i,Q[++t]=to;
if(to==ed)return 1;
}
}
return 0;
}
inline void EK(Re st,Re ed){
while(bfs(st,ed)){
maxflow+=cyf[ed];
Re x=ed;
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
int main(){
in(m),in(n),st=n+1,ed=n+2;
while(1){
in(x),in(y);
if(x==-1)break;
add(x,y,1),add(y,x,0);
}
for(Re i=1;i<=m;++i)add(st,i,1),add(i,st,0);
for(Re i=m+1;i<=n;++i)add(i,ed,1),add(ed,i,0);
EK(st,ed);
printf("%d\n",maxflow);
for(Re x=1;x<=m;++x)
for(Re i=head[x];i;i=a[i].next)
if(!(i&1)&&a[i].to!=st&&!a[i].flow)printf("%d %d\n",x,a[i].to);
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define Re register int
using namespace std;
const int N=1e5+5,inf=2e9;
int h,t,n,p,o=1,st,ed,cnt,maxflow,Q[N],zhu[N],ans[N],pan[N],pre[N],dis[N],head[N];
struct QAQ{int to,flow,next;}a[N<<1];vector<int>Ans[N];
inline void add(Re x,Re y,Re flow){a[++o].flow=flow,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re flow){add(x,y,flow),add(y,x,0);}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=0;
h=1,t=0,dis[st]=1,Q[++t]=st;
while(h<=t){
Re x=Q[h++],to;
for(Re i=head[x];i;i=a[i].next)
if(a[i].flow&&!dis[to=a[i].to]){
dis[to]=dis[x]+1,Q[++t]=to;
if(to==ed)return 1;
}
}
return 0;
}
inline int dfs(Re x,Re flow){
if(!flow||x==ed)return flow;
Re tmp=0,to,f;
for(Re i=head[x];i;i=a[i].next)
if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
a[i].flow-=f,a[i^1].flow+=f;
tmp+=f,pre[to]=i;
if(!(flow-tmp))break;
}
return tmp;
}
inline void Dinic(Re st,Re ed){
Re flow=0;maxflow=0;
while(bfs(st,ed))while(flow=dfs(st,inf))maxflow+=flow;
}
int main(){
// freopen("123.txt","r",stdin);
scanf("%d",&n),st=1e5+1,ed=st+1;
while(ans[0]<=n){
++p;
add_(st,p<<1,1),add_(p<<1|1,ed,1);
for(Re j=sqrt(p)+1;j*j-p<=p-1;++j)add_((j*j-p)<<1,(p<<1)|1,1);
Dinic(st,ed);
if(!maxflow)ans[++ans[0]]=p,Ans[zhu[p]=ans[0]].push_back(p);
else{
Re x=p<<1|1;
while(!zhu[x-1>>1])x=a[pre[x]^1].to+1;
Ans[zhu[x-1>>1]].push_back(p);
}
}
printf("%d\n",p-1);
for(Re i=1;i<=n;puts(""),++i)
for(Re j=0;j<Ans[i].size();++j)
printf("%d ",Ans[i][j]);
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define Re register int
using namespace std;
const int N=1e5+5,inf=2e9;
int h,t,n,p,o=1,st,ed,cnt,maxflow,Q[N],zhu[N],ans[N],pan[N],pre[N],cyf[N],head[N];
struct QAQ{int to,flow,next;}a[N<<1];vector<int>Ans[N];
inline void add(Re x,Re y,Re flow){a[++o].flow=flow,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re flow){add(x,y,flow),add(y,x,0);}
inline int bfs(Re st,Re ed){
for(Re i=1;i<=ed;++i)pan[i]=0;
h=1,t=0,pan[st]=1,Q[++t]=st,cyf[st]=inf;
while(h<=t){
Re x=Q[h++];
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&!pan[to=a[i].to]){
cyf[to]=min(cyf[x],a[i].flow);
pan[Q[++t]=to]=1,pre[to]=i;
if(to==ed)return 1;
}
}
return 0;
}
inline void EK(Re st,Re ed){
Re x,flow=0;maxflow=0;
while(bfs(st,ed)){
x=ed,maxflow+=cyf[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
int main(){
// freopen("123.txt","r",stdin);
scanf("%d",&n),st=1e5+1,ed=st+1;
while(ans[0]<=n){
++p;
add_(st,p<<1,1),add_(p<<1|1,ed,1);
for(Re j=sqrt(p)+1;j*j-p<=p-1;++j)add_((j*j-p)<<1,(p<<1)|1,1);
EK(st,ed);
if(!maxflow)ans[++ans[0]]=p,Ans[zhu[p]=ans[0]].push_back(p);
else{
Re x=p<<1|1;
while(!zhu[x-1>>1])x=a[pre[x]^1].to+1;
Ans[zhu[x-1>>1]].push_back(p);
}
}
printf("%d\n",p-1);
for(Re i=1;i<=n;puts(""),++i)
for(Re j=0;j<Ans[i].size();++j)
printf("%d ",Ans[i][j]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=4e4+5,M=7e4+3,inf=2e9;
int x,y,z,o=1,n1,n2,n3,nn,m,h,t,st,ed,Q[N],dis[N],pan[N],pre[N],head[N];long long maxflow;
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re flow){add(x,y,flow),add(y,x,0);}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=0;
h=1,t=0,dis[st]=1,Q[++t]=st;
while(h<=t){
Re x=Q[h++],to;
for(Re i=head[x];i;i=a[i].next)
if(a[i].flow&&!dis[to=a[i].to]){
dis[to]=dis[x]+1,Q[++t]=to;
if(to==ed)return 1;
}
}
return 0;
}
inline int dfs(Re x,Re flow){
if(!flow||x==ed)return flow;
Re tmp=0,to,f;
for(Re i=head[x];i;i=a[i].next)
if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
if(!(flow-tmp))break;
}
return tmp;
}
inline void Dinic(Re st,Re ed){
Re flow=0;
while(bfs(st,ed))while(flow=dfs(st,inf))maxflow+=flow;
}
int main(){
freopen("123.txt","r",stdin);
in(n1),in(n2),in(n3);nn=n1+n2+n3,st=nn+n1+1,ed=st+1;
for(Re i=1;i<=n1;++i)add_(i,i+nn,1);
for(Re i=1;i<=n2;++i)add_(st,n1+i,1);
for(Re i=1;i<=n3;++i)add_(n1+n2+i,ed,1);
in(m);while(m--)in(x),in(y),add_(n1+y,x,1);
in(m);while(m--)in(x),in(y),add_(x+nn,n1+n2+y,1);
Dinic(st,ed);
printf("%lld",maxflow);
}