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<limits.h>

typedef long long LL;

using namespace std;

const int INF=0x3f3f3f;

#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )

#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )

#define CLEAR( a , x ) memset ( a , x , sizeof a )

const int maxn=1100;

const int maxm=10000;

struct node{

    int u,v;

    int next;

}e[maxm];

int head[maxn],cntE;

int DFN[maxn],low[maxn];

int s[maxm],top,index,cnt;

int belong[maxn],instack[maxn];

int in[maxn],val[maxn];

int tt[maxn];//tt保存缩成的点中的最小值

int n,m;

void init()

{

    top=cntE=0;

    index=cnt=0;

    CLEAR(DFN,0);

    CLEAR(head,-1);

    CLEAR(instack,0);

}

void addedge(int u,int v)

{

    e[cntE].u=u;e[cntE].v=v;

    e[cntE].next=head[u];

    head[u]=cntE++;

}

void Tarjan(int u)

{

    DFN[u]=low[u]=++index;

    instack[u]=1;

    s[top++]=u;

    for(int i=head[u];i!=-1;i=e[i].next)

    {

        int v=e[i].v;

        if(!DFN[v])

        {

            Tarjan(v);

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

        }

        else if(instack[v])

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

    }

    int v;

    if(DFN[u]==low[u])

    {

        cnt++;

        do{

            v=s[--top];

            belong[v]=cnt;

            instack[v]=0;

        }while(u!=v);

    }

}

void work()

{

    REPF(i,1,n)

      if(!DFN[i])  Tarjan(i);

    CLEAR(in,0);

    CLEAR(tt,INF);

    REPF(i,1,n)

    {

        if(tt[belong[i]]>val[i])

            tt[belong[i]]=val[i];

    }

    REPF(k,1,n)

    {

        for(int i=head[k];i!=-1;i=e[i].next)

        {

            int v=e[i].v;

            if(belong[k]!=belong[v])

               in[belong[v]]++;

        }

    }

    int ans=0;

    int num=0;

    REPF(i,1,cnt)

    {

        if(!in[i])

        {

            num++;

            ans+=tt[i];

        }

    }

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

}

int main()

{

    int u,v;

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

    {

        init();

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

            scanf("%d",&val[i]);

        for(int i=0;i<m;i++)

        {

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

            addedge(u,v);

        }

        work();

    }

    return 0;

}