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

ydc的博客

 
 
 

日志

 
 

bzoj 2001(hnoi 2010)城市建设  

2013-02-21 23:06:34|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这绝对是论文题!!

要我写题解尼玛这不是相当于叫我写论文吗!!!!!

 

精妙的运用了分治。

写一个work(l,r)函数,表示处理l~r的询问

然后我们删边缩点

①将[l,r]的边权变为-INF,如果某条边的边权不是-INF又被选了,他必须被选,我们可以把这条边权累加入答案并缩点

②将[l,r]的边权变为INF,如果某条边的边权不是INF又没被选就不可能被选了我们就可以把这条边删了

 

代码能力太弱,几乎就是抄何朴帆代码

刚开始一直没看懂他的并查集的什么action函数还有什么a,b数组,后面发现是做完之后还原用的于是就豁然开朗了

不够很诡异的是他并查集还原的的数组大小只开到了maxn*5的大小,这个5我想应该就是并查集复杂度的那个反阿克曼函数吧。不过他的程序中有没有用启发式合并,所以……路径压缩的并查集在随机数据下时间复杂度均摊下来很接近5?

这才是我心目中最优美的并查集啊

 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 20010
#define MAXM 50010
#define oo 10000000000000000LL
using namespace std;
typedef long long LL;
int n,m,q,pos[MAXM],num[MAXM],len[MAXM],father[MAXN];
int dis[MAXM];
LL ans;
struct Edge
{
    int u,v,num;
    LL dis;
    friend bool operator < (const Edge &a,const Edge &b){  return a.dis<b.dis;  }
}edge[MAXM];
struct Node
{
    int a[MAXM*5],b[MAXM*5],cnt;
    int Find(int p)
    {
        if(father[p]==p)  return p;
        int root;
        for(root=p;father[root]!=root;root=father[root]);
        for(int x;father[p]!=root;p=x)
        {
            x=father[p],father[p]=root;
            cnt++,a[cnt]=p,b[cnt]=x;
        }
        return root;
    }
    void merge(int x,int y)
    {
        x=Find(x),y=Find(y);
        if(x!=y)  cnt++,a[cnt]=x,b[cnt]=x,father[x]=y;
    }
    void Recover(int top=0)
    {
        for(;cnt!=top;cnt--)
            father[a[cnt]]=b[cnt];
    }
}G[20];
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
    Read(n),Read(m),Read(q);
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=1,a,b;i<=m;i++)
    {
        Read(a),Read(b),Read(dis[i]);
        edge[i].u=a,edge[i].v=b,edge[i].dis=dis[i],edge[i].num=i,pos[i]=i;
    }
    for(int i=1;i<=q;i++)
        Read(num[i]),Read(len[i]);
}
void work(int dep,int l,int r)
{
    Node &temp=G[dep];
    temp.cnt=0;
    if(l==r)
    {
        edge[pos[num[l]]].dis=dis[num[l]]=len[l];
        sort(edge+1,edge+m+1);
        for(int i=1;i<=m;i++)
            pos[edge[i].num]=i;
        LL nowans=ans;
        for(int i=1;i<=m;i++)
            if(temp.Find(edge[i].u)!=temp.Find(edge[i].v))
                nowans+=edge[i].dis,temp.merge(edge[i].u,edge[i].v);
        printf("%lld\n",nowans);
        temp.Recover();
        return ;
    }
    /*Contraction*/
    int tempm=m;
    LL tempans=ans;
    for(int i=l;i<=r;i++)
        edge[pos[num[i]]].dis=-oo;
    sort(edge+1,edge+m+1);
    for(int i=1;i<=m;i++)
        pos[edge[i].num]=i;
    static int id[MAXM],s;
    s=0;
    for(int i=1;i<=m;i++)
        if(temp.Find(edge[i].u)!=temp.Find(edge[i].v))
        {
            if(edge[i].dis!=-oo)  id[++s]=i,ans+=edge[i].dis;
            temp.merge(edge[i].u,edge[i].v);
        }
    temp.Recover();
    for(int i=1;i<=s;i++)
        temp.merge(edge[id[i]].u,edge[id[i]].v);
    /*Reduction*/
    int tempcnt=temp.cnt;
    for(int i=l;i<=r;i++)
        edge[pos[num[i]]].dis=oo;
    sort(edge+1,edge+m+1);
    for(int i=1;i<=m;i++)
        pos[edge[i].num]=i;
    s=0;
    for(int i=1;i<=m&&edge[i].dis!=oo;i++)
    {
        if(temp.Find(edge[i].u)!=temp.Find(edge[i].v))  temp.merge(edge[i].u,edge[i].v);
        else id[++s]=i;
    }
    temp.Recover(tempcnt);
    for(int i=s;i>=1;i--)
    {
        swap(edge[id[i]],edge[m]);
        pos[edge[id[i]].num]=id[i],pos[edge[m].num]=m--;
    }
    /*Recover*/
    for(int i=l;i<=r;i++)
        edge[pos[num[i]]].dis=dis[num[i]];
    int mid=(l+r)>>1;
    work(dep+1,l,mid),work(dep+1,mid+1,r);
    temp.Recover();
    m=tempm,ans=tempans;
}
int main()
{
    read();
    work(1,1,q);
    return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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