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中map转json[通俗易懂]

    java中map转json[通俗易懂]在日常的使用中,我们一般会遇到map转json,如果遍历的话会浪费大量的时间,其实我们拥有这样的jar包Themethod ***isundefinedforthetypeJSONObject缺哪个包——json-lib.jar这样还是不行的需要一个依赖的jar包要不然会报错java.lang.ClassNotFoundException:

    2022年6月20日
    55
  • Method org.postgresql.jdbc4.Jdbc4Statement.setQueryTimeout(int) is not yet implemented错误解决

    Method org.postgresql.jdbc4.Jdbc4Statement.setQueryTimeout(int) is not yet implemented错误解决17:25:17:166 [Druid-ConnectionPool-Create-1566729816] ERROR log=c.a.d.p.DruidDataSource,traceId=,userId=,msg=create connection SQLException, url: jdbc:postgresql://…:5432/…, errorCode 0, state 0A0…

    2022年6月24日
    28
  • NSGA2算法代码理解

    NSGA2算法代码理解NSGA2算法代码理解:设置200个个体,目标函数为2个,决策变量的个数为30,首先初始化得到一个每个个体位于0~1之间的决策变量,利用ZDT1函数求得目标值,保存在数组中。寻找非支配排序,在这200个个体中,选中一个个体,将这个个体和其余个体的目标函数值比较,如果没有一个个体可以支配他,那么就将其加入到非支配集合中ifindividual(i).n==0%个体i非支配等级排序最高,…

    2022年5月18日
    37
  • 词向量的作用

    词向量的作用      为了描述词与词之间的相似程度而构建的高维向量,而视频,音频数据构建本身意义,可以直接通过数据进行描述图像与声音的相似度。

    2022年5月17日
    40
  • 复录比低的计算机学校,这7所报录比低的实力院校,赶紧捡漏一波!

    复录比低的计算机学校,这7所报录比低的实力院校,赶紧捡漏一波!原标题:这7所报录比低的实力院校,赶紧捡漏一波!俗话说:考研选对专业和院校,就等于成功了一半。很多准考研er对如何选择适合自己的院校仍感到很焦虑,而报录比就是选择院校专业很重要的参与因素之一。报录比报录比是指报考人数和实际录取人数的比例,可以帮助考生了解院校报考人数、拟录取人数与实际录取人数之间的比例。如果报录比大于1,就说明报考的人数比录取的人数多;如果报录比小于1,就说明报考的人数比录取的人数…

    2022年6月9日
    55
  • 数组按照出现次数排列

    数组按照出现次数排列数组按照出现次数排列

    2022年4月24日
    46

发表回复

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

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