「银联初赛第一场」自学图论的码队弟弟（dfs找环+巧解n个二元一次方程）

题意：n条边n个节点的连通图，边权为两个节点的权值之和，没有「自环」或「重边」，给出的图中有且只有一个包括奇数个结点的环。
思路：n条边n个节点保证了是在一颗树的基础上加了一条边，有且只有一个奇数节点的环保证了，沿着一个节点走下去会碰到已经访问过的节点。对于方程的解，对1号节点赋予相对值0，遍历所有节点，使所有节点拥有一个相对于1号节点的相对值，具体分析见代码

#include <bits/stdc++.h>

using namespace std;

#define fre freopen("data.in","r",stdin);

#define frew freopen("my.out","w",stdout);

#define ms(a) memset((a),0,sizeof(a))

#define re(i,a,b) for(register int i=(a);(i)<(b);++(i))

#define ree(i,a,b) for(register int i=(a);(i)<=(b);++(i))

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

#define reg register

typedef long long LL;

const int inf=(0x7f7f7f7f);

const int maxn=1e5+5;

struct node{int u,w;};

int n;

vector<node> adj[maxn];

struct A{int w;bool f;}a[maxn];

bool vis[maxn];

int ans;

bool f;

void dfs(int v,int par){

    int vs=adj[v].size();

    re(i,0,vs){

        int u=adj[v][i].u;

        if(vis[u]&&u!=par){//碰到已经访问过的非父亲的节点，则找到环

            ans=(adj[v][i].w-a[v].w-a[u].w)/2;//ans作为偏移值

            f=a[v].f;//保存环节点的状态，注意这里找到环之后不能return，要访问完所有节点，给所有节点打上相对值

        }

        if(!vis[u]){

            vis[u]=1;

            a[u].f=!a[v].f;

            a[u].w=adj[v][i].w-a[v].w;//一个节点的相对值为实际的两节点权值和（边长）-减去另一个节点的相对值

            dfs(u,v);

        }

    }

}

int main(){

    sf(n);

    for(int i=0,x,y,w;i<n;i++){

        sf(x),sf(y),sf(w);

        adj[x].push_back(node{y,w});

        adj[y].push_back(node{x,w});

    }

    //第一维标记标记相对值，第二维标记状态

    //假定相对值为从0开始，状态只有0,1两种，同状态的节点，其中一个需要增大，其他的都会增大

    a[1]={0,1};

    vis[1]=1;

    dfs(1,0);

    ree(i,1,n){

        if(a[i].f==f)printf("%d\n",a[i].w+ans);//和环节点状态一致的节点偏移量一样

        else printf("%d\n",a[i].w-ans);//和环节点状态相反的节点偏移量相反

    }

    return 0;

}

巴特西

# 「银联初赛第一场」自学图论的码队弟弟（dfs找环+巧解n个二元一次方程）

「银联初赛第一场」自学图论的码队弟弟（dfs找环+巧解n个二元一次方程）

最新文章

热门文章