#专题练习# 强连通分量,缩点

#专题练习#  强连通分量,缩点 

1.洛谷   P1455 搭配购买

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有n朵云，云朵已经被老板编号为1，2，3，……,n,并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入格式

第1行n,m,w,表示n朵云，m个搭配和你现有的钱的数目

第2行至n+1行，每行ci,di表示i朵云的价钱和价值

第n+2至n+1+m ，每行ui,vi表示买ui就必须买vi,同理，如果买vi就必须买ui

输出格式

一行，表示可以获得的最大价值。

Q:题意是：有n个云朵，每个云朵有自己的价格ci 和价值di ，小明想用手里的钱买到尽可能的大的价值。但是老板的云朵们之间具有固定搭配方案，不能拆开购买。小明想知道他能购买到的最大价值是多少？

A:依题意可知，云朵之间存在搭配，即每种搭配是一个强连通分量。第一步，我们找出每个强连通分量，并计算出每个强连通分量的总价格和总价值；第二步，我们计算小明现有的钱可以买到的最大价值，显然这是一个简单的01背包，但是这里用二维背包会超时，需要用滚动数组优化为一维。这样就结束了。（好像并查集+01背包也能写，下次想起来补上。）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
const int maxv= 10010;
const int maxe= 10100;  //可能的最大值

struct ENode
{
    int to;
    int Next;
};
ENode edegs[maxe];
int Head[maxv], tnt;
void init()
{
    memset(Head, -1, sizeof(Head));
    tnt= -1;
}
void Add_ENode (int a, int b)
{
    ++ tnt;
    edegs[tnt].to= b;
    edegs[tnt].Next= Head[a];
    Head[a]= tnt;
    ++ tnt;
    edegs[tnt].to= a;
    edegs[tnt].Next= Head[b];
    Head[b]= tnt;
}

int m;
int dfn[maxv];  //深度优先搜索中顶点被访问的时间
int low[maxv];  //顶点v 和它的邻接点中low[]的最小值
int temp[maxv];  //判断节点是否已被访问过(0-未访问 1-已访问未删除 2-已访问已删除)
int Stack[maxv];  //手动栈
int TarBfs (int v, int lay, int &scc_num)
{
    /*v: 新加入的点; lay: 时间戳; scc_num: 记录强连通分量的数量*/

    /*第2步：初始化dfn[v]和low[v]*/
    temp[v]= 1;
    low[v]= lay;
    dfn[v]= lay;
    Stack[++ m]= v;
    for (int k= Head[v]; k!= -1; k= edegs[k].Next)
    {
        /*对于v 的所有邻接节点u：*/
        int u= edegs[k].to;
        if (temp[u]== 0)
        {
            /*第2-1步：如果没有访问过，则跳转执行第2步，同时维护low[v]*/
            TarBfs(u, ++ lay, scc_num);

        }
        if (temp[u]== 1)
        {
            /*第2-2步：如果访问过，但没有删除，维护low[v]*/
            low[v]= min(low[v], low[u]);
        }

    }
    if (dfn[v]== low[v])
    {
        /*如果low[v]== dfn[v]，则当前节点是一个强连通分量的根，
        那么输出相应的强连通分量。*/
        ++ scc_num;
        do
        {
            low[Stack[m]]= scc_num;
            temp[Stack[m]]= 2;  //已删除的节点temp更新为2
        }while (Stack[m --]!= v);
    }
    return 0;
}

int Tarjan(int n)
{
    int scc_num= 0, lay= 1;
    m= 0;
    memset(temp, 0, sizeof(temp));
    memset(low, 0, sizeof(low));
    for (int i= 1; i<= n; i ++)
    {
        if (temp[i]== 0)
        {
            /*第1步：找一个没有被访问过的节点v，否则算法结束*/
            TarBfs(i, lay, scc_num);
        }
    }
    /*返回强连通分量的个数*/
    return scc_num;
}

