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;}

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

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

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • java向上取整和向下取整,万字长文!

    java向上取整和向下取整,万字长文!一面:70分钟突击电话面试正思考着项目功能模块,阿里面试官打来了电话,开始了阿里一面。阿里面试官自我介绍,介绍了5分钟左右,部门的情况,主要的业务提问开始会哪些操作系统Linux会一点说一下操作指令,怎么看cpu,看进程,看端口操作系统进程间通信追问了一个信号相关的问题,我不知道了。io多路复用,说一说面向切面编程,说一说那些场景说说面向切面编程给一个场景,有很多方法,找出耗时长的方法spring的@autowired的作用mybatis和hibernate的区别C,C

    2022年6月21日
    26
  • Qt5.7 + VS2015 环境搭建「建议收藏」

    Qt5.7 + VS2015 环境搭建「建议收藏」简述之前介绍过Qt5.x的环境搭建,5.7开始支持VS2015,为了使用新的开发环境(典型的强迫症),不得不再次进行Qt5.7+VS2015的环境搭建。除了之前介绍的搭建细节之外,其实中间有很多需要注意的部分。下面,主要分享搭建过程以及其中需要注意的一些事项。简述安装VS2015安装Qt57配置QtCreator配置编译器配置调试器HelloWorldVS20

    2022年5月16日
    59
  • WPF教程(二十五)WrapPanel[通俗易懂]

    WPF教程(二十五)WrapPanel[通俗易懂]WrapPanel用于一个接一个的排列子控件,以水平或者垂直方向,当空间不足时就会自动切换到下一行。适合于需要水平或者垂直排列控件且能自动换行的情况。水平方向排列时,每一行所有子控件的高度都被统一成固定的值,这个值由最高的那个决定;每一列垂直方向排列时,所有子控件的宽度都被统一成固定的值,这个值由最宽的那个决定。我们先来看默认情况下的WrapPanel:

    2022年7月22日
    9
  • C#窗口句柄

    C#窗口句柄在Windows中,句柄是一个系统内部数据结构的引用。例如当你操作一个窗口,或说是一个Delphi窗体时,系统会给你一个该窗口的句柄,系统会通知你:你正在操作142号窗口,就此你的应用程序就能要求系统对142号窗口进行操作——移动窗口、改变窗口大小、把窗口极小化为图标等。实际上许多WindowsAPI函数把句柄作为它的第一个参数,如GDI(图形设备接口)句柄、菜单句柄、实例句柄、位图句柄等,不仅仅局限于窗口函数。换句话说,句柄是一种内部代码,通过它能引用受系统控制的特殊元素,如窗口、位图、图标、内存块、

    2022年7月14日
    14
  • 组合数据类型练习,英文词频统计实例

    组合数据类型练习,英文词频统计实例1、列表实例:由字符串创建一个作业评分列表,做增删改查询统计遍历操作。例如,查询第一个3分的下标,统计1分的同学有多少个,3分的同学有多少个等。2、字典实例:建立学生学号成绩字典,做增删改查遍历操作

    2022年7月6日
    17
  • 【通俗易懂】机器学习中 L1 和 L2 正则化的直观解释[通俗易懂]

    【通俗易懂】机器学习中 L1 和 L2 正则化的直观解释[通俗易懂]L=Ein+λ∑j|wj|L=Ein+λ∑j|wj|L=E_{in}+\lambda\sum_j|w_j|∑jw2j≤C∑jwj2≤C\sum_jw_j^2\leqC∇Ein∇Ein\nablaE_in∇Ein+λw=0∇Ein+λw=0\nablaE_{in}+\lambdaw=0∂∂w(12λw2)=λw∂∂w(12λw2)=λw\frac{\partia…

    2022年7月13日
    14

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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