NOIP2016提高A组 B题【HDU3072】【JZOJ4686】通讯

题目描述

“这一切都是命运石之门的选择。”

试图研制时间机器的机关SERN截获了中二科学家伦太郎发往过去的一条短信，并由此得知了伦太郎制作出了电话微波炉（仮）。

为了掌握时间机器的技术，SERN总部必须尽快将这个消息通过地下秘密通讯网络，传达到所有分部。

SERN共有N个部门（总部编号为0），通讯网络有M条单向通讯线路，每条线路有一个固定的通讯花费Ci。

为了保密，消息的传递只能按照固定的方式进行：从一个已知消息的部门向另一个与它有线路的部门传递（可能存在多条通信线路）。我们定义总费用为所有部门传递消息的费用和。

幸运的是，如果两个部门可以直接或间接地相互传递消息（即能按照上述方法将信息由X传递到Y，同时能由Y传递到X），我们就可以忽略它们之间的花费。

由于资金问题（预算都花在粒子对撞机上了），SERN总部的工程师希望知道，达到目标的最小花费是多少。

输入格式

多组数据，文件以2个0结尾。

每组数据第一行，一个整数N，表示有N个包括总部的部门（从0开始编号）。然后是一个整数M，表示有M条单向通讯线路。

接下来M行，每行三个整数,Xi,Yi,Ci，表示第i条线路从Xi连向Yi，花费为 Ci。

输出格式

每组数据一行，一个整数表示达到目标的最小花费。

样例

样例输入

样例输出

数据范围与提示

样例解释

第一组数据：总部把消息传给分部1，分部1再传给分部2.总费用：100+50=150.

第二组数据：总部把消息传给分部1，由于分部1和分部2可以互相传递消息，所以分部1可以无费用把消息传给2.总费用：100+0=100.

第三组数据：总部把消息传给分部1，最小费用为50.总费用：50.

数据范围

对于10%的数据，保证M=N-1

对于另30%的数据，N ≤ 20 ，M ≤ 20

对于100%的数据，N ≤ 50000 ，M ≤ 10^5 ，Ci ≤ 10^5 ，

数据组数 ≤ 5
数据保证一定可以将信息传递到所有部门。

题解：

最开始看的时候以为是最短路，缩完点跑了遍spfa连样例都没有输出

然后又看了看，突然发现好像是最小生成数，打完kruskal样例一遍过，自己造的数据也都过了

后来有些不放心，就特判了10%的数据

但是我WA10，我忘了kruskal不能处理有向图

prim可以，但复杂度太高，可以线段树优化，可以过掉，但我并不会

这是我的考试代码：（巨丑）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define MAXN 50005

#define MAXM 100005

#define ll long long

#define re register

using namespace std;

int n,m;

int to[MAXM<<],nxt[MAXM<<],val[MAXM<<],pre[MAXN],tot_e=;

inline void add(re int u,re int v,re int w){

    tot_e++,val[tot_e]=w,to[tot_e]=v,nxt[tot_e]=pre[u],pre[u]=tot_e;

}

int dfn[MAXN],low[MAXN],sta[MAXN],top=,belong[MAXN],dfs_num=,tot=;

bool in_stack[MAXN];

inline void tarjan(re int x){

    dfn[x]=low[x]=++dfs_num;

    in_stack[x]=;

    sta[++top]=x;

    for(re int i=pre[x];i;i=nxt[i]){

        re int v=to[i];

        if(!dfn[v]){

            tarjan(v);

            low[x]=min(low[x],low[v]);

        }

        else if(in_stack[v]){

            low[x]=min(low[x],dfn[v]);

        }

    }

    if(dfn[x]==low[x]){

        tot++;

        re int y;

        do{

            y=sta[top--];

            in_stack[y]=;

            belong[y]=tot;

        }while(y!=x);

    }

}

struct node{

    int fr,to,nxt,len;

    friend bool operator < (node a,node b){

        return a.len<b.len;

    }

}edge[MAXM<<];

int head[MAXN];

inline void ADD(re int u,re int v,re int w){

    tot_e++,edge[tot_e].fr=u,edge[tot_e].to=v,edge[tot_e].nxt=head[u],head[u]=tot_e,edge[tot_e].len=w;

}

int fa[MAXN],ans=;

inline int find(re int x){

    return x==fa[x]?x:fa[x]=find(fa[x]);

}

inline int kruskal(){

    re int sum=,sum_edge=;

    for(re int i=;i<=tot;i++)

        fa[i]=i;

    sort(edge+,edge+tot_e+);

    for(re int i=;i<=tot_e;i++){

        //cout<<edge[i].len<<endl;

        re int x=find(edge[i].fr),y=find(edge[i].to);

        if(x!=y){

            fa[x]=y;

            sum+=edge[i].len;

            //cout<<edge[i].fr<<' '<<edge[i].to<<endl;

            sum_edge++;

        }

        if(sum_edge==tot-)

            break;

    }

    return sum;

}

//int ans=0;

