记录编号	26971	评测结果	AAAAAAAAAA
题目名称	朦胧之旅	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2011-07-30 14:49:19	内存使用	0.38 MiB

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN=5005;
const int oo=~0u>>2;

struct Node
{
	int v;
	Node *next;
	Node(int _v,Node *_next):v(_v),next(_next){}
	Node(){}
	void *operator new (size_t,void *p){return p;}
}*adj[MAXN],pool[MAXN],*mem=pool;

inline void addedge(int u,int v)
{
	adj[u]=new (mem++)Node(v,adj[u]);
}

int N;
int lv[MAXN],belong[MAXN],mat[MAXN];
bool bfs()
{
	queue<int> q;
	for(int i=1;i<=N;i++)
		if (belong[i]==0) 
		{
			if (mat[i]==0)
			{
				lv[i]=0;
				q.push(i);
			}
			else
				lv[i]=oo;
		}
	lv[0]=oo;
	while(q.size())
	{
		int u=q.front(),v;q.pop();
		for(Node *p=adj[u];p;p=p->next)
			if (lv[v=mat[p->v]]==oo)
			{
				lv[v]=lv[u]+1;
				q.push(v);
			}
		if (lv[0]!=oo)
			return true;
	}
	return false;
}

bool dfs(int u)
{
	for(Node *p=adj[u];p;p=p->next)
		if (lv[mat[p->v]]==lv[u]+1)
			if (mat[p->v]==0 || dfs(mat[p->v]))
			{
				mat[u]=p->v;
				mat[p->v]=u;
				return true;
			}
	lv[u]=oo;
	return false;
}

int ans;
void Hopcroft()
{
	while(bfs())
		for(int i=1;i<=N;i++)
			if (belong[i]==0 && mat[i]==0 && dfs(i))
				ans++;
}

bool used[MAXN];
int main()
{
	freopen("lovetravel.in","r",stdin);
	freopen("lovetravel.out","w",stdout);
	int M,S;
	scanf("%d%d%d",&N,&M,&S);
	memset(belong,-1,sizeof(belong));
	int minw=oo;
	for(int i=0;i<S;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v);
		belong[u]=0;
		belong[v]=1;
		if (w<minw)
			minw=w;
	}
	bool flag=false;
	for(int i=1;i<=N;i++)
		if (belong[i]==-1)
		{
			flag=true;
			break;
		}
	if (flag==false)
	{
		for(int i=1;i<=N && !flag;i++)
			if (lv[i]==0)
			{
				memset(used,false,sizeof(used));
				for(Node *p=adj[i];p;p=p->next)
					used[p->v]=true;
				for(int j=1;j<=N;j++)
					if (lv[j]==1 && !used[j])
					{
						flag=true;
						break;
					}
			}
	}
	if (flag)
	{
		Hopcroft();
		printf("0 %d\n",N-ans);
	}
	else
		printf("%d 2\n",minw);
	return 0;
}