HDOJ 1827 - Summer Holiday 简单的tarjan求强联通分量+缩点

HDOJ 1827 - Summer Holiday 简单的tarjan求强联通分量+缩点

题意:

听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？(能联系到是单向的，也就是说X能联系到Y，但是不表示Y也能联系X)

题解:

易得一个强联通分量里选择任何一个人..都可以把这个强联通分量里的人通知到..并且可以把从这个强联通分量所能达的所有强联通分量覆盖到..所以so easy了..先用tarjan求出所有的强联通分量...再算出每个强联通分量里所需花费最少的人为多少..最后找出入度为0的强联通分量..其个数就是第一个答案..它们的花费之和就是第二个答案..

Program:

#include#include#include#include#include #include#include#include#define oo 1000000007#define ll long long#define pi acos(-1.0)#define MAXN 1005#define MAXM 2005using namespace std; struct node{ int u,v,next;}edge[MAXM];int Ne,_next[MAXN],A[MAXN],DfsIndex,tpnum,tp[MAXN],dfn[MAXN],low[MAXN],V[MAXN];stack S;bool inS[MAXN];void addedge(int u,int v){ edge[++Ne].next=_next[u],_next[u]=Ne,edge[Ne].u=u,edge[Ne].v=v;}void tarjan(int x){ int v,k; dfn[x]=low[x]=++DfsIndex; inS[x]=true,S.push(x); for (k=_next[x];k;k=edge[k].next) { v=edge[k].v; if (!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); }else if (inS[v]) low[x]=min(low[x],dfn[v]); } if (low[x]==dfn[x]) { tpnum++; do { x=S-(); S.pop(); tp[x]=tpnum; inS[x]=false; }while (low[x]!=dfn[x]); }}int main(){ int n,m,i,u,v,ans; while (~scanf("%d%d",&n,&m)) { Ne=0,memset(_next,0,sizeof(_next)); for (i=1;i<=n;i++) scanf("%d",&A[i]); while (m--) { scanf("%d%d",&u,&v); addedge(u,v); } memset(dfn,0,sizeof(dfn)); memset(inS,0,sizeof(inS)); while (!S.empty()) S.pop(); DfsIndex=tpnum=0; for (i=1;i<=n;i++) if (!dfn[i]) tarjan(i); memset(V,0x7f,sizeof(V)); for (i=1;i<=n;i++) V[tp[i]]=min(V[tp[i]],A[i]); for (i=1;i<=Ne;i++) if (tp[edge[i].u]!=tp[edge[i].v]) V[tp[edge[i].v]]=0; ans=m=0; for (i=1;i<=tpnum;i++) if (V[i]) m++,ans+=V[i]; printf("%d %d\n",m,ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。