题解 - Vijos

1

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    struct sta
    {
        ll x,fa,i;
    };
    
    ll n;
    vector<int> vis;
    vector<ll> c,v;
    vector<sta> stk;
    vector<vector<ll>> e;
    vector<vector<ll>> ev;
    
    void main()
    {
        while (~scanf("%lld",&n))
        {
            e.resize(n),ev.resize(n);
            for (ll i=0;i<n;i++)
                e.resize(0),ev.resize(0);
            for (ll i=1,a,b,c;i<n;i++)
            {
                scanf("%lld%lld%lld",&a,&b,&c);
                a--,b--;
                e[a].push_back(b);
                ev[a].push_back(c);
                e[b].push_back(a);
                ev[b].push_back(c);
            }
            c.resize(n,1),v.resize(n,0);
            sta begin;
            begin.x=0,begin.fa=-1,begin.i=0;
            for (vis.resize(n,0),stk.clear(),stk.push_back(begin);!stk.empty();)
            {
                vis[stk.back().x]=1;
                for (ll i=stk.back().i;i<e[stk.back().x].size();i++,stk.back().i=i)
                    if (e[stk.back().x][i]!=stk.back().fa)
                    {
                        if (vis[e[stk.back().x][i]])
                        {
                            c[stk.back().x]+=c[e[stk.back().x][i]];
                            v[stk.back().x]+=llabs(2*c[e[stk.back().x][i]]-n)*ev[stk.back().x][i]+v[e[stk.back().x][i]];
                        }
                        else
                        {
                            sta next;
                            next.x=e[stk.back().x][i];
                            next.fa=stk.back().x;
                            next.i=0;
                            stk.push_back(next);
                            break;
                        }
                    }
                if (stk.back().i>=e[stk.back().x].size())
                    stk.pop_back();
            }
            printf("%lld\n",v[0]);
        }
    }
}

int main()
{
    dts::main();
}

0

ljt12138 LV 10 @ 8 年前

测试数据 #0: Accepted, time = 0 ms, mem = 39696 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 39700 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 39700 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 39700 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 39700 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 39696 KiB, score = 5
测试数据 #6: Accepted, time = 15 ms, mem = 39696 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 39696 KiB, score = 5
测试数据 #8: Accepted, time = 0 ms, mem = 39700 KiB, score = 5
测试数据 #9: Accepted, time = 15 ms, mem = 39696 KiB, score = 5
测试数据 #10: Accepted, time = 15 ms, mem = 39700 KiB, score = 5
测试数据 #11: Accepted, time = 15 ms, mem = 39700 KiB, score = 5
测试数据 #12: Accepted, time = 15 ms, mem = 39704 KiB, score = 5
测试数据 #13: Accepted, time = 46 ms, mem = 39696 KiB, score = 5
测试数据 #14: Accepted, time = 343 ms, mem = 39700 KiB, score = 5
测试数据 #15: Accepted, time = 375 ms, mem = 39700 KiB, score = 5
测试数据 #16: Accepted, time = 531 ms, mem = 39696 KiB, score = 5
测试数据 #17: Accepted, time = 546 ms, mem = 39700 KiB, score = 5
测试数据 #18: Accepted, time = 765 ms, mem = 39700 KiB, score = 5
测试数据 #19: Accepted, time = 1296 ms, mem = 39696 KiB, score = 5
Accepted, time = 3992 ms, mem = 39704 KiB, score = 100
不懂下面神牛的做法。直接bfs+dp

代码

#include <bits/stdc++.h>
using namespace std;

int read()
{
        int a = 0, c;
        do c = getchar(); while (!isdigit(c));
        while(isdigit(c)) {
                a = a*10+c-'0';
                c = getchar();
        }
        return a;
}

int n;
struct p {
        int to, next, dis;
}edge[2000005];
int head[1000005], top = 0, depth[1000005], size[1000005], dq[1000005], dtp = 0;
queue<int> stk;
void push(int i, int j, int k)
{
        edge[++top].to = j;
        edge[top].dis = k;
        edge[top].next = head[i];
        head[i] = top;
}

