HZOI20190725 B 回家 tarjan

题目大意：https://www.cnblogs.com/Juve/articles/11226266.html

题解：

感觉挺水的，但考场上没打出来

题目翻译一下就是输出起点到终点必经的点

其实就是求起点到终点的割点

这题算法非常多，我介绍我的方法：

55%：

可能这个算法是不严谨的，但至少能那55分

我们先tarjan求点双，然后缩点

然后我们从1号点所在点双开始dfs，

维护一个栈，每到一个点双，就把点双中的割点压入栈里，继续搜索

回溯时在弹栈，当我们搜到n号点所在点双，就停止搜索

这样栈中剩余的点就是我们要求的点

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<vector>

#include<stack>

#define MAXM 4000005

#define MAXN 2000005

#define ll long long

#define re register

using namespace std;

inline ll read(){

    re ll x=0;char ch=getchar();

    while(ch<'0'||ch>'9'){ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x;

}

ll t,n,m;

ll to[MAXM<<2],nxt[MAXM<<2],pre[MAXN],cnt=0;

inline void add(re ll u,re ll v){

    cnt++,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;

}

ll ver[MAXM<<2],nxtt[MAXM<<2],head[MAXN],sum=0;

inline void ADD(re ll u,re ll v){

    sum++,ver[sum]=v,nxtt[sum]=head[u],head[u]=sum;

}

ll dfn[MAXN],low[MAXN],dfs_order=0,sta[MAXN],top=0,dcc_num=0,belong[MAXN];

bool is_cut[MAXN];

vector<ll>dcc[MAXN];

inline void tarjan(re ll x){

    dfn[x]=low[x]=++dfs_order;

    sta[++top]=x;

    ll num=0;

    for(re ll i=pre[x];i;i=nxt[i]){

        re ll y=to[i];

        if(!dfn[y]){

            tarjan(y);

            low[x]=min(low[x],low[y]);

            if(low[y]>=dfn[x]){

                num++,dcc_num++;

                if(x!=1||num>1) is_cut[x]=1;

                re ll z;

                do{

                    z=sta[top--];

                    dcc[dcc_num].push_back(z);

                }while(y!=z);

                dcc[dcc_num].push_back(x);

            }

        }

        else low[x]=min(low[x],dfn[y]);

    }

}

stack<ll>a;

ll tot=0,num=0,new_id[MAXN];

bool flag=0,ans[MAXN];

void dfs(ll x,ll fa){

    if(x==belong[n]){

        flag=1;

        return ;

    }

    for(ll i=head[x];i;i=nxtt[i]){

        if(ver[i]==fa) continue;

        ll y=ver[i],N=dcc[y].size();

        for(ll j=0;j<N;j++){

            if(is_cut[dcc[y][j]]){

                //cout<<dcc[y][j]<<endl;

                a.push(dcc[y][j]);

            }

        }

        dfs(y,x);

        if(flag) return ;

    }

    //cout<<a.top()<<endl;

    if(!a.empty()) a.pop();

}

signed main(){

    t=read();

    while(t--){

        n=read(),m=read();

        for(re ll i=1,u,v;i<=m;i++){

            u=read(),v=read();

            if(u==v) continue;

            add(u,v),add(v,u);

        }

        tarjan(1);

        num=dcc_num;

        for(re ll i=1;i<=n;i++)

            if(is_cut[i]) new_id[i]=++num;

        for(re ll i=1;i<=dcc_num;i++){

            re ll N=dcc[i].size();

            for(re ll j=0;j<N;j++){

                re ll t=dcc[i][j];

                if(is_cut[t]){

                    ADD(i,new_id[t]);

                    ADD(new_id[t],i);

                    belong[t]=new_id[t];

                }else belong[t]=i;

            }

        }

        //for(ll i=1;i<=n;i++)

        //  cout<<i<<' '<<belong[i]<<endl;

        //cout<<"------------------------"<<endl;

        //for(ll i=1;i<=num;i++){

        //  for(ll j=head[i];j;j=nxtt[j]){

        //      cout<<i<<' '<<ver[j]<<endl;

        //  }

        //}

        dfs(belong[1],0);

        while(!a.empty()){

            re ll tp=a.top();

            a.pop();

            if(!ans[tp]){

                if(tp!=1&&tp!=n){

                    ans[tp]=1;

                    tot++;

                }

            }

        }

        printf("%lld\n",tot);

        for(ll i=2;i<n;i++)

            if(ans[i])

                printf("%lld ",i);

        puts("");

        memset(pre,0,sizeof(pre));

        cnt=dfs_order=tot=dcc_num=sum=num=0;

        memset(dfn,0,sizeof(dfn));

        memset(is_cut,0,sizeof(is_cut));

        memset(dcc,0,sizeof(dcc));

        memset(head,0,sizeof(head));

        memset(ans,0,sizeof(ans));

        flag=0;

    }

    return 0;

}

/*

15 19

1 2

1 3

1 12

12 13

13 14

12 14

2 4

3 4

4 6

4 5

6 5

5 7

5 8

7 8

7 9

8 9

9 15

15 11

15 10

4 3

1 2

2 3

3 4

5 5

1 2

2 3

3 4

4 5

4 1

5 5

1 2

2 3

3 4

4 5

5 1

*/

这有什么问题吗？为什么一直55分？有大佬能解释的话可以留言

另一种算法：

这个算法一直90分，但找不到问题（是某大佬提出的）

我们用dijkstra或spfa跑1到n的最短路，顺便记录路径

那么必经点一定在这条路上

那么我们就可以求桥，桥两边的点都是要求的点

100%：

其实只要在tarjan就割点的板子上加一句话就A了：

在判割点时，在判断条件后加上dfn[to[i]]<=dfn[n]就可以了

 if(low[y]>=dfn[x]&&dfn[y]<=dfn[n]){

     num++;

     if(x!=||num>) is_cut[x]=,tot++;

 }

想一下tarjan的实现原理，dfn[n]是终点的dfn值

我们发现如果一个节点y的dfn值大于n，那么n肯定优先于y被搜到，

而我们是从1开始dfs，所以y肯定不在1到n的必经路上

那么这道题就非常水了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#define MAXM 400005

#define MAXN 200005

#define ll long long

#define re register

using namespace std;

inline ll read(){

	re ll x=0;char ch=getchar();

	while(ch<'0'||ch>'9'){ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return x;

}

ll t,n,m;

ll to[MAXM<<1],nxt[MAXM<<1],pre[MAXN],cnt=0;

inline void add(re ll u,re ll v){

	cnt++,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;

}

ll dfn[MAXN],low[MAXN],dfs_order=0,tot=0;

bool is_cut[MAXN];

inline void tarjan(re ll x){

	dfn[x]=low[x]=++dfs_order;

	re ll num=0;

	for(re ll i=pre[x];i;i=nxt[i]){

		re ll y=to[i];

		if(!dfn[y]){

			tarjan(y);

			low[x]=min(low[x],low[y]);

			if(low[y]>=dfn[x]&&dfn[y]<=dfn[n]){

				num++;

				if(x!=1||num>1) is_cut[x]=1,tot++;

			}

		}

		else low[x]=min(low[x],dfn[y]);

	}

}

signed main(){

	t=read();

	while(t--){

		n=read(),m=read();

		for(re ll i=1,u,v;i<=m;i++){

			u=read(),v=read();

			if(u==v) continue;

			add(u,v),add(v,u);

		}

		tarjan(1);

		printf("%lld\n",tot);

		for(re ll i=1;i<=n;i++){

			if(is_cut[i])

				printf("%lld ",i);

		}

		puts("");

		cnt=dfs_order=tot=0;

		memset(pre,0,sizeof(pre));

		memset(dfn,0,sizeof(dfn));

		memset(is_cut,0,sizeof(is_cut));

	}

	return 0;

}

再来一道loj上类似的题：ZJOI 2004「一本通 3.6 练习 2」嗅探器https://loj.ac/problem/10101

你会发现这道题非常水，只不过起点终点不是1和n了

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#define MAXM 2005

#define MAXN 1005

#define ll long long

#define re register

using namespace std;

ll a, b, n, u, v, ans = 0x7fffffff;

ll to[MAXM << 1], nxt[MAXM << 1], pre[MAXN], cnt = 0;

inline void add(re ll u, re ll v) { cnt++, to[cnt] = v, nxt[cnt] = pre[u], pre[u] = cnt; }

ll dfn[MAXN], low[MAXN], dfs_order = 0, tot = 0;

bool is_cut[MAXN];

inline void tarjan(re ll x) {

    dfn[x] = low[x] = ++dfs_order;

    re ll num = 0;

    for (re ll i = pre[x]; i; i = nxt[i]) {

        re ll y = to[i];

        if (!dfn[y]) {

            tarjan(y);

            low[x] = min(low[x], low[y]);

            if (low[y] >= dfn[x] && dfn[y] <= dfn[b]) {

                num++;

                if (x != a || num > 1)

                    tot++, ans = min(ans, x);

            }

        } else

            low[x] = min(low[x], dfn[y]);

    }

}

signed main() {

    scanf("%lld", &n);

    while (~scanf("%lld%lld", &u, &v)) {

        if (u + v == 0)

            break;

        add(u, v), add(v, u);

    }

    scanf("%lld%lld", &a, &b);

    tarjan(a);

    if (tot)

        printf("%lld\n", ans);

    else

        puts("No solution");

    return 0;

}

巴特西

HZOI20190725 B 回家 tarjan

最新文章

热门文章