Luogu P1262 间谍网络【强连通分量/缩点】By cellur925

题目传送门

真是一道好题呀~~~~qwq

知道这题是tarjan，但是想了很久怎么用上强连通分量。因为样例们...它显然并不是一个强联通分量！

（被样例迷惑的最好例子）

然后...就没有然后了...感觉自己被欺骗了。脑补了一些别的做法，向题解低头。

$Sol$

这个时候我们其实需要一些冷静分析。分情况讨论。

判断无解性。什么时候无解？当存在一个间谍既不能被收买也没有被其他间谍掌握自己的资料，则无解。我们在主函数进行tarjan操作时，是从能被收买的间谍开始找环的。那么最后递归结束，当存在间谍没被访问($!dfn[i]$)，那么问题无解。
那么有解的情况呢？这时条件等价于所有的间谍都能直接或间接地被收买或被掌握。这时分两种情况：正如我思考时，分有环和无环两种情况。没还，资金就需要给那个没有入度的间谍；有环，我们就把资金给那个在环里资金最小的间谍（因为在一个强联通分量中，所以一个点可达另一个节点，这个环就解决了，我们肯定想要给资金需要少的。这部分处理可在tarjan中顺便求出）。有环的情况我们通常对它进行缩点，成为一个有向无环图，也就变成了无环的情况。
小结。缩点->DAG这是比较套路的东西了，大多数时候我们其实不用新建一个图，而都是在统计入度（这种场合较多）。
结论。还是我太弱了qwq。

$Code$

 #include<cstdio>

 #include<algorithm>

 #include<stack>

 #include<cstring>

 #define maxn 4000 

 using namespace std;

 int n,p,tot,r,dfs_clock,scc_cnt,ans;

 int head[maxn],val[maxn],rdu[maxn],dfn[maxn],low[maxn],scc[maxn],price[maxn];

 bool buy[maxn];

 struct node{

     int to,next;

 }edge[maxn*];

 stack<int>s;

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 void tarjan(int u)

 {

     dfn[u]=low[u]=++dfs_clock;

     s.push(u);

     for(int i=head[u];i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(!dfn[v])

         {

             tarjan(v);

             low[u]=min(low[u],low[v]);

         }

         else if(!scc[v]) low[u]=min(low[u],dfn[v]);

     }

     if(dfn[u]==low[u])

     {

         scc_cnt++;

         while()

         {

             int x=s.top();s.pop();

             scc[x]=scc_cnt;

             val[scc_cnt]=min(val[scc_cnt],price[x]);

             if(x==u) break;

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&p);

     memset(price,,sizeof(price));

     memset(val,,sizeof(val));

     for(int i=;i<=p;i++)

     {

         int x=;

         scanf("%d",&x);

         buy[x]=;

         scanf("%d",&price[x]);

     }

     scanf("%d",&r);

     for(int i=;i<=r;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         add(x,y);

     }

     for(int i=;i<=n;i++)

         if(!dfn[i]&&buy[i]) tarjan(i);

     for(int i=;i<=n;i++)

         if(!dfn[i]){ans=i;break;}

     if(ans) {printf("NO\n%d",ans);return ;}

     printf("YES\n");

     for(int x=;x<=n;x++)

         for(int i=head[x];i;i=edge[i].next)

         {

             int y=edge[i].to;

             if(scc[x]==scc[y]) continue;

             rdu[scc[y]]++;

         }

     for(int i=;i<=scc_cnt;i++)

         if(rdu[i]==) ans+=val[i];

     printf("%d",ans);

     return ;

 }

$Warning$

那个最后缩点的时候这个地方比较容易写错。最后是在$scc_cnt$上进行操作的。

    for(int x=;x<=n;x++)

        for(int i=head[x];i;i=edge[i].next)

        {

            int y=edge[i].to;

            if(scc[x]==scc[y]) continue;

            rdu[scc[y]]++;

        }

    for(int i=;i<=scc_cnt;i++)

        if(rdu[i]==) ans+=val[i];

巴特西

Luogu P1262 间谍网络【强连通分量/缩点】By cellur925

最新文章

热门文章

巴特西

Luogu P1262 间谍网络 【强连通分量/缩点】By cellur925

最新文章

热门文章

Luogu P1262 间谍网络【强连通分量/缩点】By cellur925