时间戳

首页 > 技术文章 > $ACM$ 课第五次作业-图论

$ACM$ 课第五次作业-图论

ChenyangXu 2020-05-04 11:28 原文

\(ACM\) 课第五次作业-图论

\(A.\ PET\)

题意

给定一颗 \(n\) 个节点的有根树，统计深度大于 \(d\) 的节点数量

输入格式

多组数据，\(d < n\leq 100000\)

输出格式

输出深度大于 \(d\) 的节点数量

题解

树上 \(dfs\) 即可

由于内存限制，下面给出链式前向星和 \(vector\) 的实现

注意，初始化 \(vector\) 时下标从 \(0\) 开始，以及链式前向星的数组开大点

\(code\)

/*vector*/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
    char c = getchar();
    int ans = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * f;
}

int t, n, d;
vector<int> g[N];
void dfs(int cur, int fa, int step, int &ans)
{
    if(step > d) ans++;
    for(auto i: g[cur])
        if(i != fa) dfs(i, cur, step + 1, ans);
}
int main()
{
    t = read();
    while(t--) {
        n = read(), d = read();
        for(int i = 0; i < n; ++i) g[i].clear();
        for(int i = 1; i < n; ++i) {
            int a = read(), b = read();
            g[a].push_back(b);
        }
        int ans = 0;
        dfs(0, -1, 0, ans);
        printf("%d\n", ans);
    }
    return 0;
}
/*
*/

/*链式前向星*/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 1e6 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
    char c = getchar();
    int ans = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * f;
}

int t, n, d, ans;
int cnt, head[N];
struct edge
{
    int to, next;
}e[N];

void addedge(int a, int b)
{
    e[cnt].to = b;
    e[cnt].next = head[a];
    head[a] = cnt++;
}
void dfs(int cur, int fa, int step, int &ans)
{
    if(step > d) ans++;
    for(int i = head[cur]; ~i; i = e[i].next) {
        int to = e[i].to;
        if(to != fa) dfs(to, cur, step + 1, ans);
    }
}
int main()
{
    t = read();
    while(t--) {
        memset(head, -1, sizeof(head));
        n = read(), d = read();
        for(int i = 1; i < n; ++i) {
            int a = read(), b = read();
            addedge(a, b);
        }
        int ans = 0;
        dfs(0, -1, 0, ans);
        printf("%d\n", ans);
    }
    return 0;
}
/*
*/

\(B.\) 哈密顿绕行世界问题

题意

给定 \(20\) 个点，每个点分别与另外 \(3\) 个点有一条有向边

给定起点，求所有回到起点的哈密顿回路，即经过起点两次，经过其他节点一次的路径

输入格式

多组数据

输出格式

输出路径，按字典序非降序排序

题解

哈密顿回路，直接 \(dfs\) 即可

\(code\)

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
    char c = getchar();
    int ans = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * f;
}

int m, vis[100];
vector<int> g[100], path;
vector< vector<int> > ans;
void dfs(int cur, int step)
{
    if(step == 21) {
        if(cur == m) ans.pb(path);
        return;
    }
    for(auto i: g[cur]) {
        if(!vis[i] || vis[i] && i == m && step == 20) {
            path.pb(i);
            if(i != m) vis[i] = 1;
            dfs(i, step + 1);
            path.erase(--path.end());
            if(i != m) vis[i] = 0;
        }
    }
}
bool cmp(vector<int> v1, vector<int> v2)
{
    for(int i = 0; i < v1.size(); ++i){
        if(v1[i] < v2[i]) return 1;
        else if(v1[i] > v2[i]) return 0;
    }
    return 1;
}
void solve()
{
    path.pb(m);
    vis[m] = 1;
    dfs(m, 1);
    sort(ans.begin(), ans.end(), cmp);
    for(int i = 0; i < ans.size(); ++i) {
        printf("%d:  ", i + 1);
        for(int j = 0; j < ans[i].size(); ++j)
            printf("%d%c", ans[i][j], " \n"[j == ans[i].size() - 1]);
    }
}
int main()
{
    for(int i = 1; i <= 20; ++i) {
        int a = read(), b = read(), c = read();
        g[a].pb(i), g[b].pb(i), g[c].pb(i);
    }
    while(cin >> m && m) {
        memset(vis, 0, sizeof(vis));
        path.clear();
        solve();
    }
    return 0;
}
/*
*/

\(C.\) 六度分离

题意

六度分离理论这么说道：任意两个不认识的人之间至多隔了 \(6\) 个人

现给定 \(n\) 个人，\(m\) 个关系，验证六度分离理论是否成立

输入格式

多组数据，\(n\leq 100,\ m\leq 200\)

输出格式

若六度分离理论成立，输出 \(Yes\)

若不成立，输出 \(No\)

题解

\(floyed\) 求任意两点之间的最短路，枚举点逐一 \(check\) 即可

注意一下 \(floyed\) 算法的枚举顺序，松弛的中点 \(k\) 在最外层

\(code\)

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
    char c = getchar();
    int ans = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * f;
}


int n, m, g[500][500], dis[500][500];
void floyed()
{
    memset(dis, inf, sizeof(dis));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(g[i][j] || i == j) dis[i][j] = g[i][j];
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
bool check()
{
    floyed();
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(g[i][j] != inf && dis[i][j] > 7) return 0;
    return 1;
}
int main()
{
    while(~scanf("%d %d", &n, &m)) {
        memset(g, 0, sizeof(g));
        for(int i = 1; i <= m; ++i) {
            int a = read(), b = read();
            g[a][b] = g[b][a] = 1;
        }
        int flag = check();
        if(flag) puts("Yes");
        else puts("No");
    }
    return 0;
}
/*
*/

\(D.\ Watchcow\)

题意

给定 \(n\) 个点，\(m\) 条双向边，求出从起点 \(1\) 出发的欧拉回路，即经过每条边各一次的回路

输入格式

\(n\leq 10000,\ M\leq 50000\)

输出格式

输出从起点 \(1\) 出发的欧拉回路

题解

欧拉回路模板题

用链式前向星维护边，\(dfs\) 一遍，回溯时记录答案，最后倒序输出即可

由于本题是双向边，答案不一定要倒序输出

\(code\)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 5e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
    char c = getchar();
    int ans = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * f;
}

int n, m;
int cnt = 1, head[N];
struct node
{
    int to, next, vis;
}e[N];
void addEdge(int a, int b)
{
    e[cnt].to = b;
    e[cnt].next = head[a];
    e[cnt].vis = 0;
    head[a] = cnt++;
}
vector<int> ans;
void dfs(int m)
{
    for(int i = head[m]; ~i; i = e[i].next) {
        if(!e[i].vis && e[i].to != -1) {
            e[i].vis = 1;
            dfs(e[i].to);
        }
    }
    ans.pb(m);
}
int main()
{
    memset(head, -1, sizeof(head));
    ans.clear();
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        int a = read(), b = read();
        addEdge(a, b), addEdge(b, a);
    }
    dfs(1);
    for(int i = ans.size() - 1; i >= 0; --i) printf("%d\n", ans[i]);//倒序输出
    return 0;
}
/*
3 3
1 2
2 3
3 1
*/

推荐阅读