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

n+e

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

 
 
 

日志

 
 

[BZOJ1937][Shoi2004]Mst 最小生成树  

2015-03-16 21:40:37|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1937: [Shoi2004]Mst 最小生成树

Time Limit: 3 Sec  Memory Limit: 64 MB
Submit: 284  Solved: 104
[Submit][Status][Discuss]

Description

Input

第一行为N、M,其中 表示顶点的数目, 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行,每行三个整数Ui,Vi,Wi,表示顶点Ui与Vi之间有一条边,其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行,每行两个整数Xi、Yi,表示顶点Xi与Yi之间的边是T的一条边。

Output

输出最小权值

Sample Input

6 9 1 2 2 1 3 2 2 3 3 3 4 3 1 5 1 2 6 3 4 5 4 4 6 7 5 6 6 1 3 2 3 3 4 4 5 4 6

Sample Output

8 【样例说明】 边(4,6)的权由7修改为3,代价为4 边(1,2)的权由2修改为3,代价为1 边(1,5)的权由1修改为4,代价为3 所以总代价为4+1+3=8 修改方案不唯一。

HINT

 1<=n<=50,1<=m<=750,1<=wi<=1000
n-->点数..m-->边数..wi--->边权

Solution

树边边权只能改小,非树边边权只能改大,不然不优
对于一个树边i和一个非树边j,若j覆盖i,则必有
wi-di<=wj+dj
di,dj为修改的边权权值。
即wi-wj<=di+dj
由于wi-wj为定值,因此可以这样连边:
add(s,树边,flow=1,cost=0)
add(非树边,t,flow=1,cost=0)
add(树边,非树边,flow=1,cost=wi-wj) (if(wi-wj>0))
跑最大费用可行流,应该可以证明流对应着一种原来的方案(感谢clbq指出错误)

假如有5个点,连边情况(x,y,v)=(1,3,3),(1,4,5),(2,3,4),(2,5,2),构成一个二分图
当第一条边满足时,第二条边不一定满足条件。但是第二条边满足条件时,可以调整证明第一条边也满足条件。
同理满足3必定满足4

至于为什么是可行流
[BZOJ1937][Shoi2004]Mst 最小生成树 - Trinkle - n+e
 显然流量为1时,ans=42,如果跑最大流的话,流量为2,ans=29,然后发现自己怎么搞也搞不出来

但是至今没看过km。。。

Code

/**************************************************************
    Problem: 1937
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:7112 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
const int N=800,M=200000;
int et=1,la[N],l,r,q[2000],in[N],p[N],dis[N],s,t,flow,cost;
struct E{int to,flow,cost,nxt;}e[M<<1];
void add(int x,int y,int f,int c){
    e[++et]=(E){y,f,c,la[x]},la[x]=et;
    e[++et]=(E){x,0,-c,la[y]},la[y]=et;
}
int bfs(){
    memset(dis,-63,sizeof(dis));
    for(q[l=r=1]=s,in[s]=1,dis[s]=0;l<=r;in[q[l++]]=0)
    for(int i=la[q[l]];i;i=e[i].nxt)
    if(e[i].flow&&dis[e[i].to]<dis[q[l]]+e[i].cost)
    dis[e[i].to]=dis[q[l]]+e[i].cost,p[e[i].to]=i,
    !in[e[i].to]?in[q[++r]=e[i].to]=1:1;
    return dis[t]>0;
}
int mincost(){
    while(bfs()){
        for(int u=t;u!=s;u=e[p[u]^1].to)
        e[p[u]].flow--,e[p[u]^1].flow++;
        flow++,cost+=dis[t];
    }
    return cost;
}
int n,m,x,y,v,i,j,fa[N],dep[N],pre[N],_et=1,_la[N];
struct D{int x,y,v,f;}d[N];
struct _E{int to,nxt;}_e[N];
#define _add(x,y) (_e[++_et]=(_E){y,_la[x]},_la[x]=_et)
void dfs(int x){
    for(int i=_la[x];i;i=_e[i].nxt)
    if(!dep[_e[i].to])
        dep[_e[i].to]=dep[x]+1,fa[_e[i].to]=x,
        pre[_e[i].to]=i>>1,dfs(_e[i].to);
}
int main(){
    scanf("%d%d",&n,&m);s=m+1,t=s+1;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&v);if(x>y)j=x,x=y,y=j;
        d[i]=(D){x,y,v,0};
    }
    for(i=1;i<n;d[j].f=1,i++){
        scanf("%d%d",&x,&y);if(x>y)j=x,x=y,y=j;
        for(j=1;j<=m&&!(d[j].x==x&&d[j].y==y);j++);
    }
    for(i=1;i<=m;i++)
    if(d[i].f)_add(d[i].x,d[i].y),_add(d[i].y,d[i].x),add(s,i,1,0);
    else _et+=2,add(i,t,1,0);
    for(dfs(dep[1]=1),i=1;i<=m;i++)
    if(d[i].f==0){
        if(dep[x=d[i].x]<dep[y=d[i].y])j=x,x=y,y=j;
        for(;dep[x]>dep[y];x=fa[x])
        if(d[pre[x]].v>d[i].v)add(pre[x],i,1,d[pre[x]].v-d[i].v);
        if(x!=y)for(;x!=y;x=fa[x],y=fa[y]){
            if(d[pre[x]].v>d[i].v)add(pre[x],i,1,d[pre[x]].v-d[i].v);
            if(d[pre[y]].v>d[i].v)add(pre[y],i,1,d[pre[y]].v-d[i].v);
        }
    }
    printf("%d",mincost());
}
  评论这张
 
阅读(636)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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