<題目鏈接>

題目大意：

聽說lcy幫大家預定了新馬泰7日游，Wiskey真是高興的夜不能寐啊，他想著得快點把這消息告訴大家，雖然他手上有所有人的聯(lián)系方式，但是一個一個聯(lián)系過去實在太耗時間和電話費了。他知道其他人也有一些別人的聯(lián)系方式，這樣他可以通知其他人，再讓其他人幫忙通知一下別人。你能幫Wiskey計算出至少要通知多少人，至少得花多少電話費就能讓所有人都被通知到嗎？?

解題分析：

強連通縮點，再將所有入度為0的強連通分量中最小的價值相加即可。

#include <bits/stdc++.h> using namespace std;#define pb push_back #define rep(i,s,t) for(int i=s;i<=t;i++) #define clr(a,b) memset(a,b,sizeof(a)) const int N = 1e3+10,M = 2e3+10; int n,m,tot,cnt,scc,top; int val[N],instk[N],stk[N],dfn[N],low[N],ind[N],outd[N],belong[N],head[N]; struct Edge{int to,next; }edge[M]; vector<int>G[N]; void init(){rep(i,0,n)G[i].clear();tot=cnt=scc=top=0;clr(instk,0);clr(stk,0);clr(dfn,0);clr(low,0);clr(ind,0);clr(outd,0);clr(belong,0),clr(head,-1); } void addedge(int u,int v){edge[++cnt].to=v,edge[cnt].next=head[u];head[u]=cnt; } void Tarjan(int u){dfn[u]=low[u]=++tot;stk[++top]=u;instk[u]=1;for(int i=head[u];~i;i=edge[i].next){int v=edge[i].to;if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}else if(instk[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){scc++;while(true){int v=stk[top--];instk[v]=0;belong[v]=scc;G[scc].pb(v);if(v==u)break;}} } int main(){while(scanf("%d%d",&n,&m)!=EOF){init();rep(i,1,n)scanf("%d",&val[i]);rep(i,1,m){int u,v;scanf("%d%d",&u,&v);addedge(u,v);}rep(i,1,n)if(!dfn[i])Tarjan(i);rep(u,1,n) for(int i=head[u];~i;i=edge[i].next){int v=edge[i].to;if(belong[u]!=belong[v])ind[belong[v]]++,outd[belong[u]]++;}int ans=0,res=0;rep(i,1,scc) if(!ind[i]){int mn=1e9;rep(j,0,G[i].size()-1){ //遍歷該連通塊中的所有元素，尋找價值最小的int v=G[i][j];mn=min(mn,val[v]);}res++;ans+=mn;}printf("%d %d\n",res,ans);} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/00isok/p/10765315.html

總結(jié)

以上是生活随笔為你收集整理的HDU - 1827 Summer Holiday (强连通)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。