记录编号	93740	评测结果	AAAAAAAAAA
题目名称	[SGU U252]铁路网	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-03-27 21:04:20	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=250,INF=0x7fffffff/2;
class EDGE{
public:
	int from,to,cap,flow,cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
int ansflow=0,anscost=0;
int N;//0到N
int S,T;
int n,m;
void addedge(int from,int to,int cap,int cost){
	edges.push_back((EDGE){from,to,cap,0,cost});
	edges.push_back((EDGE){to,from,0,0,-cost});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
bool SPFA(int S,int T){
	queue<int> Q;
	int f[SIZEN]={0};
	bool inq[SIZEN]={0};
	int father[SIZEN]={0};
	for(int i=0;i<=N;i++) f[i]=INF;
	f[S]=0,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			EDGE &now=edges[c[x][i]];
			if(now.flow>=now.cap) continue;
			if(f[x]+now.cost<f[now.to]){
				f[now.to]=f[x]+now.cost;
				father[now.to]=c[x][i];
				if(!inq[now.to]){
					inq[now.to]=true;
					Q.push(now.to);
				}
			}
		}
	}
	if(f[T]==INF) return false;
	int nowflow=INF,x;
	x=T;
	while(x!=S){
		EDGE &now=edges[father[x]];
		nowflow=min(nowflow,now.cap-now.flow);
		x=now.from;
	}
	ansflow+=nowflow,anscost+=nowflow*f[T];
	x=T;
	while(x!=S){
		edges[father[x]].flow+=nowflow;
		edges[father[x]^1].flow-=nowflow;
		x=edges[father[x]].from;
	}
	return true;
}
vector<int> nowans;
bool visit[SIZEN]={0};
int match[SIZEN]={0};
void findpath(int x){
	if(!x) return;
	visit[x]=true;
	nowans.push_back(x);
	if(match[x]){
		findpath(match[x]-n);
	}
}
void work(void){
	while(SPFA(S,T));
	printf("%d %d\n",n-ansflow,anscost);
	//下面注释中的内容是用来输出答案的
	/*int indeg[SIZEN]={0};
	for(int i=1;i<=n;i++){
		for(int j=0;j<c[i].size();j++){
			EDGE &now=edges[c[i][j]];
			if(now.to!=S&&now.to!=T&&now.cap==now.flow){
				indeg[now.to-n]++;
				match[i]=now.to;
				match[now.to]=i;
				break;
			}
		}
	}
	for(int i=n;i>=1;i--){
		if(!indeg[i]){
			nowans.clear();
			findpath(i);
			printf("%d ",nowans.size());
			for(int j=0;j<nowans.size();j++) printf("%d ",nowans[j]);printf("\n");
		}
	}*/
}
void init(void){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v+n,1,w);
	}
	N=2*n+1;
	S=0,T=N;
	for(int i=1;i<=n;i++) addedge(S,i,1,0);
	for(int i=1;i<=n;i++) addedge(n+i,T,1,0);
}
int main(){
	freopen("railwaycommunication.in","r",stdin);
	freopen("railwaycommunication.out","w",stdout);
	init();
	work();
	return 0;
}