Summer Holiday

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

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 16
2 2 2 2 2 2 2 2 2 2 2 2
1 3
3 2
2 1
3 4
2 4
3 5
5 4
4 6
6 4
7 4
7 12
7 8
8 7
8 9
10 9
11 10

Sample Output

3 6

题解：每个强联通分量均可以访问到此联通图的每个成员，还可以访问下一个强联通分量，所以加一个入度，另开一个数组找此强联通分量的最小值；

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<vector>

 using namespace std;

 const int INF=0x3f3f3f3f;

 //#define LOCAL

 #define mem(x,y) memset(x,y,sizeof(x))

 const int MAXN=;

 int dfs_block,css;

 int dfn[MAXN],low[MAXN],Instack[MAXN],pre[MAXN],minicost[MAXN],in[MAXN];

 vector<int>vec[MAXN];

 int cost[MAXN];

 stack<int>S;

 void initial(){

     mem(dfn,);mem(low,);mem(Instack,);mem(pre,);mem(minicost,INF);mem(in,);

     for(int i=;i<MAXN;i++)vec[i].clear();

     while(!S.empty())S.pop();

     css=dfs_block=;

 }

 void targin(int u,int fa){

     dfn[u]=low[u]=++dfs_block;

     S.push(u);

     Instack[u]=;

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

         int v=vec[u][i];

         if(!dfn[v]){

             targin(v,u);

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

         }

         else if(Instack[v])low[u]=min(low[u],dfn[v]);//v写成了u...

     }

     if(dfn[u]==low[u]){

         css++;

         while(){

             int v=S.top();

             S.pop();

             Instack[v]=;

             pre[v]=css;

             if(u==v)break;

         }

     }

 }

 int main(){

     #ifdef LOCAL

     freopen("data.in","r",stdin);

     freopen("data.out","w",stdout);

     #endif

     int N,M;

     while(~scanf("%d%d",&N,&M)){

         initial();

         for(int i=;i<=N;i++)scanf("%d",cost+i);

         int a,b;

         while(M--){

             scanf("%d%d",&a,&b);

             vec[a].push_back(b);

         }

         for(int i=;i<=N;i++){

             if(dfn[i])continue;

             targin(i,-);

         }

         for(int i=;i<=N;i++){

             minicost[pre[i]]=min(minicost[pre[i]],cost[i]);//当前强联通分量的最小值；

             for(int j=;j<vec[i].size();j++){

                 int v=vec[i][j];

                 if(pre[i]!=pre[v])in[pre[v]]++;//如果这个强联通分量可以由别的强联通分量到达，入度++；

             }

         }

         int ans1=,ans2=;

         for(int i=;i<=css;i++){

             //printf("%d\n",in[i]);

             if(in[i]==){

                 ans1++;

                 ans2+=minicost[i];

             }

         }

         printf("%d %d\n",ans1,ans2);

     }

     return ;

 }

秒客网

Summer Holiday(强联通入度最小点)

Summer Holiday