Hdu 4738 Caocao's Bridges (有重边无向图求桥)

╰+攻爆jí腚メ 2022-10-06 12:50 6阅读 0赞

2013杭州网络赛的第一题，坑点相当多，貌似这题导致15分钟没有队伍过题……

比赛时我负责这道题，WA9次才A。。。。。

从边数小于等于点数平方这点来看肯定有重边，需要处理。

图不连通，输出0.

如果取到的最小值是0的话，要输出1，表示要派一个人过去。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=1005;
    const int M=N*N*2;
    
    struct Edge
    {
    	int v,next,val;
    	bool sign;
    }edge[M];
    
    int head[N],e;
    int dfn[N],low[N];
    int brg[M],cnt;   //存储桥的权值及数量
    int top,dp;   //dp存储搜索深度
    int n,m;
    
    void Add (int u,int v,int val)
    {
    	edge[e].v = v ;
    	edge[e].val = val ;
    	edge[e].next = head[u] ;
    	edge[e].sign = false ;
    	head[u] = e ++ ;
    }
    
    void Init ()
    {
    	memset(head,-1,sizeof(head));
    	e=cnt=0;
    	memset(dfn,0,sizeof(dfn));
    	memset(low,0,sizeof(low));
    	memset(brg,0,sizeof(brg));
    	top=dp=0;
    }
    
    void tarjan (int now ,int fa)
    {
    	dfn[now] = low[now] = ++dp;
    	bool first =false ;
    	for (int i = head[now] ; ~i ; i = edge[i].next)
    	{
    		int e = edge[i].v;
    		if (edge[i].sign) continue;
    		//无向图加双向边时必定相邻
    		//处理后避免深搜的时候搜回去,经过重边再搜回来
    		edge[i].sign = edge[i ^ 1].sign = true;  
    		if (!dfn[e])
    		{
    			tarjan(e,now);
    			low[now] = min(low[now] ,low[e]);
    			if (dfn[now] < low[e])   //是桥
    				brg[cnt++] = edge[i].val ;
    		}
    		else low[now] = min(low[now] , dfn[e]);
    	}
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    
        while (scanf("%d%d",&n,&m),n||m)
        {
    		Init();
    		int i,a,b,c;
    		for (i=1;i<=m;i++)
    		{
    			scanf("%d%d%d",&a,&b,&c);
    			Add(a,b,c);
    			Add(b,a,c);
    		}
    		int colornum=0;
            for (i=1;i<=n;i++)
            {
                top=dp=0;
                if (dfn[i]==0)
                    tarjan (i,-1),colornum++;
            }
            if (colornum>1)//不连通
    			printf("0\n");
    		else if (cnt==0)  //没有桥
    			printf("-1\n");
    		else
    		{
    			sort(brg,brg+cnt);
    			if (brg[0]==0)   //存在桥权值为0
    				printf("1\n");
    			else
    				printf("%d\n",brg[0]);
    		}
        }
        return 0;
    }

2014-7-31更新一种写法

#pragma comment(linker, "/STACK:1024000000,1024000000")
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int INF=0x3f3f3f3f;
    
    const int nPoint=1005;
    const int nEdges=1005*1005*2;
    int brg[nEdges];
    
    class BCC
    {
    public:
    	struct Edge{
    		int from, to,val, next;
    		bool cut;  //是否为桥
    	}edge[nEdges];
    
    	int e,id,n;
    	int head[nPoint],dfn[nPoint], low[nPoint];
    	int bridgetop;
    	int colornum, top; //双连通分量数,栈顶
    	int color[nPoint],Stack[nPoint];
    	bool iscut[nPoint];  //该点是否为割点
    	int bri_cut;    //桥的数目
    
    	void Add (int u, int v,int val){
    		Edge E={u,v,val,head[u],false};
    		edge[ e ] = E;
    		head[u] = e++;
    	}
    
    	void Tarjan (int u, int pre)
    	{
    		dfn[u]=low[u]=++id;
    		Stack[++top]=u;
    		int child=0, flag=1;
    		
    		for (int i=head[u]; ~i; i=edge[i].next)
    		{
    			int v=edge[i].to;
    			//if (v == pre) continue; //重边算一条的写法
    			if (flag && v==pre)
    			{//重边有效的写法
    				flag = 0; 
    				continue;
    			}
    			if (!dfn[v])
    			{
    				child++;
    				Tarjan(v,u);
    				low[u] = min(low[u], low[v]);
    				if (low[v] >= dfn[u])
    				{
    					iscut[u] = true;  //是割点
    					if (low[v]>dfn[u])
    						edge[i].cut = edge[i^1].cut = true;  //是桥
    				}
    			}
    			else low[u] = min(low[u], dfn[v]);
    		}
    		if (child == 1 && pre<0) //树根
    			iscut[u] = false;
    		if (low[u] == dfn[u])
    		{
    			colornum++;
    			do
    			{
    				color[ Stack[top] ] = colornum;
    			}while(Stack[top--] != u);
    		}
    	}
    
    	void Init (int _n)
    	{
    		n=_n;
    		memset(head, -1, sizeof(head));
    		memset(dfn, 0, sizeof(dfn));
    		memset(iscut, 0, sizeof(iscut));
    		memset(color, -1, sizeof(color));
    		bridgetop =e=id= 0;
    		top = colornum = 0;
    	}
    
    	bool Deal ()
    	{
    		int i,flag=0;
    		for (i=1; i<=n; i++) if (!dfn[i])
    		{
    			Tarjan(i, -1);
    			flag++;
    		}
    		bri_cut = 0;
    		for (i=0; i<e; i+=2)
    			if (edge[i].cut)
    			{
    				brg[bri_cut]=edge[i].val;
    				bri_cut++;
    			}	
    		if (flag==1) return true;
    		return false;
    	}
    }ob;
    
    int n,m;
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    
        while (scanf("%d%d",&n,&m),n||m)
        {
    		ob.Init(n);
    		int i,a,b,c;
    		for (i=1;i<=m;i++)
    		{
    			scanf("%d%d%d",&a,&b,&c);
    			ob.Add(a,b,c);
    			ob.Add(b,a,c);
    		}
    		bool flag=ob.Deal();
    		int cnt=ob.bri_cut;
    		if (flag==false)//不连通
    			printf("0\n");
    		else if (cnt==0)  //没有桥
    			printf("-1\n");
    		else
    		{
    			sort(brg,brg+cnt);
    			if (brg[0]==0)   //存在桥权值为0
    				printf("1\n");
    			else
    				printf("%d\n",brg[0]);
    		}
        }
        return 0;
    }