[SDOI2009]晨跑

题目描述
Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校，保证寝室编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以 在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。Elaxia耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天 数尽量长。 除了练空手道，Elaxia其他时间都花在了学习和找MM上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。

存在1→n的边存在。这种情况下，这条边只能走一次。

输入格式
第一行：两个数N,M。表示十字路口数和街道数。 接下来M行，每行3个数a,b,c，表示路口a和路口b之间有条长度为c的街道（单向）。

输出格式
两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长 度。

输入输出样例
输入 #1 复制
7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1
输出 #1 复制
2 11
说明/提示
对于30%的数据，N ≤ 20，M ≤ 120。

对于100%的数据，N ≤ 200，M ≤ 20000。

很明显的费用流，现在主要目的就是建图。题目要求一个点只能经过一次，所以我们拆点限流即可，建图完毕。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=410,M=8e4+10;
const int inf=0x3f3f3f3f;
int n,m,h[N],s,t,v[N],e[N],d[N];
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	w[++tot]=d; flow[tot]=c; to[tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(d,inf,sizeof d);	d[s]=0;	queue<int> q;	q.push(s);
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=inf;
}
void EK(){
	int res=0,maxflow=0;
	while(spfa()){
		int mi=0x3f3f3f3f;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=d[t];	maxflow+=mi;
	}
	cout<<maxflow<<' '<<res<<endl;
}
signed main(){
	cin>>n>>m;	s=1;	t=n<<1;
	for(int i=1;i<=n;i++){
		if(i==1||i==n)	add(i*2-1,i<<1,inf,0);
		else	add(i*2-1,i<<1,1,0);
	}
	while(m--){
		int a,b,c;	cin>>a>>b>>c;	add(a*2,b*2-1,1,c);
	}
	EK();
	return 0;
}