首页 > 代码库 > HDU 1827 Summer Holiday
HDU 1827 Summer Holiday
http://acm.hdu.edu.cn/showproblem.php?pid=1827
题意：
听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？
思路：
强连通分量，然后统计入度为0的连通分支数量，这就是至少需要通知的人数，然后最小花费是每个连通分支中权值最小的点相加。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack>10 using namespace std;11 12 const int INF=0x3f3f3f;13 const int maxn=1000+5;14 int n,m;15 16 vector<int> G[maxn];17 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;18 int scc_v[maxn];19 stack<int> S;20 int a[maxn];21 int in[maxn];22 23 void dfs(int u) {24 pre[u] = lowlink[u] = ++dfs_clock;25 S.push(u);26 for (int i = 0; i < G[u].size(); i++)27 {28 int v = G[u][i];29 if (!pre[v])30 {31 dfs(v);32 lowlink[u] = min(lowlink[u], lowlink[v]);33 }34 else if(!sccno[v])35 lowlink[u] = min(lowlink[u], pre[v]);36 }37 if (pre[u] == lowlink[u])38 {39 scc_cnt++;40 scc_v[scc_cnt] = INF;41 for(;;)42 {43 int x = S.top(); S.pop();44 //计算出每个连通分支中的最小权值45 scc_v[scc_cnt] = min(scc_v[scc_cnt], a[x]);46 sccno[x] = scc_cnt;47 if (x == u) break;48 }49 }50 }51 52 void find_scc(int n)53 {54 dfs_clock = scc_cnt = 0;55 memset(pre, 0, sizeof(pre));56 memset(sccno, 0, sizeof(sccno));57 for (int i = 1; i <= n; i++)58 if (!pre[i]) dfs(i);59 }60 61 62 int main()63 {64 //freopen("D:\\input.txt","r",stdin);65 while(scanf("%d%d",&n,&m)==2)66 {67 for(int i=1;i<=n;i++) G[i].clear();68 for(int i=1;i<=n;i++) scanf("%d",&a[i]);69 while(m--)70 {71 int u,v;72 scanf("%d%d",&u,&v);73 G[u].push_back(v);74 }75 find_scc(n);76 memset(in,0,sizeof(in));77 for(int u=1;u<=n;u++)78 {79 for(int i=0;i<G[u].size();i++)80 {81 int v=G[u][i];82 if(sccno[u]!=sccno[v]) in[sccno[v]]=1;83 }84 }85 int ans=0,num=0;86 for(int i=1;i<=scc_cnt;i++)87 {88 if(in[i]==0)89 {90 ans+=scc_v[i];91 num++;92 }93 }94 printf("%d %d\n",num,ans);95 }96 return 0;97 }
HDU 1827 Summer Holiday
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。