hdu 4635 Strongly connected (tarjan)

hdu 4635 Strongly connected (tarjan)

大家好,又见面了,我是全栈君。

题意:给一个n个顶点m条弧的简单有向图(无环无重边),求最多能够加入多少条弧使得加入后的有向图仍为简单有向图且不是一个强连通图。假设给的简单有向图本来就是强连通图,那么输出-1.


分析:

1.用tarjan算法求出强连通分量的个数,假设个数为1,那么输出-1,结束,否则运行2

2.如果将一些强连通分量合并为有n1个顶点简单全然图1,而将剩下的强连通分量合并为n2个顶点的简单全然图2,跨这两个简单全然图的弧的方向仅仅能是单向的,如果m1为全然图1内部的弧的数量,m2为为全然图2内部的弧的数量。m3为跨这两个简单全然图的弧的数量,那么

 ans=n1*(n1-1)-m1+n2*(n2-1)-m2+n1*n2-m3  —————————————————-1式

 n1+n2=n                                                            —————————————————-2式

 m1+m2+m3=m                                                 —————————————————-3式

 n*n=(n1+n2)(n1+n2)=n1*n1+n2*n2+2*n1*n2 —————————————————–4式

所以

ans=n*n-m-n-n1*n2=n*n-m-n-n1*(n-n1)

ans要最大,所以n1*(n-n1)要最小。同一时候要跨图1。图2的弧要单向,

所以在跨图1,图2的弧要单向的情况下。n1尽量小。


代码:
#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX 100005#define INF 1<<30using namespace std;typedef struct ArcNode{    int adjvex;//该弧所指向的顶点的位置    struct ArcNode * nextarc;//指向下一条弧的指针} ArcNode;typedef struct VNode{    int vertex;    //int In_deg,Out_deg;    int belong;    ArcNode * firstarc;} VNode;VNode V[MAX];int DFN[MAX],Stack[MAX],low[MAX];int top,index,bcnt;bool instack[MAX];long long n,m;int Min;int cnt;int k;int edge[MAX][2];void init(){    int a,b;    ArcNode * p;    for(int i=1; i<=n; i++)    {        V[i].vertex=i;        //V[i].In_deg=V[i].Out_deg=0;        V[i].firstarc =NULL;    }    for(int i=0; i<m; i++)    {        scanf("%d%d",&a,&b);       // V[a].Out_deg++;       // V[b].In_deg++;       edge[i][0]=a;       edge[i][1]=b;        p=(ArcNode*)malloc(sizeof(ArcNode));        p->adjvex =b;        p->nextarc =V[a].firstarc ;        V[a].firstarc =p;    }}void DFS_tarjan(int i){    int j;    ArcNode * p;    DFN[i]=low[i]=++index;    Stack[++top]=i;    instack[i]=true;    p=V[i].firstarc ;    while(p!=NULL)    {        j=p->adjvex;        if(!DFN[j])        {            DFS_tarjan(j);            if(low[j]<low[i])//Low(u)为u的子树可以追溯到的最早的栈中节点的次序号                low[i]=low[j];        }        else if(instack[j]&&DFN[j]<low[i])//Low(u)为u可以追溯到的最早的栈中节点的次序号            low[i]=DFN[j];        p=p->nextarc;//    }    if(DFN[i]==low[i])    {        bcnt++;        cnt=0;        int INDEG=0;        int OUTDEG=0;        do        {            j=Stack[top--];//出栈,j是为该强连通分量中一个顶点            instack[j]=false;            //INDEG+=V[j].In_deg;            //OUTDEG+=V[j].Out_deg;            V[j].belong=bcnt;            cnt++;        }        while(i!=j);        for(int kkk=0;kkk<m;kkk++)        {            if(V[edge[kkk][0]].belong==bcnt&&V[edge[kkk][1]].belong!=bcnt)            {                OUTDEG++;            }            if(V[edge[kkk][0]].belong!=bcnt&&V[edge[kkk][1]].belong==bcnt)                INDEG++;        }        if(Min>cnt&&(INDEG==0||OUTDEG==0))        {            Min=cnt;        }    }}void FREE(){    ArcNode * p;    ArcNode * q;    for(int i=1; i<=n; i++)    {        p=V[i].firstarc;        while(p!=NULL)        {            q=p;            p=p->nextarc;            free(q);        }    }}void solve(){    int i;    top=index=bcnt=0;    memset(DFN,0,sizeof(DFN));    memset(instack,false,sizeof(instack));    for(i=1; i<=n; i++)    {        if(!DFN[i])            DFS_tarjan(i);    }    //printf("%d\n",bcnt);    FREE();    if(bcnt==1)    {        printf("Case %d: -1\n",k);        return;    }    long long ans=n*n-n-m-(Min*(n-Min));    //printf("%d\n",Min);    printf("Case %d: %lld\n",k,ans);}int main(){    int t;    scanf("%d",&t);    for(k=1; k<=t; k++)    {        scanf("%lld%lld",&n,&m);        Min=INF;        init();        solve();    }    return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115821.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 解决Pycharm运行速度慢的方法「建议收藏」

    解决Pycharm运行速度慢的方法「建议收藏」用惯了Jupyter,Spyder的开发者切换到Pycharm时,发现不论是打开IDE的速度,还是调试的速度都慢的让人想砸电脑,笔者在这花了好长时间生闷气,最终总结了几个坑来解决运行速度慢的问题,希望能帮到大家。1.扩大Pycharm运行内存打开后找到-Xms-Xmx两行,增加运行内存(根据电脑配置,笔者是8G内存),可明显改善打开IDE的速度2.新建工程选择Python解释器笔者常用Anaconda,因此选用了它3.解决运行时查看变量速度慢的方法File->Setting-&gt

  • Scala学习笔记(一)

    Scala学习笔记(一)

  • 计算机考研数据库题库及答案_数据结构历年考研真题

    计算机考研数据库题库及答案_数据结构历年考研真题在数据库的三级模式结构中,描述数据库中全体数据的全局逻辑结构和特征的是()。A.充分必要条件B.必要条件C.充分条件D.既不充分也不必要条件。A.需求分析阶段B.概念设计阶段C.逻辑设计阶段D.物理设计阶段。在关系模式R(U,F)中,Y∈XF+是X→Y是否成立的()。A.数据库系统B.文件系统C.人工管理D.数据项管理。A.网络系统B.数据库系统C.操作系统D.数据库。A.外模式B.内模式C.存储模式D.模式。…

    2022年10月26日
  • 10分钟梳理MySQL核心知识点

    10分钟梳理MySQL核心知识点

  • anycast隧道_IPv6中Anycast通信模型若干问题的分析和研究.pdf

    anycast隧道_IPv6中Anycast通信模型若干问题的分析和研究.pdf您所在位置:网站首页>海量文档&nbsp>&nbsp计算机&nbsp>&nbsp通信/网络IPv6中Anycast通信模型若干问题的分析和研究.pdf109页本文档一共被下载:次,您可全文免费在线阅读后下载本文档。下载提示1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受…

  • H5文件读取_如何用电脑读取手机文件

    H5文件读取_如何用电脑读取手机文件H5文件读取:importtorch.utils.dataasdataimporttorchimporth5pyclassDatasetFromHdf5(data.Dataset):def__init__(self,file_path):super(DatasetFromHdf5,self).__init__()hf=h5py.File(file_path)self.data=hf.get(‘data’)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号