HDU 1827 Summer Holiday——————(Kosaraju求强连通分量,缩点)

Bertha 。 2022-02-01 14:29 221阅读 0赞

# [Summer Holiday][] #

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

**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

--------------------

就是先用Kosaraju算法缩点，缩点之后再对每一个强连通分量求出消耗的最小值  
最后找入度为0的强连通分量，把它们的消耗值加起来

#include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<stack>
    #include<queue>
    #include<vector>
    #include<deque>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e5+7;
    int V;
    int cost[MAXN], used[MAXN], cmp[MAXN],ind[MAXN], Cost[MAXN];
    vector<int>  G[MAXN];
    vector<int> rG[MAXN];
    vector<int> vs;
    
    void add_edge(int from, int to)
    {
        
            G[from].push_back(to);
            rG[to].push_back(from);
    }
    
    void dfs(int v)
    {
        
            used[v] = true;
            for(int i=0;i<(int)G[v].size();++i)
                    if(!used[G[v][i]])      dfs(G[v][i]);
            vs.push_back(v);
    }
    
    void rdfs(int v, int k)
    {
        
            used[v] = true;
            cmp[v]  = k;
            for(int i=0;i<(int)rG[v].size();++i)
                    if(!used[rG[v][i]])     rdfs(rG[v][i], k);
    }
    
    int scc()
    {
        
            memset(used, 0, sizeof(used));
            vs.clear();
            for(int i=0;i<V;++i)
                    if(!used[i])    dfs(i);
    
            int k=0;
            memset(used, 0, sizeof(used));
            for(int i=vs.size()-1;i>=0;--i)
                    if(!used[vs[i]])        rdfs(vs[i], k++);
            return k;
    }
    
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
            int n,m;
            while(cin>>n>>m)
            {
        
                    V = n;
                    int x,y;
                    for(int i=0;i<V;++i)
                    {
        
                            cin>>cost[i];
                            G[i].clear();
                            rG[i].clear();
                    }
                    for(int i=0;i<m;++i)
                    {
        
                            cin>>x>>y;
                            add_edge(x-1,y-1);
                    }
                    memset(Cost, 0x3f, sizeof(Cost));
                    int N = scc();
                    for(int i=0;i<V;++i)
                            Cost[cmp[i]] = min(Cost[cmp[i]], cost[i]);
                    // for(int i=0;i<V;++i)
                    //         cout<<i+1<<" "<<cmp[i]+1<<endl;
                    // cout<<"---------"<<endl;
                    memset(ind, 0, sizeof(ind));
                    for(int v=0;v<V;++v)
                    {
        
                            for(int i=0;i<(int)G[v].size();++i)
                            {
        
                                    if(cmp[v]==cmp[G[v][i]])       continue;
                                            ind[cmp[G[v][i]]]++;
                            }
                    }
                    int sum = 0, num = 0;
                    for(int i=0;i<N;++i)
                    {
        
                            // cout<<i+1<<" "<<ind[i]<<endl;
                            if(ind[i]==0)
                            {
        
                                    // cout<<i+1<<endl;
                                    num++;
                                    sum += Cost[i];
                            }
                    }
                    cout<<num<<" "<<sum<<endl;
            }
            return 0;
    }

[Summer Holiday]: http://acm.hdu.edu.cn/showproblem.php?pid=1827