signed main(){

    while(~scanf("%d%d",&n,&m)){

        int num=;

        if(n+m==) break;

        for(re int i=,x,y,c;i<=m;i++){

            scanf("%d%d%d",&x,&y,&c);

            add(x+,y+,c);num+=c;

        }

        if(m==n-){

            cout<<num<<endl;

            continue;

        }

        for(re int i=;i<=n;i++){

            if(!dfn[i]) tarjan(i);

        }

        //for(int i=1;i<=n;i++){

        //    cout<<i<<' '<<belong[i]<<endl;

        //}

        tot_e=;

        for(re int i=;i<=n;i++){

            for(re int j=pre[i];j;j=nxt[j]){

                re int y=to[j];

                if(belong[i]!=belong[y])

                    ADD(belong[i],belong[y],val[j]),ADD(belong[y],belong[i],val[j]);

                    //ans+=val[j];

            }

        }

        ans=kruskal();

        printf("%d\n",ans);

        //memset(low,0,sizeof(low));

        memset(dfn,,sizeof(dfn));

        //memset(sta,0,sizeof(sta));

        //memset(in_stack,0,sizeof(in_stack));

        //memset(belong,0,sizeof(belong));

        //memset(to,0,sizeof(to));

        //memset(nxt,0,sizeof(nxt));

        memset(pre,,sizeof(pre));

        //memset(val,0,sizeof(val));

        memset(head,,sizeof(head));

        //memset(edge,0,sizeof(edge));

        //memset(fa,0,sizeof(fa));

        tot_e=top=dfs_num=tot=ans=;

    }

    return ;

}

然额正解是贪心（全机房10分的大部分都是打的最小生成树）

说实话考试时我从没考虑过贪心

贪心的话就是缩完点，对于每一个强连通分量，最优方案是这个强连通分量所有如边中最小的一条，因为题目保证一定可以将信息传递到所有部门。

本以为是水题，结果题把我水了

AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define MAXN 50005

#define MAXM 100005

#define ll long long

#define re register

using namespace std;

int n,m,ans=;

int to[MAXM<<],nxt[MAXM<<],val[MAXM<<],pre[MAXN],tot_e=;

inline void add(re int u,re int v,re int w){

    tot_e++,val[tot_e]=w,to[tot_e]=v,nxt[tot_e]=pre[u],pre[u]=tot_e;

}

int dfn[MAXN],low[MAXN],sta[MAXN],top=,belong[MAXN],dfs_num=,tot=;

bool in_stack[MAXN];

inline void tarjan(re int x){

    dfn[x]=low[x]=++dfs_num;

    in_stack[x]=;

    sta[++top]=x;

    for(re int i=pre[x];i;i=nxt[i]){

        re int v=to[i];

        if(!dfn[v]){

            tarjan(v);

            low[x]=min(low[x],low[v]);

        }

        else if(in_stack[v]){

            low[x]=min(low[x],dfn[v]);

        }

    }

    if(dfn[x]==low[x]){

        tot++;

        re int y;

        do{

            y=sta[top--];

            in_stack[y]=;

            belong[y]=tot;

        }while(y!=x);

    }

}

struct node{

    int to,nxt,len;

}edge[MAXM<<];

int head[MAXN],out_deg[MAXN];

inline void ADD(re int u,re int v,re int w){

    tot_e++,edge[tot_e].to=v,edge[tot_e].nxt=head[u],head[u]=tot_e,edge[tot_e].len=w;

}

signed main(){

    while(~scanf("%d%d",&n,&m)){

        if(n+m==) break;

        for(re int i=,x,y,c;i<=m;i++){

            scanf("%d%d%d",&x,&y,&c);

            add(x+,y+,c);

        }

        for(re int i=;i<=n;i++){

            if(!dfn[i]) tarjan(i);

        }

        tot_e=;

        for(re int i=;i<=n;i++){

            for(re int j=pre[i];j;j=nxt[j]){

                re int y=to[j];

                if(belong[i]!=belong[y])

                    ADD(belong[y],belong[i],val[j]),out_deg[belong[y]]++;

            }

        }

        for(int i=;i<=tot;i++){

            if(!out_deg[i]) continue;

            int minn=0x7fffffff;

            bool flag=;

            for(int j=head[i];j;j=edge[j].nxt){

                minn=min(minn,edge[j].len);

                flag=;

            }

            if(flag==) ans+=minn;

        }

        printf("%d\n",ans);

        memset(dfn,,sizeof(dfn));

        memset(pre,,sizeof(pre));

        memset(head,,sizeof(head));

        tot_e=top=dfs_num=tot=ans=;

    }

    return ;

}

巴特西

NOIP2016提高A组 B题【HDU3072】【JZOJ4686】通讯

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

样例解释

数据范围

最新文章

热门文章

巴特西

NOIP2016提高A组 B题 【HDU3072】【JZOJ4686】通讯

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

样例解释

数据范围

最新文章

热门文章

NOIP2016提高A组 B题【HDU3072】【JZOJ4686】通讯