3369. 三千米健身步道

10175101159

拒绝dfs从我做起
这就是一道数学题

#include<bits/stdc++.h>
using namespace std;
int n,x,y,rst;
int cnt[1001],fr[1000],to[1000];
int i;
int main()
{
    cin>>n;
    for(i=1;i<n;++i){
        cin>>x>>y;
        ++cnt[x],++cnt[y];
        fr[i]=x,to[i]=y;
    }
    for(i=1;i<n;++i){
        rst+=(cnt[fr[i]]-1)*(cnt[to[i]]-1);
    }
    cout<<rst;
    return 0;
}
10215101475_秦长青

龟龟

煤渣2333

DFS得出路径总数,然后除2

  • 按照常规的深搜方法,得出的路径数必然是正确答案的两倍,因为每一条路径都有对应的对称路径
  • 所以直接深搜,然后除2,就是结果啦

代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

vector<vector<int>> g;
int n;
bool visited[1010];
int ans = 0;

void dfs(int u, int depth) {
    if (depth == 4) {
        ans++;
        return ;
    }
    if (!g[u].empty()) {
        for (int it : g[u]) {
            if (!visited[it]) {
                visited[it] = true;
                dfs(it, depth + 1);
                visited[it] = false;
            }
        }
    }
}

int main() {
    cin >> n;
    g.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        visited[i] = true;
        dfs(i, 1);
        visited[i] = false;
    }
    cout << ans / 2;
    return 0;
}
╮ 潜心 ╰

蒟蒻第一次手写邻接表+DFS 斗胆发一次题解
个人做完认为其实难度不大 算图论基础题吧

#include <bits/stdc++.h>
using namespace std;
    //创建邻接表
typedef struct EdgeNode {
    int adjvex;
    int weight;
    struct EdgeNode *next;
} EdgeNode;
typedef struct VertexNode {
    int data;
    EdgeNode *FirstEdge;
} VertexNode, AdjList[1100];
typedef struct {
    AdjList adjList;
    int n_v, n_e;
} Graph;
void Creat_Adj_List (Graph *G) {
    cin >> G->n_v;
    G->n_e = G->n_v - 1;
            //如果改成更一般的模板的话 应该是cin >> G->n_v >> G->n_e
    for (int i=1; i <= G->n_v; ++i)
        G->adjList[i].FirstEdge = nullptr;
    int x, y;
    for (int i=0; i < G->n_e; ++i) {
        cin >> x >> y;
        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = y;
        e->next = G->adjList[x].FirstEdge;
        G->adjList[x].FirstEdge = e;

        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = x;
        e->next = G->adjList[y].FirstEdge;
        G->adjList[y].FirstEdge = e;
    }
}
    //以下开始深搜
int ans = 0;
bool vis[1100];
void DFS (Graph *G, int s, int len) {
    if (len == 3) {
        ++ans; return;
    }
    EdgeNode *p = G->adjList[s].FirstEdge;
    vis[s] = 1;
    while (p) {
        if (!vis[p->adjvex]) DFS(G, p->adjvex, len+1);
        p = p->next;
    }
}
int main()
{
    //freopen("testin.txt", "r", stdin);
    ios::sync_with_stdio(false);
    Graph G;
    Creat_Adj_List(&G);
    for (int i=1; i<=G.n_v; ++i) {
        DFS(&G, i, 0);
        memset(vis, 0, sizeof(vis));
    }
            //从所有顶点开始搜 每条可能的路径都被算了两遍
    cout << ans/2 << endl;
    return 0;
}
wjwjwj

using namespace std;

const int maxn = 100010;
bool vis[maxn];
int n, cnt = 0;
vector dist[maxn];

void dfs(int u, int deep) {
if (deep == 3) {
cnt++;
return;
}
for (int i = 0; i < dist[u].size(); i++) {
int v = dist[u][i];
if (!vis[v]) {
vis[v] = true;
dfs(v, deep + 1);
vis[v] = false;
}
}
}

int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
dist[u].push_back(v);
dist[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
vis[i] = true;
dfs(i, 0);
vis[i] = false;
}
cout << cnt / 2;
return 0;
}

你当前正在回复 博客/题目
存在问题!