long long dx(int i)
{
        depth[i] = 0;
        stk.push(i);
        while (!stk.empty()) {
                int now = stk.front(); stk.pop();
                dq[++dtp] = now;
               // cout << now <<"--"<< endl;
                for (int i = head[now]; i; i = edge[i].next) {
                        int to = edge[i].to;
                        //cout << to<<" "<<depth[to] << endl;
                        if (depth[to] > depth[now] + 1) {
                                depth[to] = depth[now] + 1;
                                stk.push(to);
                        }
                }
        }
        long long ans = 0;
        while (dtp) {
                int to = dq[dtp--];
                size[to] = 1;
                for (int i = head[to]; i; i = edge[i].next)
                if (depth[edge[i].to] > depth[to]) {
                                size[to] += size[edge[i].to];
                                ans += (long long)edge[i].dis * abs(n-size[edge[i].to]-size[edge[i].to]);
                }
        }
        return ans;
}

int main()
{
        memset(depth, 127/3, sizeof depth);
        memset(size, 0, sizeof size);
        n = read();
        int x, y, z;
        for (int i = 1; i < n; i++) {
                x = read(); y = read(); z = read();
               // cout <<x <<endl;
                push(x, y, z);
                push(y, x, z);
        }
        cout << dx(1) << endl;
        return 0;
}

0

Onlynagesha LV 9 @ 8 年前

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>

typedef long long int64;
using std::abs;
using std::cout;

const int maxN = 1000005;

struct Edge
{
int to, next, weight;
void assign (int t, int n, int w)
{
to = t;
next = n;
weight = w;
}
};

Edge elist[maxN << 1];
int head[maxN] = {0};
int ecnt (0);
int N;

inline void addEdge (int u, int v, int w)
{
elist[++ecnt].assign (v, head[u], w);
head[u] = ecnt;
elist[++ecnt].assign (u, head[v], w);
head[v] = ecnt;
}

void input ()
{
scanf ("%d", &N);

for (int i = 1, u, v, w; i < N; i++)
{
scanf ("%d%d%d", &u, &v, &w);
addEdge (u, v, w);
}
}

int parent[maxN] = {0};
int size[maxN];
int proc[maxN];
int weight[maxN];
int pos (1);

void bfs ()
{
std::queue<int> que;
que.push (1);
parent[1] = proc[1] = 1;

while (!que.empty ())
{
int cur = que.front ();
que.pop ();

for (int e = head[cur]; e; e = elist[e].next)
{
int& to = elist[e].to;

if (to != parent[cur])
{
que.push (to);
proc[++pos] = to;
parent[to] = cur;
weight[to] = elist[e].weight;
}
}
}
}

int64 solve ()
{
int64 ans (0LL);
bfs ();

for (int i = N, cur; i > 1; i--)
{
cur = proc[i];
size[cur] = 1;

for (int e = head[cur]; e; e = elist[e].next)
{
int& to = elist[e].to;

if (to != parent[cur]) size[cur] += size[to];
}

ans += 1LL * weight[cur] * abs (N -
(size[cur] << 1));
}

return ans;
}

int main ()
{
input ();
cout << solve ();
return 0;
}

0

t14t41t LV 10 @ 9 年前

