记录编号	325831	评测结果	AAAAAAAAAA
题目名称	[SGU U252]铁路网	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2016-10-20 16:03:17	内存使用	0.28 MiB

#include <vector>
#include <iostream>
#include <fstream>
#include <list>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <cfloat>
#include <cmath>
using namespace std;
#define maxn 205
#define INF 0x7fffffff
class MCMF
{
	struct edge
	{
		int from, to;
		int rem, cost;
	};
	int s, t;
	int cost[maxn];
	int path[maxn];
	int flow[maxn];
	bool vis[maxn];
	vector<int> G[maxn];
	vector<edge> edges;
public:
	MCMF(int a, int b)
	{
		s = a;
		t = b;
	}
	void addedge(int f, int t, int fl, int ct)
	{
		edges.push_back((edge){f, t, fl, ct});
		edges.push_back((edge){t, f, 0, -ct});
		int k = edges.size();
		G[f].push_back(k-2);
		G[t].push_back(k-1);
	}
	bool spfa(int &fl, int &ct)
	{
		queue<int> q;
		memset(vis, false, sizeof(vis));
		for(int i = 0; i < maxn; i++)
			cost[i] = flow[i] = INF;
		vis[s] = true;
		flow[s] = INF;
		cost[s] = 0;
		q.push(s);
		while(q.size())
		{
			int c = q.front();
			q.pop();
			for(int i = 0; i < G[c].size(); i++)
			{
				edge &e = edges[G[c][i]];
				if(e.rem > 0 && cost[e.to] > cost[c] + e.cost)
				{
					cost[e.to] = cost[c] + e.cost;
					path[e.to] = G[c][i];
					flow[e.to] = min(flow[c], e.rem);
					if(!vis[e.to])
					{
						q.push(e.to);
						vis[e.to] = true;
					}
				}
			}
			vis[c] = false;
		}
		if(cost[t] == INF)
			return false;
		fl += flow[t];
		ct += cost[t] * flow[t];
		for(int cur = t; cur != s; cur = edges[path[cur]].from)
		{
			int p = path[cur];
			edges[p].rem -= flow[t];
			edges[p^1].rem += flow[t];
		}
		return true;
	}
	int mincmaxf(int &c)
	{
		int f = 0;
		c = 0;
		while(spfa(f, c));
		return f;
	}
};
int main()
{
    freopen("railwaycommunication.in", "r", stdin);
    freopen("railwaycommunication.out", "w", stdout);
    int n, m;
    scanf("%d %d", &n, &m);
    MCMF sol(0, n*2+1);
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        sol.addedge(a, b+n, 1, c);
    }
    for(int i = 1; i <= n; i++)
    {
        sol.addedge(0, i, 1, 0);
        sol.addedge(n+i, 2*n+1, 1, 0);
    }
    int c;
    int f = sol.mincmaxf(c);
    printf("%d %d\n", n-f, c);
	return 0;
}