2017-12-16

bzoj【2561】: 最小生成树

2561: 最小生成树

Description

　给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？

Input

　　第一行包含用空格隔开的两个整数，分别为N和M；
　　接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。
　　最后一行包含用空格隔开的三个整数，分别为u，v，和 L；
　　数据保证图中没有自环。　

Output

　输出一行一个整数表示最少需要删掉的边的数量。

Sample Input

3 2

3 2 1

1 2 3

1 2 2

Sample Output

HINT

对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；

　　对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200；

　　对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。

Source

2012国家集训队Round 1 day1

Solution

emmm我觉得这道题好劲啊….
然后又被cxy说是水题…~~我菜爆了~~

对于那条被放进去的边$(v,u,w)$：

如果存在一条边权值小于它，且能使$v,u$联通，那么这条边必须被切除

如果存在一条边权值大于它，且能使$v,u$联通，那么这条边必须被切除

以上两条分别是对于最小，最大生成树。
以下就只讨论最小生成树的情况，另外一个同理。

那么问题似乎就变成了，花费最小的代价将上述中满足条件的边切掉。
可以把$v,u$看作不同的两个集合。将小于$w$的边全都加入网络，跑一边最小割即可

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int rtn=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=0;
	for(;isdigit(ch);ch=getchar())rtn=(rtn<<1)+(rtn<<3)+ch-'0';
	return f?rtn:-rtn;
}
const int maxn=200010;
const int inf=1e9;
int n,m,v,u,w,cnt=1;
struct edge{
	int a,b,w;
}E[maxn];
struct node{
	int a,b,c,nt;
}e[maxn<<3];
struct Graph{
	int p[maxn>>2],dep[maxn>>2];
	inline void add(int x,int y,int z){
		e[++cnt].a=x,e[cnt].b=y,e[cnt].c=z;
		e[cnt].nt=p[x];p[x]=cnt;
		
		e[++cnt].a=y,e[cnt].b=x,e[cnt].c=w;
		e[cnt].nt=p[y];p[y]=cnt;
	}
	inline bool bfs(int s,int t){
		queue<int>q;
		memset(dep,0,sizeof(dep));
		dep[s]=1;q.push(s);
		while(q.size()){
			int k=q.front();q.pop();
			for(int i=p[k];i;i=e[i].nt){
				int kk=e[i].b;
				if(dep[kk]||!e[i].c)continue;
				dep[kk]=dep[k]+1;
				if(!dep[t])q.push(kk);
			}
		}return dep[t];
	}
	inline int dfs(int k,int t,int flow){
		if(k==t||!flow)return flow;
		int rtn=0;
		for(int i=p[k];i&&flow;i=e[i].nt){
			int kk=e[i].b;
			if(dep[kk]!=dep[k]+1||!e[i].c)continue;
			int a=dfs(kk,t,min(e[i].c,flow));
			flow-=a;rtn+=a;
			e[i].c-=a;e[i^1].c+=a;
		}
		if(!rtn)dep[k]=0;
		return rtn;
	}
	inline int Dinic(int s,int t){
		int rtn=0;
		while(bfs(s,t))
			rtn+=dfs(s,t,inf);
		return rtn;
	}
	inline void clear(){
		for(int i=1;i<=n;i++)p[i]=0;
		cnt=1;
	}
}G;
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++)E[i].a=read(),E[i].b=read(),E[i].w=read();
	v=read();u=read();w=read();
	for(int i=1;i<=m;i++)
		if(E[i].w<w)
			G.add(E[i].a,E[i].b,1);
	int ans=G.Dinic(v,u);
	G.clear();
	for(int i=1;i<=m;i++)
		if(E[i].w>w)
			G.add(E[i].a,E[i].b,1);
	ans+=G.Dinic(v,u);
	printf("%d\n",ans);
	return 0;
}