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)


相关推荐

  • 知乎转载_知乎上的文章可以转载吗

    知乎转载_知乎上的文章可以转载吗链接:https://www.zhihu.com/question/22590902/answer/55182189来源:知乎著作权归作者所有,转载请联系作者获得授权。题主的问题是如何白手起家靠一个人赚到100万,我觉得这个是可以做到的,但是要分阶段,不太可能从一个从无经商经验的人突然转变成一个人折腾点东西就能赚百万(多个人一起有可能)。我先把我个人的阶段拆解开来,给你一个直观的感受。…

  • 医疗器械进销存软件管理系统_简单仓库管理系统

    医疗器械进销存软件管理系统_简单仓库管理系统开发环境:Eclipse/MyEclipse、Tomcat8、Jdk1.8数据库:MySQL适用于:课程设计,毕业设计,学习等等系统介绍有偿

  • eclipse安装教程与使用教程「建议收藏」

    eclipse安装教程与使用教程「建议收藏」第一首先在电脑的浏览器中输入“eclipse官网”。 然后在网页中点击进入eclipse的官方下载网站。 2 第二然后再点击页面右边的“download”。 在弹出的页面下面点击“downloadpackages”。 3 第三然后在下面找到“eclipseIDEforjavadevelopers”的选项。 在选项右边有一个“3…

  • vue 双向绑定原理及依赖搜集的过程「建议收藏」

    vue 双向绑定原理及依赖搜集的过程「建议收藏」双向数据绑定机制:官方:vue是采用数据劫持结合发布者-订阅者模式的方式,通过Object.defineProperty()来劫持各个属性的setter,getter,在数据变动时发布消息给订阅者,触发响应的监听回调。第一步:需要observer的数据对象进行递归遍历,包括子属性对象的属性,都加上setter和getter,这样的话,给这个对象的某个值赋值,就会触发setter,那么就能监听到了数据变化第二步:compile解析模板令,将模板中的变量替换成数据.然后初始化渲染页面视图,并将每个令对

    2022年10月17日
  • 微信开放平台—-微信扫码登录

    微信开放平台—-微信扫码登录告知:所有操作是基于域名已备案,并且具有企业级微信公众号!1.准备工作   1.1.注册微信开放平台帐号       https://open.weixin.qq.com   1.2.创建应用(网站应用),填写资料https://open.weixin.qq.com/cgi-bin/appcreate?t=manage/createWeb&amp;type=…

  • Qt中的角度转弧度[通俗易懂]

    Qt中的角度转弧度[通俗易懂]在Qt中,qAsin(),qAtan2()等三角函数的返回值是弧度而不是角度,因此要将弧度转化为角度。弧度=角度*Pi/180以qAtan()函数为例qrealqAtan(qrealv)Returnsthearctangentofvasanangleinradians.Arctangentistheinverseoperationoftangent….

发表回复

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

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