HDU-1827-Summer Holiday（强连通分量，贪心）-白红宇

HDU-1827-Summer Holiday（强连通分量，贪心）

阅读量：7210 次

发布时间：2019-06-29

本文共 2126 字，大约阅读时间需要 7 分钟。

链接：

题意：

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

思路：

tarjan算法，缩点。

先tarjan缩点，得到入度为0的强连通分量，再在每个入度为0的强连通分量中寻找一个消耗最小的人。

找最小的人可以在搜索的出栈的时候得到。

卡cin

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long LL;const int MAXN = 1e3+10;const int INF = 0x3f3f3f3f;vector
                    
                      G[MAXN];stack
                     
                       St;int Dfn[MAXN], Low[MAXN];int Vis[MAXN], Dis[MAXN];int Fa[MAXN], Cost[MAXN];int Val[MAXN];int n, m;int times, cnt;void Init(){ for (int i = 1;i <= n;i++) G[i].clear(), Fa[i] = i; memset(Dfn, 0, sizeof(Dfn)); memset(Low, 0, sizeof(Low)); memset(Vis, 0, sizeof(Vis)); memset(Dis, 0, sizeof(Dis)); times = cnt = 0;}void Tarjan(int x){ Dfn[x] = Low[x] = ++times; Vis[x] = 1; St.push(x); for (int i = 0;i < G[x].size();i++) { int node = G[x][i]; if (Dfn[node] == 0) { Tarjan(node); Low[x] = min(Low[x], Low[node]); } else if (Vis[node] == 1) Low[x] = min(Low[x], Dfn[node]); } if (Low[x] == Dfn[x]) { cnt++; Val[cnt] = Cost[St.top()]; while (St.top() != x) { Val[cnt] = min(Val[cnt], Cost[St.top()]); Fa[St.top()] = cnt; Vis[St.top()] = 0; St.pop(); } Val[cnt] = min(Val[cnt], Cost[St.top()]); Fa[St.top()] = cnt; Vis[St.top()] = 0; St.pop(); }}int main(){ int t; while (~scanf("%d%d", &n, &m)) {// cin >> n >> m; Init(); for (int i = 1;i <= n;i++) scanf("%d", &Cost[i]);// cin >> Cost[i]; int l, r; for (int i = 1;i <= m;i++) { scanf("%d%d", &l, &r);// cin >> l >> r; G[l].push_back(r); } for (int i = 1;i <= n;++i) if (!Dfn[i]) Tarjan(i); for (int i = 1;i <= n;++i) { for (int j = 0;j < G[i].size();j++) { int node = G[i][j]; if (Fa[i] != Fa[node]) ++Dis[Fa[node]]; } } int res_num = 0, res_val = 0; for (int i = 1;i <= cnt;i++) if (!Dis[i]) res_num++, res_val += Val[i]; cout << res_num << ' ' << res_val << endl; } return 0;}

转载于:https://www.cnblogs.com/YDDDD/p/10821724.html

你可能感兴趣的文章