Source Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000;
const int oo=2000000007;
struct edge{
	int u,v,cap,next;
}E[N+N];
int n, L, R, e, ei;
int w[N], can[N], last[N];
vector<vector<int> > cg;
void addEdge(int u,int v, int cap){
	E[ei++] = {u,v,cap,last[u]};
	last[u] = ei-1;
	E[ei++] = {v,u,0,last[v]};
	last[v] = ei-1;
}
int low[N],idx[N], comp[N], id;
int val[N];
bool vis[N];
vector<int> S;
int dfs;
int findSCC(int u){
	S.push_back(u);
	vis[u] = true;
	low[u] = idx[u] = ++dfs;
	int minVal = oo;
	for(auto &v:cg[u]){
		if(low[v]==0)
			minVal = min(minVal, findSCC(v));
		if(vis[v])
			low[u] = min(low[u], low[v]);
		else
		    minVal = min(minVal, val[comp[v]]);
	}
	if(low[u] == idx[u]){
		val[id] = minVal;
		while(true){
			int x=S.back();
			S.pop_back();
			vis[x] = false;
			comp[x] = id;
			if(x >= L && can[x] > 0)
				val[id] = min(val[id], w[x]);
			if(x == u)
				break;
		}
	    return val[id++];
	}
	return minVal;
}
int findLeft(){
	cg.resize(n);
	for(auto &e:cg)
		e.clear();
	for(int i=0;i<ei;++i)
		if(E[i].cap > 0){
			cg[E[i].u].push_back(E[i].v);
		}
	memset(low,0,sizeof(low));
	dfs = 0;
	id = 0;
	for(int i=0;i<n;++i)
		if(low[i] == 0)
			findSCC(i);
	int at = -1, best = oo;
	for(int i=0;i<L;++i){
		if(can[i]==0)
			continue;
		int cur = val[comp[i]];
		if(cur == oo)
			continue;
		int total = w[i] + cur;
		if (best > total){
			best = total;
			at = i;
		}
	}
	return at;
}
int q[N], qf,ql;
int p[N];
pair<int,int> findRightAndFlow(int src) {
	q[qf=ql=0] = src;
	memset(p, -1, sizeof(p));
	int best = oo, at = -1;
	p[src] = src;
	while(qf<=ql){
		int u=q[qf++];
		for(int e=last[u]; e!=-1; e=E[e].next){
			if(E[e].cap == 0 || p[E[e].v] != -1)
				continue;
			p[E[e].v] = e;
			q[++ql] = E[e].v;
			if(E[e].v >= L && can[E[e].v] > 0){
				if(best > w[E[e].v]){
					best = w[E[e].v];
					at = E[e].v;
				}
			}
		}
	}
	assert(at != -1);
	int flow = min(can[src], can[at]);
	for(int cur=at; cur != src; cur = E[p[cur]].u){
		flow = min(flow, E[p[cur]].cap);
	}
	can[src] -= flow;
	can[at] -= flow;
	for(int cur=at; cur != src; cur = E[p[cur]].u){
		E[p[cur]].cap -= flow;
		E[p[cur] ^ 1].cap += flow;
	}
	return {at, flow};
}
pair<int,ll> minCostMaxFlow() {
	pair<int,ll> ret;
	int paths = 0;
	while(true) {
		int left = findLeft();
		if(left == -1)
			break;
		auto cur = findRightAndFlow(left);
		ret.first += cur.second;
		ret.second += cur.second * (ll)(w[left] + w[cur.first]);
		++paths;
	}
	fprintf(stderr, "paths = %d", paths);
	return ret;
}
int main() {
	scanf("%d%d%d",&L, &R, &e);
	n = L + R;
	memset(last,-1,sizeof(last));
	for(int i=0;i<n;++i)
		scanf("%d%d",&can[i], &w[i]);
	for(int i=0,a,b;i<e;++i){
		scanf("%d%d",&a,&b);
		--a;--b;
		addEdge(a,b+L, oo);
	}
	auto ret = minCostMaxFlow();
	printf("%d %lld\n",ret.first, ret.second);
	return 0;
}
Copy
Even Flow jester
GNU G++17
3260 ms
2.0 MB
Accepted