本文共 1833 字，大约阅读时间需要 6 分钟。

很妙的一题,但看完做法后才深知自己多傻逼

考虑怎样的边$(u,v,l)$可能在最小生成树上

首先我们会把权值小于$l$的边全部用来构造最小生成树

此时如果$u,v$不连通,我们就会选择这条边

所以问题的实质是让权值小于$l$的边连通性达到最大后,$u,v$仍然不连通

就是最小割了!!!把前面的边都加上去构成无向图,跑最小割

最大生成树同理

#include 
   
    using namespace std;const int maxn=5e6+10;const int inf=1e9;struct edge{
   	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow){
   	d[++cnt]=(edge){
   v,head[u],flow},head[u]=cnt;	d[++cnt]=(edge){
   u,head[v],0},head[v]=cnt;}int dis[maxn],n,m,s,t,l,ans1,ans2;bool bfs(int s,int  t){
   	queue
    
     q;	for(int i=0;i<=n;i++)	dis[i]=0;	dis[s]=1;  q.push( s );	while( !q.empty() )	{
   		int u=q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v=d[i].to;			if( dis[v]==0&&d[i].flow )			{
   				dis[v]=dis[u]+1;	q.push(v);				if( v==t )	return true;			}		}	}	return false;}int dinic(int u,int flow){
   	if( u==t )	return flow;	int res=flow;	for(int i=head[u]; i&&res ;i=d[i].nxt )	{
   		int v=d[i].to;		if( d[i].flow&&dis[v]==dis[u]+1 )		{
   			int temp=dinic(v,min(res,d[i].flow) );			if( temp==0 )	dis[v]=0;			d[i].flow-=temp; d[i^1].flow+=temp;			res-=temp;		}	}	return flow-res;}struct p{
       int l,r,w;    bool operator < ( const p&tmp ) const{
           return w
     
      > n >> m;	for(int i=1;i<=m;i++)        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w );    cin >> s >> t >> l;    sort( a+1, a+1+m );    for(int i=1;i<=m;i++)    {
           if( a[i].w >= l )    break;        add( a[i].l, a[i].r , 1 );        add( a[i].r, a[i].l , 1 );    }    while( bfs(s,t) )   ans1 += dinic(s,t);    cnt = 1;    for(int i=1;i<=n;i++)   head[i] = 0;    for(int i=m;i>=1;i--)    {
           if( a[i].w<=l )  break;        add( a[i].l, a[i].r , 1 );        add( a[i].r, a[i].l , 1 );    }    while( bfs(s,t) )   ans2 += dinic(s,t);    cout << ans1+ans2;}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115363754 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！