HDU1827-传递的最小花费

电玩女神 2022-07-12 15:51 150阅读 0赞

# Summer Holiday #

**Time Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 3457    Accepted Submission(s): 1585**

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

**题目大意：**

题目意思如题，就是求选出最少的点使之能通过边传递所有的点，并且每个点都有个代价，且最小的花费是多少

**题目思路**：

我们知道如果是个连通图的话那么这个图的最小花费就是这个图当中的点的最小值，因此我们可以先用targan缩点，并且在缩点的过程中用个数组记录新图的每个点的最小花费，然后新图就是个有向无环图了，然后我们考虑点的入度，如果入度不为0则说明他可以有接入他的点传递而来，且保证是点最少和花费最少，应为接入点的花费小于他两的花费和，因此我们只需记录入度为0的点然后最少的点数就是入度为0的点数，最少花费就是所有入度为0的最少花费！

**AC代码：**

#include<cstring>
    #include<cstdio>
    #define min(x,y) (x<y?x:y)
    const int maxn = 1e3+10;
    const int maxm = 2e3+10;
    
    struct st{
      int v,nex;
    }edge[maxm];
    
    int hed[maxn],vis[maxn],low[maxn],dfn[maxn],belon[maxn],stack[maxn],cost[maxn],M[maxn],in[maxn];
    int n,m,e,top,cnt,num;
    
    void init(){
        memset(hed,-1,sizeof(hed));
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        memset(in,0,sizeof(in));
        memset(M,0x3f,sizeof(M));
        e=1;
        top=num=cnt=0;
    }
    
    void add(int u,int v){
        edge[e].v=v,edge[e].nex=hed[u],hed[u]=e++;
    }
    
    void targan(int u){      //targan缩点
        dfn[u]=low[u]=++num;
        stack[top++]=u;
        vis[u]=1;
        for(int i=hed[u];~i;i=edge[i].nex){
            int v = edge[i].v;
            if(!dfn[v]){
                targan(v);
                low[u]=min(low[u],low[v]);
            }else if(vis[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
        if(low[u]==dfn[u]){
            cnt++;
            int x;
            do{
                x=stack[--top];
                vis[x]=0;
                belon[x]=cnt;
                M[cnt]=min(M[cnt],cost[x]);   //记录每个新点的最小花费
            }while(x!=u);
        }
    }
    
    int main()
    {
        while(~scanf("%d%d",&n,&m)){
            init();
            for(int i=1;i<=n;i++)scanf("%d",&cost[i]);
            while(m--){
                int u,v;scanf("%d%d",&u,&v);
                add(u,v);
            }
            for(int i=1;i<=n;i++){
                if(!dfn[i])targan(i);
            }
            for(int i=1;i<=n;i++){
                for(int j = hed[i];~j;j=edge[j].nex){
                    int v = edge[j].v;
                    if(belon[i]!=belon[v]){
                        in[belon[v]]=1;
                    }
                }
            }
            int sum1=0,sum2=0;
            for(int i=1;i<=cnt;i++){
                if(in[i]==0){
                    sum1++;      //入度为0的点的个数
                    sum2+=M[i];  //所有入度为0的点的花费和
                }
            }
            printf("%d %d\n",sum1,sum2);
        }
    
        return 0;
    }