The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

ZOJ 3378 Attack the NEET Princess 求无向图任意两点之间的割边

   所谓0->n-1路径上一定要经过的割边,就是0->n-1任意一条路径上的割边,因为割边是必经之路。其实这题跟ZOJ 2588是同一个题,稍微变化就可以得到答案了,不过这题我当时的模板貌似写挫了,对边进行判重的时候进行了暴力,其实可以用set存一下,那么查找的复杂度可以降到log(n).
 具体求割边的方法可以看这个:http://www.cppblog.com/abilitytao/archive/2009/09/26/97267.html
不过程序貌似有问题,代码写得比较挫,就不值得借鉴了。
#include<iostream>
#include
<algorithm>
#include
<set>
#include
<cstdio>
#include
<memory.h>
using namespace std;
#define min(a,b) ((a<b?a:b))

set<int>mm;//存储重边

int const maxn=10010;//顶点数
int const maxm=100010;//边数
int n,m;

struct Edge
{
    
int u,v,idx;
    
bool operator<(Edge o)const
    
{
        
if(u!=o.u)
            
return u<o.u;
        
else
            
return v<o.v;
    }

}
e[maxm*2];

struct node
{
    
int t;
    
int idx;
    node 
*next;
}
edge[maxm*2];

node 
*adj[maxn];
int len=0;


void addedge(int u,int v,int idx)//加入一条边
{
    edge[len].idx
=idx;edge[len].next=adj[u];edge[len].t=v;adj[u]=&edge[len++];
}




void input()
{
    
int i;
    
for(i=0;i<m;i++)
    
{
        scanf(
"%d%d",&e[i].u,&e[i].v);
        e[i].idx
=i;
        
if(e[i].u>e[i].v)
            swap(e[i].u,e[i].v);
    }

    sort(e,e
+m);
    
int flag=0;
    
for(i=0;i<m-1;i++)
    
{

        
if(e[i].u!=e[i+1].u||e[i].v!=e[i+1].v)
        
{

            addedge(e[i].u,e[i].v,e[i].idx);
            addedge(e[i].v,e[i].u,e[i].idx);

            
if(flag==1)
            
{
                mm.insert(e[i].idx);
                flag
=0;
            }



        }

        
else 
        
{
            flag
=1;
            mm.insert(e[i].idx);
        }


    }

    addedge(e[m
-1].u,e[m-1].v,e[m-1].idx);
    addedge(e[m
-1].v,e[m-1].u,e[m-1].idx);
    
if(flag==1)
        mm.insert(e[m
-1].idx);


}


int v[maxn];
int dfsn[maxn];//时间戳
int low[maxn];//记录它和它的子孙结点能够到达的最小时间戳
int re[maxm*2];
int nAns;//记录结果数目
int T=0;

void init(int n)
{
    mm.clear();
    nAns
=0;
    
int i;
    
for(i=0;i<=n;i++)
        adj[i]
=NULL;
    len
=0;
}


void dfs(int fa,int x)//传入树的父亲结点
{
    v[x]
=1;dfsn[x]=T;low[x]=T;T++;
    node 
*p;
    
for(p=adj[x];p!=NULL;p=p->next)
    
{
        
if(p->t==fa)
            
continue;
        
int u=p->t;
        
if(!v[u])
        
{
            dfs(x,u);
            low[x]
=min(low[x],low[u]);//注意是low值相比较,画个图很好理解
        }

        
else if(u!=x)
            low[x]
=min(dfsn[u],low[x]);
    }


}




int findAns=0;
void DfsFindPath(int fa,int x)
{
    v[x]
=1;
    
if(x==n-1)
    
{
        findAns
=1;
        
return;
    }

    node 
*p;
    
for(p=adj[x];p!=NULL;p=p->next)
    
{
        
if(!v[p->t])
        
{
            DfsFindPath(x,p
->t);
            
if(findAns==1)
            
{
                
if(low[p->t]>dfsn[x])
                
{
                    
if(mm.find(p->idx)==mm.end())
                        re[nAns
++]=p->idx;
                }

                
return;
            }


        }

    }

}



void FindBridge(int s)
{
    T
=0;
    nAns
=0;
    memset(v,
0,sizeof(v));
    findAns
=0;
    dfs(
-1,s);//注意第一个结点的父亲用-1表示
    memset(v,0,sizeof(v));
    DfsFindPath(
-1,s);

}





int main()
{
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        init(n);
        input();
        FindBridge(
0);
        sort(re,re
+nAns);
        printf(
"%d\n",nAns);
        
int i;
        
for(i=0;i<nAns;i++)
        
{
            
if(i>0)
                printf(
" ");
            printf(
"%d",re[i]);
        }

        printf(
"\n");
    }


    
return 0;
}

posted on 2010-08-24 23:41 abilitytao 阅读(1465) 评论(1)  编辑 收藏 引用

评论

# re: ZOJ 3378 Attack the NEET Princess 求无向图任意两点之间的割边 2010-08-29 17:54 Tanky Woo

朋友你好:
C/C++和算法论坛:C++奋斗乐园
欢迎你加入。
里面有C/C++交流,求助,源码,
算法学习,求助,
ACM刷题
等各种板块,
相信大家在一起能学习快乐。

论坛地址:
[url=http://www.cppleyuan.com/index.php">http://www.cppleyuan.com/index.php]http://www.cppleyuan.com/index.php">http://www.cppleyuan.com/index.php[/url]

另外,论坛现在招收版主,有意愿的朋友可以看看:
[url=http://www.cppleyuan.com/forumdisplay.php?fid=44">http://www.cppleyuan.com/forumdisplay.php?fid=44]http://www.cppleyuan.com/forumdisplay.php?fid=44">http://www.cppleyuan.com/forumdisplay.php?fid=44[/url]

注:此留言绝不是广告,只是看见博主也是C/C++和算法的爱好者,我们想邀请博主一起加入我们的 论坛。

我也是一名C/C++和ACM爱好者,大家可以去我博客看看就知道了:
[url=http://www.wutianqi.com/">http://www.wutianqi.com/]http://www.wutianqi.com/">http://www.wutianqi.com/[/url]

打扰之处请见谅。
  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理