注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2561]最小生成树  

2015-06-20 15:48:31|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2561: 最小生成树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 872  Solved: 434
[Submit][Status][Discuss]

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

1

HINT

对于20%的数据满足N ≤ 10,M ≤ 20,L ≤ 20;
对于50%的数据满足N ≤ 300,M ≤ 3000,L ≤ 200;
对于100%的数据满足N ≤ 20000,M ≤ 200000,L ≤ 20000。

Source

Solution

新加的那条边要在最小生成树上,说明边权<L的边集不能使u、v连通。
另s=u,t=v,跑一遍网络流,答案为最小割,意思是至少删掉这么多条边以后才能使st不连通。
对于边权>L的情况同理

Code

/**************************************************************
    Problem: 2561
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:516 ms
    Memory:15528 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 20010
#define M 400010
int n,m,x[M],y[M],v[M],l,i;
#define min(a,b) (a<b?a:b)
struct NF{
    int la[N],et,d[N],q[N],l,r,s,t,cur[N];
    struct E{int to,flow,nxt;}e[M];
    void add(int x,int y){
        e[++et]=(E){y,1,la[x]},la[x]=et;
        e[++et]=(E){x,1,la[y]},la[y]=et;
    }
    int bfs(){
        memset(d,0,sizeof(d));
        for(q[l=r=0]=t,d[t]=1;l<=r;l++)
        for(int i=la[q[l]];i;i=e[i].nxt)
        if(e[i^1].flow&&!d[e[i].to])d[q[++r]=e[i].to]=d[q[l]]+1;
        return d[s];
    }
    int dfs(int x,int ret){
        if(x==t||ret==0)return ret;
        int tmp,flow=0;
        for(int&i=cur[x];i;i=e[i].nxt)
        if(d[e[i].to]+1==d[x]){
            tmp=dfs(e[i].to,min(e[i].flow,ret-flow));
            e[i].flow-=tmp,e[i^1].flow+=tmp,flow+=tmp;
            if(flow==ret)return flow;
        }
        return flow;
    }
    int maxflow(){
        int flow=0;
        while(bfs())memcpy(cur,la,sizeof(la)),flow+=dfs(s,1<<30);
        return flow;
    }
}G1,G2;
int main(){
    for(G1.et=G2.et=i=1,n=F(),m=F();i<=m;x[i]=F(),y[i]=F(),v[i]=F(),i++);
    for(G1.s=G2.s=F(),G1.t=G2.t=F(),l=F(),i=1;i<=m;i++){
        if(v[i]<l)G1.add(x[i],y[i]);
        if(v[i]>l)G2.add(x[i],y[i]);
    }
    printf("%d\n",G1.maxflow()+G2.maxflow());
}

  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018