UVALive - 6436、HYSBZ

这两道题都是用`简单dfs`解的，主要是`熟悉回溯过程`就能做，据说用`bfs`也能做

道路修建（HYSBZ - 2435）

在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家

之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好n – 1条双向道路。每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4个国家，如果该道路长度为 1，则费用为1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。

由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建

费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计

算出所需要的费用。请你帮助国王们设计一个这样的软件。

Input

输入的第一行包含一个整数n，表示 W 星球上的国家的数量，国家从 1到n

编号。接下来 n – 1行描述道路建设情况，其中第 i 行包含三个整数ai、bi和ci，表

示第i 条双向道路修建在 ai与bi两个国家之间，长度为ci。

Output

输出一个整数，表示修建所有道路所需要的总费用。

Sample Input

1 2 1

1 3 1

1 4 2

6 3 1 5 2 1

Sample Output

Hint

n = 1,000,000 1≤ai, bi≤n

0 ≤ci≤ 10^6

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <queue>

#include <iomanip>

#include <stack>

#include <algorithm>

#include <vector>

#include <functional>

using namespace std;

typedef long long LL;

#define Fil(Array, len, num) fill(Array, Array + len, num)

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

const double PI = 3.1415926;

const double E = 2.1718281828;

const int MAXN = 1000005;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

struct Edge

{

    int to, w, next;

}edge[MAXN << 1];

int head[MAXN << 1], cnt, vis[MAXN];

void Add(int a, int b, int c)

{

    edge[++cnt].to = b;

    edge[cnt].w = c;

    edge[cnt].next = head[a];

    head[a] = cnt;

}

int n, num[MAXN];

LL ans;

void dfs(int s)

{

    num[s] = 1;

    for(int i = head[s];i != -1;i = edge[i].next)

    {

        if(!vis[edge[i].to])

        {

            vis[edge[i].to] = 1;

            dfs(edge[i].to);

            num[s] += num[edge[i].to];

            ans += (LL)abs(n - 2 * num[edge[i].to]) * edge[i].w;//这里要注意是num[edge[i].to]

        }

    }

}

int main()

{

    scanf("%d", &n);

    Fil(head, MAXN, -1);

    int a, b, c;

    for(int i = 1;i < n;++i)

    {

        scanf("%d%d%d", &a, &b, &c);

        Add(a, b, c);

        Add(b, a, c);

    }

    vis[1] = 1;

    dfs(1);

    cout << ans << endl;

    return 0;

}

UVALive - 6436

题目里面的图拉不下来，就自己看题吧

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <queue>

#include <iomanip>

#include <stack>

#include <algorithm>

#include <vector>

#include <functional>

using namespace std;

typedef long long LL;

#define Fil(Array, len, num) fill(Array, Array + len, num)

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

const double PI = 3.1415926;

const double E = 2.1718281828;

const int MAXN = 1000005;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

vector<int> mp[MAXN];

int num[MAXN], n;

LL ans;

void dfs(int s, int fa)

{

    num[s] = 1;

    int len = mp[s].size();

    LL t = 0;

    for(int i = 0;i < len;++i)

    {

        if(mp[s][i] == fa)

            continue;

        dfs(mp[s][i], s);

        num[s] += num[mp[s][i]];

//        这里是算该点之后的所有点，然后算忙碌度

        t += (LL)((n - num[mp[s][i]] - 1) * num[mp[s][i]]);

//        cout << s << " " <<  mp[s][i] << " " << t << " " << num[mp[s][i]] << endl;

    }

//    这里还要算这个点前面的有几个点，加上忙碌度，算出来每两个点都算了两次

    t += (LL)(n - num[s]) * (num[s] - 1);

    ans = max(ans, t);

}

int main()

{

    int T;

    scanf("%d", &T);

    for(int cas = 1;cas <= T;++cas)

    {

        for(int i = 0;i < MAXN;++i)

            mp[i].clear();

        ans = 0;

        scanf("%d", &n);

        for(int i = 1;i < n;++i)

        {

            int a, b;

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

            mp[a].push_back(b);

            mp[b].push_back(a);

        }

        dfs(1, -1);

        printf("Case #%d: %lld\n", cas, ans / 2);

    }

    return 0;

}

巴特西

UVALive - 6436、HYSBZ - 2435 (dfs)

这两道题都是用`简单dfs`解的，主要是`熟悉回溯过程`就能做，据说用`bfs`也能做

道路修建（HYSBZ - 2435）

Input

Output

Sample Input

Sample Output

Hint

UVALive - 6436

最新文章

热门文章

巴特西

UVALive - 6436、HYSBZ - 2435 (dfs)

这两道题都是用简单dfs解的，主要是熟悉回溯过程就能做，据说用bfs也能做

道路修建（HYSBZ - 2435）

Input

Output

Sample Input

Sample Output

Hint

UVALive - 6436

最新文章

热门文章

这两道题都是用`简单dfs`解的，主要是`熟悉回溯过程`就能做，据说用`bfs`也能做