记录编号	436064	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] 晨跑	最终得分	100
用户昵称	LCWhiStLe	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2017-08-10 21:49:55	内存使用	12.36 MiB

/*
	事实证明 vector 的确 比链表 跑得快
	开O2后直接起飞 
*/
#include<queue>
#include<vector>
#include<cstdio>
#include<iostream>
#define MAXN 20010

using namespace std;

const int INF=0x7fffffff;
const int N=810;

int n,m,a,b,c,ans1,ans2,decc,src;

int dis[N<<1],pre[N<<1],f[2][N<<1][N<<1];

bool vis[N<<1];

vector<int> e[MAXN];

queue<int> q;

inline void read(int&x) {
	int f=1;x=0;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();}
	x=x*f;
}

inline void add(int x,int y,int v,int fee) {
	e[x].push_back(y);
	f[0][x][y]=v;
	f[1][x][y]=fee;
}

inline void add_edge(int x,int y,int v,int f) {
	add(x,y,v,f);add(y,x,0,-f);
}

bool spfa() {
	for(int i=1;i<=n<<1;i++) dis[i]=INF,vis[i]=false,pre[i]=-1;
	while(!q.empty()) q.pop();
	q.push(src);
	dis[src]=0;
	vis[src]=true;
	pre[src]=0;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=0;i<e[u].size();i++) {
			int to=e[u][i];
			if(f[0][u][to]&&dis[to]>dis[u]+f[1][u][to]) {
				dis[to]=dis[u]+f[1][u][to];
				pre[to]=u;
				if(!vis[to]) {
					q.push(to);
					vis[to]=true;
				}
			}
		}
	}
	return dis[decc]!=INF;
}

inline int change() {
	int flow=INF;ans1++;
	for(int i=decc;i!=1;i=pre[i])
	  flow=min(flow,f[0][pre[i]][i]);
	for(int i=decc;i!=1;i=pre[i]) {
		f[0][pre[i]][i]-=flow;
		f[0][i][pre[i]]+=flow;
	} 
	return flow*dis[decc];
}

inline void ISPA() {
	while(spfa())
	  ans2+=change();
	return;
}

inline int hhh() {
	freopen("run.in","r",stdin);
	freopen("run.out","w",stdout);
	read(n);read(m);
	src=1;decc=n<<1;
	for(int i=1;i<=m;i++) {
		read(a);read(b);read(c);
		add_edge(a+n,b,1,c);
	}
	for(int i=2;i<n;i++) add_edge(i,i+n,1,0);
	add_edge(1,1+n,INF,0);
	add_edge(n,n<<1,INF,0);
	ISPA();
	printf("%d %d\n",ans1,ans2);
	return 0;
}

int sb=hhh();
int main() {;}