gistfile1.cpp

#include <vector>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>

using namespace std;

long long min(long long a, long long b) {
	if (a < b) {
		return a;
	}
	return b;
}

struct G {
	const static long long oo = 1000000001;
	int size;
	vector<pair<int, long long> > * g;
	long long * dis;
	int * pre;

	G(int size) : size(size), g(new vector<pair<int, long long> >[size]), dis(new long long[size]), pre(new int[size]) {}
	virtual ~G() {
		delete [] g;
		delete [] dis;
		delete [] pre;
	}

	void addEdge(int l, int r, long long t) {
		g[l].push_back(make_pair(r, t));
	}

	void spfa(int s) {
		if (s < 0 || s >= size) {
			return;
		}
		bool * ex = new bool[size];
		for (int i = 0; i < size; i++) {
			dis[i] = oo;
			ex[i] = false;
			pre[i] = -1;
		}
		dis[s] = 0;
		ex[s] = true;
		int * q = new int[size + 1];
		int l = 0, r = 1;
		q[0] = s;
		while (l != r) {
			int u = q[l++];
			if (l >= size) {
				l = 0;
			}
			for (unsigned int i = 0; i < g[u].size(); i++) {
				int v = g[u][i].first;
				long long c = g[u][i].second;
				if (valid(u, v)) {
					if (dis[u] < dis[v] - c) {
						dis[v] = dis[u] + c;
						pre[v] = u;
						if (!ex[v]) {
							ex[v] = true;
							q[r++] = v;
							if (r >= size) {
								r = 0;
							}
						}
					}
				}
			}
			ex[u] = false;
		}
		delete [] q;
		delete [] ex;
	}

	virtual bool valid(int i, int j) {
		return true;
	}
};

struct MaxFlowG : public G {
	long long * flow;
	long long * lim;
	long long * c;

	MaxFlowG(int size) : G(size), flow(new long long[size * size]), lim(new long long[size * size]), c(new long long[size * size]) {
		memset(flow, 0, sizeof(long long) * size * size);
		memset(lim, 0, sizeof(long long) * size * size);
		memset(c, 0, sizeof(long long) * size * size);
	}

	virtual ~MaxFlowG() {
		delete flow;
		delete lim;
		delete c;
	}

	void addEdge(int l, int r, long long cost, long long li) {
		G::addEdge(l, r, cost);
		G::addEdge(r, l, -cost);
		lim[l * size + r] = li;
		c[l * size + r] = cost;
		c[r * size + l] = -cost;
	}

	pair<long long, long long> minCostMaxFlow(int s, int t, bool printOut) {
		long long cost = 0;
		long long maxFlow = 0;
		while (1) {
			spfa(s);
			if (pre[t] == -1) {
				break;
			}
			long long bot = oo;
			for (int current = t; current != s; current = pre[current]) {
				int p = pre[current];
				bot = min(bot, lim[p * size + current] - flow[p * size + current]);
			}
			maxFlow += bot;
			long long dCost = 0;
			for (int current = t; current != s; current = pre[current]) {
				flow[pre[current] * size + current] += bot;
				flow[current * size + pre[current]] -= bot;
				dCost += c[pre[current] * size + current];
			}
			cost += dCost * bot;
		}
		if (printOut) {
			for (int i = 1; i < size - 1; i++) {
				for (int j = 1; j < size - 1; j++) {
					if (flow[i * size + j] > 0) {
						printf("(%d, %d, %lld), ", i, j, c[i * size + j]);
					}
				}
			}
			printf("\n");
		}
		return make_pair(cost, maxFlow);
	}

	virtual bool valid(int i, int j) {
		return flow[i * size + j] < lim[i * size + j];
	}
private:
	void addEdge(int l, int r, long long c) {}
};

void spfaTest() {
	int ca;
	scanf("%d", &ca);
	while (ca--) {
		int n, m;
		scanf("%d%d", &n, &m);
		G g(n);
		G g2(n);
		while (m--) {
			int l, r, c;
			scanf("%d%d%d", &l, &r, &c);
			g.addEdge(l - 1, r - 1, c);
			g2.addEdge(r - 1, l - 1, c);
		}
		g.spfa(0);
		g2.spfa(0);
		long long ret = 0;
		for (int i = 0; i < n; i++) {
			ret += g.dis[i];
			ret += g2.dis[i];
		}
		printf("%lld\n", ret);
	}
}

void poj2516() {
	int n, m, k;
	long long req[50];
	while (scanf("%d%d%d", &n, &m, &k) == 3) {
		if (n == 0 && m == 0 && k == 0) {
			break;
		}
		MaxFlowG * g[50];
		for (int i = 0; i < k; i++) {
			g[i] = new MaxFlowG(n + m + 2);
		}
		for (int i = 0; i < k; i++) {
			req[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < k; j++) {
				int li;
				scanf("%d", &li);
				req[j] += li;
				g[j]->addEdge(m + i, n + m + 1, 0, li);
			}
		}
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j < k; j++) {
				int li;
				scanf("%d", &li);
				g[j]->addEdge(0, i, 0, li);
			}
		}
		for (int i = 0; i < k; i++) {
			for (int j = 1; j <= n; j++) {
				for (int jj = 1; jj <= m; jj++) {
					int c;
					scanf("%d", &c);
					g[i]->addEdge(jj, m + j, c, MaxFlowG::oo);
				}
			}
		}
		long long ret = 0;
		for (int i = 0; i < k; i++) {
			pair<long long, long long> ans = g[i]->minCostMaxFlow(0, n + m + 1, false);
			if (ans.second != req[i]) {
				goto DEAD;
			}
			ret += ans.first;
		}
		printf("%lld\n", ret);
		goto NEXT;
DEAD:
		printf("-1\n");
NEXT:
		for (int i = 0; i < k; i++) {
			delete g[i];
		}
	}
}

void bipartitle() {
	int N, M;
	scanf("%d%d", &N, &M);
	MaxFlowG * g = new MaxFlowG(N + M + 2);
	int l, r, c;
	for (int i = 1; i <= N; i++) {
		g->addEdge(0, i, 0, 1);
	}
	for (int i = N + 1; i <= N + M; i++) {
		g->addEdge(i, N + M + 1, 0, 1);
	}
	while (scanf("%d%d%d", &l, &r, &c) == 3) {
		g->addEdge(l, r, c, 1);
	}
	pair<long long, long long> ret = g->minCostMaxFlow(0, N + M + 1, true);
	printf("%lld %lld\n", ret.first, ret.second);
}

int main() {
	//spfaTest();
	//poj2516();
	bipartitle();
	return 0;
}