问题 B: 通讯

时间限制: 1 Sec 内存限制: 256 MB

题面

题目描述

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

试图研制时间机器的机关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。

输出

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

样例输入

3 3 0 1 100 1 2 50 0 2 100 3 3 0 1 100 1 2 50 2 1 100 2 2 0 1 50 0 1 100 0 0

样例输出

150

100

提示

【样例解释】

第一组数据：总部把消息传给分部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 ，数据保证一定可以将信息传递到所有部门。

考试心路历程

拿到题很激动，终于在考试里面看到了图论题。而且貌似是最拿手的有向图tarjan强连通分量缩点+最短路。

然后就这么打了。还是没认真读题，花了30分钟码出来tarjan和dijkstra，还问了老师有没有负边权。

结果样例都过不去。心态有点崩。然后柳暗花明，kruskal，跳进了最小生成树的坑里就没起来。

这是有向图欸。我是怎么“天才”地把无向图算法引入到有向图里面的？这个本应贪心100却最小生成树10分的教训我能记一辈子。。

再学图论算法一定要把有向图和无向图看清楚！

题解

膜一发tarjan大神！

因为是有向图，而且题面明显给到了“如果两个部门可以直接或间接地相互传递消息我们就可以忽略它们之间的花费”

这几乎就是强连通分量的标准定义了。tarjan强连通分量缩点板子。

不知道各位大神怎么处理的贪心，我建了个反图然后跑出来每个点入边中的最小值。

因为“数据保证一定可以将信息传递到所有部门”，所以贪心策略正确。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#include<stack>

#include<algorithm>

#define rint register int

using namespace std;

int n,m,xi,yi,ci,tot,first[],first_f[];

struct node{int u,v,w,nxt;}edge[],edge_q[],edge_f[];

int tot_q,first_q[];

stack <int> s;

int dfn[],low[],cnt,sum,sum1;

bool ins[];

int dist[],fa[];

int belong[],dp[];

bool vis[];

long long ans=;

inline void renew()

{

    tot=tot_q=cnt=sum=ans=;

    for(rint i=;i<=n;++i)

    {first[i]=first_q[i]=dfn[i]=low[i]=belong[i]=first_f[i]=;ins[i]=vis[i]=false;fa[i]=i;}

    for(rint i=;i<=m;++i)

        edge[i].u=edge[i].v=edge[i].w=edge[i].nxt=,

        edge_q[i].u=edge_q[i].v=edge_q[i].w=edge_q[i].nxt=,

        edge_f[i].u=edge_f[i].v=edge_f[i].w=edge_f[i].nxt=;

}

inline int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}

inline bool cmp(node aa,node bb){return aa.w<bb.w;}

inline void add(int uu,int vv,int ww)

{

    ++tot;

    edge[tot].u=uu;

    edge[tot].v=vv;

    edge[tot].w=ww;

    edge[tot].nxt=first[uu];

    first[uu]=tot;

}

inline void add_q(int uu,int vv,int ww)

{

    ++sum;

    edge_q[sum].u=uu;

    edge_q[sum].v=vv;

    edge_q[sum].w=ww;

    edge_q[sum].nxt=first_q[uu];

    first_q[uu]=sum;

}

inline void add_f(int uu,int vv,int ww)

{

    ++sum1;

    edge_f[sum1].u=uu;

    edge_f[sum1].v=vv;

    edge_f[sum1].w=ww;

    edge_f[sum1].nxt=first_f[uu];

    first_f[uu]=sum1;

}

inline void tarjan(int x)

{

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

    s.push(x);ins[x]=;

    for(rint i=first[x];i;i=edge[i].nxt)

    {

        int y=edge[i].v;

        if(!dfn[y])

        {

            tarjan(y);

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

        }

        else if(ins[y])

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

    }

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

    {

        tot_q++;

        while()

        {

            int l_top=s.top();

            s.pop();ins[l_top]=false;

            belong[l_top]=tot_q;

            if(l_top==x)break;

        }

    }

    return ;

}

int main()

{

    while()

    {

        scanf("%d %d",&n,&m);

        if(n==&&m==)return ;

        renew();

        for(rint i=;i<=m;++i)

        {

            scanf("%d %d %d",&xi,&yi,&ci);

            xi++,yi++;

            add(xi,yi,ci);

        }

        tarjan();

        for(rint i=;i<=n;++i)

            for(rint j=first[i];j;j=edge[j].nxt)

            {

                int y=edge[j].v;

                if(belong[i]==belong[y])continue;

                add_q(belong[i],belong[y],edge[j].w);

                add_f(belong[y],belong[i],edge[j].w);

            }

        for(rint i=;i<=tot_q;++i)

        {

            if(i==belong[])continue;

            int minn=0x7fffffff;

            for(rint j=first_f[i];j;j=edge_f[j].nxt)

            {

                minn=min(edge_f[j].w,minn);

            }

            ans+=minn;

        }

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

    }

}

巴特西

「题解」：07.16NOIP模拟T2：通讯

问题 B: 通讯

题面

考试心路历程

题解

最新文章

热门文章