[图论]强联通分量+缩点 Summer Holiday

╰+攻爆jí腚メ 2021-11-23 09:46 232阅读 0赞

# Summer Holiday #

## Description ##

听说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输出答案一行。

### Examples ###

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

### Output ###

3 6

### 正确解法： ###

若它是一个无向图，则可以用并查集来解决，可是这是一个有向图。

就用强联通分量来写，先判断他们的强联通分量。然后看每个点的下点是否和自己属于同一块，若不属于同一块，标记一下入度=1，也就是说我们只要考虑入度为0的强联通分量即可，至于入度为1的强联通分量，会有入度为0的点传到那边，就不用考虑了。

我们再来看入度为0的强联通分量中代价最小的那一个，我们就让他来传话。

最小联系人数就是入度为0的强联通分量的个数，最小花费就是 个数\*各自代价最小

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
      2 #include <cstdio>
      3 #include <cstring>
      4 #include <cmath>
      5 #include <algorithm>
      6 #include <queue>
      7 #include <vector>
      8 #include <set>
      9 #include <map>
     10 #include <stack>
     11 typedef long long ll;
     12 const int N=1000+100;
     13 const int mod=1e9+7;
     14 const int inf=0x7fffffff;
     15 using namespace std;
     16 int n,m,Bcnt=0,a[N];
     17 int Link[N],len=0,id=0;
     18 int tin[N],low[N],bok[N],indu[N],mincost[N];
     19 int belong[N];
     20 stack<int>s;
     21 struct node
     22 {
     23     int y,next;
     24 }e[2010];
     25 void add(int xx,int yy)
     26 {
     27     e[++len].next=Link[xx];
     28     Link[xx]=len;
     29     e[len].y=yy;
     30 }
     31 void tarjan(int u)
     32 {
     33     tin[u]=low[u]=++id;
     34     s.push(u);
     35     bok[u]=1;
     36     for(int i=Link[u];i;i=e[i].next)
     37     {
     38         int v=e[i].y;
     39         if(!tin[v])
     40         {
     41             tarjan(v);
     42             low[u]=min(low[u],low[v]);
     43         }
     44         else if(bok[v])
     45         {
     46             low[u]=min(low[u],tin[v]);
     47         }
     48     }
     49     if(tin[u]==low[u])
     50     {
     51         Bcnt++;
     52         while(true)
     53         {
     54             int v=s.top();
     55             s.pop();
     56             bok[v]=0;
     57             belong[v]=Bcnt;
     58             if(u==v)    break;
     59         }
     60     }
     61 }
     62 int main()
     63 {
     64     while(scanf("%d %d",&n,&m)!=EOF)
     65     {
     66         if(n==0)    break;
     67         memset(bok,0,sizeof(bok));
     68         memset(Link,0,sizeof(Link));
     69         memset(e,0,sizeof(e));
     70         memset(tin,0,sizeof(tin));
     71         memset(low,0,sizeof(low));
     72         memset(belong,0,sizeof(belong));
     73         memset(a,0,sizeof(a));
     74         memset(indu,0,sizeof(indu));
     75         Bcnt=0; id=0;   len=0;
     76         int xx,yy;
     77         for(int i=1;i<=n;i++)
     78             scanf("%d",&a[i]);
     79         while(m--)
     80         {
     81             scanf("%d %d",&xx,&yy);
     82             add(xx,yy);
     83         }
     84         for(int i=1;i<=n;i++)
     85             if(!tin[i])
     86                 tarjan(i);
     87         for(int i=1;i<=n;i++)
     88             for(int j=Link[i];j;j=e[j].next)
     89         {
     90             int kkk=e[j].y;
     91             if(belong[i]!=belong[kkk])
     92                 indu[belong[kkk]]=1;
     93         }
     94         for(int i=1;i<=Bcnt;i++)
     95             mincost[i]=999999999;
     96         for(int i=1;i<=n;i++)
     97             if(mincost[belong[i]]>a[i]&&indu[belong[i]]==0)
     98                 mincost[belong[i]]=a[i];
     99         int ans=0,sum=0;
    100         for(int i=1;i<=Bcnt;i++)
    101         {
    102             if(indu[i]!=0)  continue;
    103             ans++;
    104             sum+=mincost[i];
    105         }
    106         printf("%d %d\n",ans,sum);
    107         //printf("hello\n");
    108     }
    109 
    110     return 0;
    111 }

转载于:https://www.cnblogs.com/Kaike/p/11144019.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/4255825d505b4c479c1f023d14eec1d7.png