【BZOJ 1877】[SDOI2009] 晨跑

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1877
数据生成器：http://paste.ubuntu.com/23172606/

喜闻乐见大水题！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200*2+9;
const int M = 50000+9;
const int INF = 100000000;

int head[N],dis[N],nxt[M],cost[M],to[M],flow[M]; 
int n,m,S,T,F,C,inq[N],cur[N],sur[N];
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

#define id(x,ty) ((x)+n*(ty))
inline void Add_Edge(int u, int v, int f, int c) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline bool SPFA(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(S); inq[S] = 1; cur[S] = INF;
	
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=nxt[i]) if (flow[i])
			if (!~dis[to[i]] || dis[to[i]] > dis[w] + cost[i]) {
				sur[to[i]] = i;
				dis[to[i]] = dis[w] + cost[i]; 
				cur[to[i]] = min(flow[i], cur[w]);
				if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
			}
	}
	return ~dis[T];
}

inline void MCMF(){
	for (int w=T;SPFA();w=T) {
		F += cur[T];
		while (w != S) {
			flow[sur[w]] -= cur[T];
			flow[sur[w]^1] += cur[T];
			C += cur[T]*cost[sur[w]];
			w = to[sur[w]^1];
		}
	}
}

int main(){
	n = read(); m = read(); S = id(1,1); T = id(n,0);
	for (int i=2;i<n;i++) Add_Edge(id(i,0),id(i,1),1,0);
	for (int i=1,u,v,c;i<=m;i++) 
		u = read(), v = read(), c = read(),
		Add_Edge(id(u,1),id(v,0),1,c);
	MCMF();
	printf("%d %d\n",F,C);
	return 0;
}