分析题目可知，只要处理好每条边两端到底有多少国家就可以了。而对于这个问题，我们可以随便找一个根，一遍树形DP维护每个结点为根的子树的大小，即size域。最后统计答案时枚举所有边，利用求出的size域可得道路两边国家个数差的绝对值。
本题不能直接递归，否则会爆栈，应手动改成非递归；
还应注意计算的中间过程可能会爆int，要强制类型转换；
不要被卡常数；

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1000005
#define nil 0
#define oo 1000000000
#define ll long long
using namespace std;
int n, sz[N], lst[N], fa[N];
int u[N << 1], v[N << 1], w[N << 1], nxt[N << 1], pnt[N], e;
int S[N], top;
bool vis[N];
ll ans;
inline void add(int a, int b, int c)
{
u[++e] = a; v[e] = b; w[e] = c;
nxt[e] = pnt[a]; pnt[a] = e;
}
inline int aas(int a) //我对cmath库有阴影。。。
{
return (a >= 0 ? a : -a);
}
inline int read()
{
char ch = getchar();
int a = 0;
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9')
{
a = a * 10 + ch - 48;
ch = getchar();
}
return a;
}
inline void init()
{
int a, b, c;
n = read();
u[0] = v[0] = w[0] = nxt[0] = pnt[0] = e = top = 0;
for(int i = 1; i < n; ++i)
{
a = read(); b = read(); c = read();
add(a, b, c); add(b, a, c);
}
for(int i = 1; i <= n; ++i) lst[i] = pnt[i];
memset(vis, 0, sizeof(vis));
}
void work()
{
S[++top] = 1; vis[1] = true;
while(top > 0) //非递归dfs整棵树得到size域
{
int t = S[top];
for(int i = lst[t]; i != nil; i = nxt[i]) if(!vis[v[i]]) //lst数组用来进行当前弧优化
{
fa[v[i]] = t;
S[++top] = v[i];
vis[v[i]] = true;
lst[t] = nxt[i];
break;
}
if(t == S[top])
{
sz[t] = 1;
for(int i = pnt[t]; i != nil; i = nxt[i]) if(v[i] != fa[t])
{
sz[t] += sz[v[i]];
}
--top;
}
}
for(int i = 1; i <= e; ++i)
{
if(fa[v[i]] == u[i]) ans += (ll)aas(n - sz[v[i]] - sz[v[i]]) * w[i];
else ans += (ll)aas(n - sz[u[i]] - sz[u[i]]) * w[i];
}
ans >>= 1; //统计时两个方向都统计了一遍，所以答案除以二
printf("%lld\n", ans);
}

int main()
{
init();
work();
return 0;
}

0

hyl LV 10 @ 11 年前

cow!dfs搞了半天60分，bfs一会就ac了

0

lihanwenxc LV 8 @ 11 年前

program bzojp2435;
var now,n,i,k,l,r:longint;
u,v,w,next:array[0..2000000]of longint;
save,line,point,father,deep:array[0..1000001]of longint;
a,b,c,min:int64;p:array[0..1000000]of boolean;
ans:qword;
begin
read(n);
for i:=1 to n-1 do begin
read(u[i*2-1],v[i*2-1],w[i*2-1]);
next[i*2-1]:=point[u[i*2-1]];point[u[i*2-1]]:=i*2-1;
u[i*2]:=v[i*2-1];v[i*2]:=u[i*2-1];w[i*2]:=w[i*2-1];
next[i*2]:=point[u[i*2]];point[u[i*2]]:=i*2;
end;
fillchar(deep,sizeof(deep),127);
line[1]:=1;deep[1]:=1;l:=1;r:=1;p[1]:=true;
repeat
now:=point[line[l]];
while now<>0 do begin
if p[v[now]]=true then begin
now:=next[now];continue;
end;
if deep[line[l]]+1<deep[v[now]] then begin
deep[v[now]]:=deep[line[l]]+1;
father[v[now]]:=line[l];
inc(r);line[r]:=v[now];
p[v[now]]:=true;now:=next[now];
end;
end;
inc(l);
until l=n+1;
for i:=1 to n do save[i]:=1;
for i:=n downto 1 do
save[father[line[i]]]:=save[father[line[i]]]+save[line[i]];
for i:=1 to n-1 do
begin
min:=save[u[i*2-1]];
if save[v[i*2-1]]<min then
min:=save[v[i*2-1]];
ans:=ans+w[i*2-1]*abs(n-2*min);
end;
writeln(ans);
end.

题解

6 条题解

代码

道路修建

信息

状态

开发

支持

题解

6 条题解

代码

道路修建

信息

状态

开发

支持

还没有账户？

登录