加载中…
个人资料
lovedream
lovedream
  • 博客等级:
  • 博客积分:0
  • 博客访问:59,807
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

HDU4126——福州赛F题

(2011-11-28 21:38:00)
标签:

杂谈

分类: ACM/ICPC解题报告

朴素思路是n^3的,求出每条边的“最佳替换边”,不作具体介绍。

讲2种思路:

第一种是来自PHT大牛的:在MST上DFS,每到一个节点,枚举其所有不属于MST的边,若未标记,则加入一个最小堆中,标记之;否则将其从最小堆中删除(取消标记即可)。且对于没条当前边,不断pop直到堆顶元素已被标记,此时堆顶的边就是当前边的“最佳替换边”。复杂度是O(mlogm)。

第二种是我自己YY的:求得MST后,从小到大枚举不在MST中的边,加入到MST中,则必成环,缩环成点,环上的边的“最佳替换边”就是当前枚举的边了。复杂度是O(n^2),不过由于“从小到大枚举边”,这个排序过程本身就是O(mlogm)因此总复杂度和第一种一样。

下面代码是第二种方法写的,很挫。

#include<stdio.h>
#include<string.h>
#include<algorithm>
const int INF=2100000000;

int wh[3005][3005],first[3005],next[11000],vv[11000],fa[3005],best[11000];
short bel[4550000];
int N,dis[3005];

int find_fa(int n)
{
    if(n==fa[n])
        return n;
    return fa[n]=find_fa(fa[n]);
}

inline void add(int u,int v,int &e)
{
    next[e]=first[u],vv[e]=v,first[u]=e++;
    next[e]=first[v],vv[e]=u,first[v]=e++;
}

struct Node
{
    short uu,vv;
    int w;
}node[4550000];

int prim(int E)
{
    int i,j,u,v,e=2,ans=0;
    for(i=1;i<=N;i++)
        fa[i]=i;
    for(i=2;i<=E;i++)
    {
        u=find_fa(node[i].uu),v=find_fa(node[i].vv);
        if(u-v)
        {
            fa[u]=v;
            ans+=node[i].w;
            bel[i]=e;
            add(node[i].uu,node[i].vv,e);
        }
    }
    return ans;
}
int cost,t,tt;

inline void merge(int n,int m)
{
    int e,t;
    for(e=first[m];e;e=t)if(vv[e]-m)
    {
        t=next[e];
        if(vv[e]-n)
            next[e]=first[n],first[n]=e;
        vv[e^1]=n;
    }
    else
        t=next[e];
}
bool dfs(int n,int f,int ee)
{
    if(n==t)
    {
        fa[n]=tt;N--;
        merge(tt,n);
        best[ee]=cost;
        best[ee^1]=best[ee];
        return 1;
    }
    for(int e=first[n];e;e=next[e])
    {
        if(vv[e]-f&&vv[e]-n)
        {
            if(dfs(vv[e],n,e)&&n-tt)
            {
                fa[n]=tt;N--;
                merge(tt,n);
                best[ee]=cost;
                best[ee^1]=best[ee];
                return 1;
            }
        }
    }
    return 0;
}
void solve(int E)
{
    int i,j,n,u,v;

    for(i=1;i<=N;i++)
        fa[i]=i;
    for(i=1;i<=N*2+4;i++)
        best[i]=INF;

    for(i=2;i<=E;i++)if(!bel[i])
    {
        u=find_fa(node[i].uu),v=find_fa(node[i].vv);
        if(u==v)
            continue;
        cost=node[i].w,t=v;tt=u;
        dfs(u,u,0);
        if(N==1)
            return;
    }
}
int cmp(const void *a,const void *b)
{
    return ((Node *)a)->w-((Node *)b)->w;
}
int main()
{
    int e=2,u,v,i,j,m,MST,q,t,tt;
    long long sum;
    double ans=0;

    while(scanf("%d%d",&N,&m),N)
    {
        memset(first,0,sizeof(first));
        memset(bel,0,(m+10)*sizeof(short));
        memset(wh,0,sizeof(wh));
        memset(best,0,sizeof(best));

        for(i=1;i<=m;i++)
            scanf("%d%d%d",&u,&v,&j),u++,v++,node[i+1].uu=u,node[i+1].vv=v,node[i+1].w=j;
        node[0].w=INF,node[1].w=0;
        qsort(node+2,m,sizeof(Node),cmp);
        for(i=1;i<=m;i++)
            u=node[i+1].uu,v=node[i+1].vv,wh[u][v]=wh[v][u]=i+1;

        MST=prim(m+1);
        solve(m+1);

        scanf("%d",&q);
        for(sum=0,i=1;i<=q;i++)
        {
            scanf("%d%d%d",&u,&v,&j);
            u++,v++;
            t=wh[u][v];

            if(!bel[t])
                sum+=MST;
            else
                tt=bel[t],sum+=j<best[tt]?j-node[t].w:best[tt]-node[t].w,sum+=MST;
        }

        printf("%.4f\n",sum/(double)q);
    }
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有