hdu1827之强联通

# 移动开发 2024-05-05 04:16 0 26 来源：云博客

Summer Holiday

Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1430 Accepted Submission(s): 645

Problem Description

To see a World in a Grain of Sand

And a Heaven in a Wild Flower,

Hold Infinity in the palm of your hand

And Eternity in an hour.

—— William Blake

听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊。他想着得快点把这消息告诉大家，尽管他手上有全部人的联系方式，可是一个一个联系过去实在太耗时间和电话费了。他知道其它人也有一些别人的联系方式，这样他能够通知其它人。再让其它人帮忙通知一下别人。

你能帮Wiskey计算出至少要通知多少人。至少得花多少电话费就能让全部人都被通知到吗？

Input

多组測试数组，以EOF结束。

第一行两个整数N和M（1<=N<=1000, 1<=M<=2000）。表示人数和联系对数。

接下一行有N个整数，表示Wiskey联系第i个人的电话费用。

接着有M行，每行有两个整数X，Y，表示X能联系到Y，可是不表示Y也能联系X。

Output

输出最小联系人数和最小花费。

每一个CASE输出答案一行。

Sample Input

  12 162 2 2 2 2 2 2 2 2 2 2 2 1 33 22 13 42 43 55 44 66 47 47 127 88 78 910 911 10

Sample Output

3 6

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <queue>#include <algorithm>#include <map>#include <cmath>#include <iomanip>#define INF 99999999typedef long long LL;using namespace std;const int MAX=1000+10;int n,m,size,top,index;int head[MAX],val[MAX],dfn[MAX],low[MAX];int mark[MAX],stack[MAX];struct Edge{ int v,next; Edge(){} Edge(int V,int NEXT):v(V),next(NEXT){}}edge[MAX*2];void Init(int num){ for(int i=0;i<=num;++i)head[i]=-1,mark[i]=0; size=top=index=0;}void InsertEdge(int u,int v){ edge[size]=Edge(v,head[u]); head[u]=size++;}void tarjan(int u){ if(mark[u])return; dfn[u]=low[u]=++index; stack[++top]=u; mark[u]=1; for(int i=head[u];i != -1;i=edge[i].next){ int v=edge[i].v; tarjan(v); if(mark[v] == 1)low[u]=min(low[u],low[v]); } if(dfn[u] == low[u]){ while(stack[top] != u){ mark[stack[top]]=-1; val[u]=min(val[u],val[stack[top]]); low[stack[top--]]=low[u]; } mark[u]=-1; --top; }}int main(){ int u,v; while(~scanf("%d%d",&n,&m)){ Init(n); for(int i=1;i<=n;++i)scanf("%d",val+i); for(int i=0;i<m;++i){ scanf("%d%d",&u,&v); InsertEdge(u,v); } for(int i=1;i<=n;++i){ if(mark[i])continue; tarjan(i); } for(int i=0;i<=n;++i)mark[i]=0; for(int i=1;i<=n;++i){ for(int j=head[i];j != -1;j=edge[j].next){ v=edge[j].v; if(low[i] == low[v])continue; mark[low[v]]=1; } } int sum=0,ans=0; for(int i=1;i<=n;++i){ if(!mark[low[i]] && dfn[i] == low[i])++ans,sum+=val[i]; mark[low[i]]=1; } printf("%d %d\n",ans,sum); } return 0;}