记录编号	39291	评测结果	AAAAAAAAAA
题目名称	最小最大生成树	最终得分	100
用户昵称	CC	是否通过	通过
代码语言	C++	运行时间	1.682 s
提交时间	2012-07-08 16:42:37	内存使用	4.27 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 1000000000
struct bian {
	int x,y,v,index;
	bool av;
}d[200050];
struct edge {
	int y,c;
	edge *next,*opt;
	edge (int y,int c,edge *next): y(y),c(c),next(next) {};
}*a[20050];
int n,m,tot,P,Q,R,ans;
int level[20050];
bool cmp(bian a,bian b) {
	return a.v < b.v;
}
void create(int x,int y,int c) {
	a[x] = new edge(y,c,a[x]);
	a[y] = new edge(x,0,a[y]);
	a[x]->opt = a[y];a[y]->opt = a[x];
}
bool bfs() {
	memset(level,-1,sizeof(level));
	int q[100000] = {0},head = 0,tail = 0;
	level[P] = 0;
	q[0] = P;
	while (head <= tail) {
		int now = q[head++];
		for (edge *p = a[now];p;p = p->next) 
			if (p->c && level[p->y] == -1) 
				level[q[++tail] = p->y] = level[now] + 1;
	}
	return level[Q] != -1;
}
int extend(int u,int s) {
	int o = 0,t;
	if (u == Q) return s;
	for (edge *p = a[u];p && o < s;p = p->next) 
		if (p->c && level[p->y] == level[u] + 1) {
			t = p->c; if (t > s - o) t = s - o;
			t = extend(p->y,t);
			o += t;p->c -= t;p->opt->c += t;
		}
	if (!o) level[u] = -1;
	return o;
}
int dinic() {
	int tmp = 0,o;
	while (bfs()) {
		while((o = extend(P,INF))) 
			tmp += o;
	}
	return tmp;
}
void solve() {
	std::sort(d + 1,d + m + 1,cmp);
	for (int i = 1;i <= m;i++) {
		if (d[i].v < R) {
			create(d[i].x,d[i].y,1);
			create(d[i].y,d[i].x,1);
		} else {
			break;
		}
	}
	ans = dinic();
	memset(a,0,sizeof(a));
	for (int i = m;i >= 1;i--) {
		if (d[i].v > R) {
			create(d[i].x,d[i].y,1);
			create(d[i].y,d[i].x,1);
		} else {
			break;
		}
	}
	ans += dinic();
	printf("%d\n", ans);
}
int main() {
	freopen("mstmn.in","r",stdin);
	freopen("mstmn.out","w",stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= m;i++) {
		scanf("%d%d%d", &d[i].x, &d[i].y, &d[i].v);
		d[i].av = 1;d[i].index = i;
	}
	scanf("%d%d%d", &P, &Q, &R);
	d[++m].x = P;d[m].y = Q;d[m].v = R;d[m].av = 1;d[m].index = m;
	solve();
	return 0;
}