int ci[maxv];
int di[maxv];
int rock_ci[maxv]; //每个连通块的费用和
int rock_di[maxv]; //每个连通块的价值和
int dp[10010];
int main()
{
    int n, m, cost;
    int a, b;
    scanf("%d %d %d", &n, &m, &cost);
    for (int i= 1; i<= n; i ++)
    {
        scanf("%d %d", &a, &b);
        ci[i]= a;
        di[i]= b;
    }
    init();
    for (int i= 0; i< m; i ++)
    {
        scanf("%d %d", &a, &b);
        Add_ENode(a, b);
    }

    int ans= Tarjan(n);
    memset(rock_ci, 0, sizeof(rock_ci));
    memset(rock_di, 0, sizeof(rock_di));
    for (int i= 1; i<= n; i ++)
    {
        int tmp= low[i];
        rock_ci[tmp]+= ci[i];
        rock_di[tmp]+= di[i];
    }
    int sum= 0;
//    for (int i= 1; i<= ans; i ++)
//    {
//        printf("--> %d %d
", rock_ci[i], rock_di[i]);
//    }
//    cout << cost << endl;
    for (int i= 1; i<= ans; i ++)
    {
        for (int j= cost; j>= 0; j --)
        {
            if (j- rock_ci[i]>= 0) dp[j]= max(dp[j], dp[j- rock_ci[i]]+ rock_di[i]);
            else dp[j]= dp[j];
//            printf("-%d- -%d- -%d-
", dp[i][j], dp[i- 1][j], rock_di[i]);
        }
    }
    printf("%d
", dp[cost]);
    return 0;
}

 2. 洛谷  P2835 刻录光盘

题目描述

在JSOI2005夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？！

组委会把这个难题交给了LHC，LHC分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！

可是，LHC调查后发现，由于种种原因，有些营员并不是那么的合作，他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们JSOI宣扬的团队合作精神格格不入！！！

现在假设总共有N个营员（2<=N<=200），每个营员的编号为1~N。LHC给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料。

现在，请你编写一个程序，根据回收上来的调查表，帮助LHC计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

输入格式

先是一个数N，接下来的N行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号，以一个0结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有1个0，一行中的若干数之间用一个空格隔开。

输出格式

一个正整数，表示最少要刻录的光盘数。

Q: 老板手里的动漫碟(雾)不够人手一份了，所以老板希望关系好的小朋友们可以相互拷一下。但不是所有人的关系都很铁，一个人只愿意帮助他的朋友；更坑爹的是，有些（天杀的）小贱货会嫌麻烦而选择不帮助自己的朋友。所以人与人之间的帮助并不是相互的。老板现在很发愁，他想发出最少的CD来让每个人都能看到动漫，你能够帮帮他么？

A: 很显然，因为有小贱货的存在，所以我们的传递是单向的，就不能简单愉快的无脑交强连通/ 并查集模板了。那么我们就要动脑筋想一想了。其实我们能够发现，在单向传递的情况下，总有那么几个不被别人帮助却转身去帮助他人的小天使了，那我们现在要做的就是找出这些小天使并把CD交给他们了。而找他们的过程，没错我们要做的就是寻找最小点基。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
const int maxv= 210;
const int maxe= 40040;  //可能的最大值

struct ENode
{
    int to;
    int Next;
};
ENode edegs[maxe];
int Head[maxv], tnt;
void init()
{
    memset(Head, -1, sizeof(Head));
    tnt= -1;
}
void Add_ENode (int a, int b)
{
    ++ tnt;
    edegs[tnt].to= b;
    edegs[tnt].Next= Head[a];
    Head[a]= tnt;
}

int m;
int dfn[maxv];  //深度优先搜索中顶点被访问的时间
int low[maxv];  //顶点v 和它的邻接点中low[]的最小值
int temp[maxv];  //判断节点是否已被访问过(0-未访问 1-已访问未删除 2-已访问已删除)
int Stack[maxv];  //手动栈
int TarBfs (int v, int lay, int &scc_num)
{
    /*v: 新加入的点; lay: 时间戳; scc_num: 记录强连通分量的数量*/

    /*第2步：初始化dfn[v]和low[v]*/
    temp[v]= 1;
    low[v]= lay;
    dfn[v]= lay;
    Stack[++ m]= v;
    for (int k= Head[v]; k!= -1; k= edegs[k].Next)
    {
        /*对于v 的所有邻接节点u：*/
        int u= edegs[k].to;
        if (temp[u]== 0)
        {
            /*第2-1步：如果没有访问过，则跳转执行第2步，同时维护low[v]*/
            TarBfs(u, ++ lay, scc_num);
        }
        if (temp[u]== 1)
        {
            /*第2-2步：如果访问过，但没有删除，维护low[v]*/
            low[v]= min(low[v], low[u]);
        }
    }
    if (dfn[v]== low[v])
    {
        /*如果low[v]== dfn[v]，则当前节点是一个强连通分量的根，
        那么输出相应的强连通分量。*/
        ++ scc_num;
        do
        {
            low[Stack[m]]= scc_num;
            temp[Stack[m]]= 2;  //已删除的节点temp更新为2
        }while (Stack[m --]!= v);
    }
    return 0;
}

int Tarjan(int n)
{
    int scc_num= 0, lay= 1;
    m= 0;
    memset(temp, 0, sizeof(temp));
    memset(low, 0, sizeof(low));
    for (int i= 1; i<= n; i ++)
    {
        if (temp[i]== 0)
        {
            /*第1步：找一个没有被访问过的节点v，否则算法结束*/
            TarBfs(i, lay, scc_num);
        }
    }
    /*返回强连通分量的个数*/
    return scc_num;
}

int in_degree[maxv];
int main()
{
    int n;
    int u, v;
    scanf("%d", &n);
    init();
    for (int i= 1; i<= n; i ++)
    {
        u= i;
        while (~ scanf("%d", &v))
        {
            if (! v) break;
            Add_ENode(u, v);
        }
    }
    int ans= Tarjan(n);

    /*缩点，求最小点基数量*/
    memset(in_degree, 0, sizeof(in_degree));
    for (int u= 1; u<= n; u ++)
    {
        for (int k= Head[u]; k!= -1; k= edegs[k].Next)
        {
            int v= edegs[k].to;
            if (low[u]!= low[v])
            {
                /*如果u 和v 之间有边但他们却不连通，则说明是单向关系*/
                /*u所在的强连通分量是 v所在的强连通分量的 “父亲” */
                /*子连通块的入度 +1*/
                in_degree[low[v]] ++;
            }
        }
    }
    int cnt= 0;
    for (int i= 1; i<= ans; i ++)
    {
        /*入度为0 的连通块，就是最小点基的其中一个点*/
        /*至少需要发的cd 的数量就是最小点基集合的大小*/
        if (in_degree[i]== 0) cnt ++;
    }
    printf("%d
", cnt);
    return 0;
}

end；