CodeForces160D 最小生成树 + dfs

https://cn.vjudge.net/problem/26727/origin

题目大意:

给一个带权的无向图,保证没有自环和重边. 由于最小生成树不唯一,因此你需要确定每一条边是以下三种情况哪一个 1.一定在所有MST上 2.可能在某个MST上 3.一定不可能在任何MST上输入

第一行给出n,m表示点数和边数. 数据范围见原题面之后m行,每行给出ai,bi,wi 表示一个边的两个端点和边的权值.保证没有自环与重边. 输出

一看到这题就觉得似曾相似，仔细一看是某场比赛里卡了我三个小时的类似题，当时由于题解写的和我写的算法不一样，没有去补题。这次遇到这题偶然发现由于这题的数据开大了，之前那题的暴力算法走不通了，正好用到了我之前写了很久没找出bug的算法。

第一步显然是将所有边按权值从小到大排序，将每层权值相同的边分开来做。

第二步显然是将每层所有两点已经联通的点打上none的标记

问题在于分开必通过和可以不通过的边，上次只想到了dfs，也想到将所有已联合的点形成联通快找联通快之间必连的点，这次看了题解，发现这种联通块之间必须链接的点被称为桥，必须连接的点成为割点，寻找桥和割点都是通过tarjan算法实现的，也就是基于dfs打一个时间戳实现。

所以我们只要每一层进行见图找出所有的桥即可解决问题。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 1e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,tmp,K,tot,index;

int tree[maxn];

int type[maxn];

int vis[maxn];

int head[maxn];

struct Query{

    int u,v,w,id;

}q[maxn];

struct Edge{

    int v,next,id;

}edge[maxn * ];

bool cmp(Query a,Query b){

    return a.w < b.w;

}

int find(int p){

    if(p == tree[p]) return p;

    return tree[p] = find(tree[p]);

}

void Union(int a,int b){

    a = find(a); b = find(b);

    tree[a] = b;

}

void add(int u,int v,int id){

    edge[tot].v = v;

    edge[tot].next = head[u];

    edge[tot].id  = id;

    head[u] = tot++;

}

int dfs(int u,int last){

    int lowu = vis[u] = ++index;

    for(int i = head[u]; ~i;i = edge[i].next){

        int v = edge[i].v;

        if(!vis[v]){

            int lowv = dfs(v,i);

            lowu = min(lowu,lowv);

            if(lowv > vis[u]) type[edge[i].id] = ;

        }else if(vis[v] < vis[u] && i != (last ^ )){

            lowu = min(lowu,vis[v]);

        }

    }

    return lowu;

}

int main()

{

    scanf("%d%d",&N,&M);

    For(i,,M) scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w),q[i].id = i;

    sort(q + ,q +  + M,cmp);

    For(i,,N) tree[i] = i;

    For(i,,M){

        int j = i;

        while(j <= M && q[j].w == q[i].w)j++; j--;

        For(k,i,j){

            q[k].u = find(q[k].u);q[k].v = find(q[k].v);

            int u = q[k].u; int v = q[k].v;

            if(u == v){

                type[q[k].id] = ;

                continue;

            }

            type[q[k].id] = ;

            vis[u] = vis[v] = ;

            head[u] = head[v] = -;

        }

        index = tot = ;

        For(k,i,j){

            if(q[k].u != q[k].v){

                add(q[k].u,q[k].v,q[k].id);

                add(q[k].v,q[k].u,q[k].id);

            }

        }

        For(k,i,j) if(!vis[q[k].u]) dfs(q[k].u,-);

        For(k,i,j) Union(q[k].u,q[k].v);

        i = j;

    }

    For(i,,M){

        if(!type[i]) puts("none");

        else if(type[i] == )puts("any");

        else puts("at least one");

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

巴特西

CodeForces160D 最小生成树 + dfs

最新文章

热门文章