HDU 1827 Summer Holiday

http://acm.hdu.edu.cn/showproblem.php?pid=1827

题意：

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

思路：

强连通分量，然后统计入度为0的连通分支数量，这就是至少需要通知的人数，然后最小花费是每个连通分支中权值最小的点相加。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<stack>

 using namespace std;

 const int INF=0x3f3f3f;

 const int maxn=+;

 int n,m;

 vector<int> G[maxn];

 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

 int scc_v[maxn];

 stack<int> S;

 int a[maxn];

 int in[maxn];

 void dfs(int u) {

     pre[u] = lowlink[u] = ++dfs_clock;

     S.push(u);

     for (int i = ; i < G[u].size(); i++)

     {

         int v = G[u][i];

         if (!pre[v])

         {

             dfs(v);

             lowlink[u] = min(lowlink[u], lowlink[v]);

         }

         else if(!sccno[v])

         lowlink[u] = min(lowlink[u], pre[v]);

     }

     if (pre[u] == lowlink[u])

     {

         scc_cnt++;

         scc_v[scc_cnt] = INF;

         for(;;)

         {

             int x = S.top(); S.pop();

             //计算出每个连通分支中的最小权值

             scc_v[scc_cnt] = min(scc_v[scc_cnt], a[x]);

             sccno[x] = scc_cnt;

             if (x == u) break;

         }

     }

 }

 void find_scc(int n)

 {

     dfs_clock = scc_cnt = ;

     memset(pre, , sizeof(pre));

     memset(sccno, , sizeof(sccno));

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

         if (!pre[i]) dfs(i);

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     while(scanf("%d%d",&n,&m)==)

     {

         for(int i=;i<=n;i++)   G[i].clear();

         for(int i=;i<=n;i++)   scanf("%d",&a[i]);

         while(m--)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[u].push_back(v);

         }

         find_scc(n);

         memset(in,,sizeof(in));

         for(int u=;u<=n;u++)

         {

             for(int i=;i<G[u].size();i++)

             {

                 int v=G[u][i];

                 if(sccno[u]!=sccno[v])  in[sccno[v]]=;

             }

         }

         int ans=,num=;

         for(int i=;i<=scc_cnt;i++)

         {

             if(in[i]==)

             {

                 ans+=scc_v[i];

                 num++;

             }

         }

         printf("%d %d\n",num,ans);

     }

     return ;

 }