46 条题解
-
1
Sky1231 (sky1231) LV 10 @ 2020-10-26 14:50:39
#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; ll rt=1; class tr_node { public: ll fa,cnt,cost; vector<ll> s,c; }; ll num[(1<<17)+1],ans[(1<<17)+1]; tr_node tr[(1<<17)+1]; void tr_dfs1(ll now,ll fa) { tr[now].fa=fa; tr[now].cnt=num[now]; tr[now].cost=0; for (ll i=0;i<tr[now].s.size();i++) if (tr[now].s[i]!=fa) { tr_dfs1(tr[now].s[i],now); tr[now].cnt+=tr[tr[now].s[i]].cnt; tr[now].cost+=tr[tr[now].s[i]].cost+tr[tr[now].s[i]].cnt*tr[now].c[i]; } } void tr_dfs2(ll now) { if (now==rt) ans[now]=tr[now].cost; for (ll i=0;i<tr[now].s.size();i++) if (tr[now].s[i]!=tr[now].fa) { ans[tr[now].s[i]]=ans[now]+(tr[rt].cnt-2*tr[tr[now].s[i]].cnt)*tr[now].c[i]; tr_dfs2(tr[now].s[i]); } } ll n,ansn; void main() { scanf("%lld",&n); for (ll i=1;i<=n;i++) scanf("%lld",&num[i]); for (ll i=1;i<=n;i++) tr[i].s.clear(),tr[i].c.clear(); for (ll i=1;i<n;i++) { ll x,y,c; scanf("%lld%lld%lld",&x,&y,&c); tr[x].s.push_back(y),tr[x].c.push_back(c); tr[y].s.push_back(x),tr[y].c.push_back(c); } tr_dfs1(rt,rt); tr_dfs2(rt); ansn=rt; for (ll i=2;i<=n;i++) if (ans[ansn]>ans[i]) ansn=i; printf("%lld\n%lld\n",ansn,ans[ansn]); } } int main() { dts::main(); } -
0
#include<cstdio> #include<cstring> #define N 100001 #define M 200001 using namespace std; struct node{int next,to,w;}e[M];int l[M],a[N],n,tot,ansi; long long ans=2147483647456465234557ll,f[N],rs[N],jl[N]; bool vis[N]; void add(int u,int v,int w) { e[tot]={l[u],v,w};l[u]=tot++; e[tot]={l[v],u,w};l[v]=tot++; return; } void dfs(int x,int dep) { vis[x]=true; jl[x]=a[x]*dep;rs[x]=a[x]; for(int i=l[x];~i;i=e[i].next) { int y=e[i].to; if(!vis[y]) dfs(y,dep+e[i].w),jl[x]+=jl[y],rs[x]+=rs[y]; } } void fdfs(int x,int fa,int w) { vis[x]=true; if(x!=1) f[x]=f[fa]+rs[1]*w-2*rs[x]*w; if(f[x]<ans) {ans=f[x];ansi=x;} for(int i=l[x];~i;i=e[i].next) { int y=e[i].to; if(!vis[y]) fdfs(y,x,e[i].w); } } int main() { memset(l,-1,sizeof(l)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z); dfs(1,0); memset(vis,0,sizeof(vis)); f[0]=1e9; f[1]=jl[1]; fdfs(1,0,0); printf("%d\n%lld",ansi,ans); } -
0
#include<iostream> #include<cstring> #include<cstdio> #include<vector> using namespace std; const int maxn=100020,inf=0x3f3f3f3f; struct data { int v,w,next; }e[maxn*2]; int head[maxn],cnt=1,n; long long dp[maxn],size[maxn]; void add(int u,int v,int w) { e[cnt]=(data){v,w,head[u]}; head[u]=cnt++; } void dfs1(int fa,int u) { for(int i=head[u];i;i=e[i].next) if(e[i].v!=fa) { int v=e[i].v; dfs1(u,v); size[u]+=size[v]; dp[u]+=dp[v]+size[v]*e[i].w; } } void dfs2(int fa,int u) { for(int i=head[u];i;i=e[i].next) if(e[i].v!=fa) { int v=e[i].v; dp[v]=dp[u]+e[i].w*(size[1]-2*size[v]); dfs2(u,v); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&size[i]); for(int i=1;i<=n-1;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs1(0,1); dfs2(0,1); long long minn=100000000000000LL; vector<long long>ans; for(int i=1;i<=n;i++) if(minn>dp[i]){ minn=dp[i]; ans.clear(); ans.push_back(i); } else if(minn==dp[i]) { ans.push_back(i); } for(int i=0;i<ans.size();i++)printf("%lld ",ans[i]); printf("\n"); printf("%lld\n",minn); } -
0
和bzoj1827一模一样
#include<bits/stdc++.h> using namespace std; const int N=100000+10; typedef long long ll; int last[N];ll dis[N],s[N],p[N]; ll ans,ansid=1;int n,len; struct Edge{int to,next;ll val;Edge(int to=0,int next=0,ll val=0):to(to),next(next),val(val){}}e[N<<1]; void add_edge(int u,int v,ll w){e[++len]=Edge(v,last[u],w);last[u]=len;} ll dfs(int x,int fa) { ll tot=dis[x]*p[x]; s[x]=p[x]; for(int i=last[x];i;i=e[i].next) { int id=e[i].to; if(id==fa)continue; dis[id]=dis[x]+e[i].val; tot+=dfs(id,x); s[x]+=s[id]; } return tot; } void dp(int x,int fa) { for(int i=last[x];i;i=e[i].next) { int id=e[i].to; if(id==fa)continue; if(s[1]-s[id]*2<0) { ans+=(s[1]-s[id]*2)*e[i].val; ansid=id; dp(id,x); } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&p[i]); for(int u,v,i=1;i<n;i++) { ll w; scanf("%d%d%lld",&u,&v,&w); add_edge(u,v,w);add_edge(v,u,w); } ans=dfs(1,0); dp(1,0); printf("%lld\n%lld\n",ansid,ans); return 0; } -
0
feng_lingsong LV 9 @ 2015-12-26 15:32:43
一开始写的int，只过了三个点，改成longlong之后在赋初值上磕了半天，才知道longlong赋初值结尾要打LL
#include <cstdio>
#include <cstdlib>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define INF 1 << 30using namespace std;
const int maxn = 100005;
struct Node {
int nextNode, length;
Node *next;
} *N[maxn], pool[maxn << 1];int n, pool_cnt;
long long f1[maxn], f2[maxn], g1[maxn], g2[maxn];
int a[maxn], b[maxn], c[maxn], tot;inline void addedge(int x, int y, int l) {
Node *p = &pool[++pool_cnt];
*p = (Node){y, l, N[x]};
N[x] = p;
}
bool vis1[maxn];
void dfs1(int k) {
vis1[k] = true;
f2[k] = c[k];
for (Node *p = N[k]; p; p = p->next) if (!vis1[p->nextNode]) {
a[p->nextNode] = p->length;
b[p->nextNode] = k;
dfs1(p->nextNode);
f2[k] += f2[p->nextNode];
g2[k] += (g2[p->nextNode] + f2[p->nextNode] * a[p->nextNode]);
}
f1[k] = tot - f2[k];
}
bool vis2[maxn];
void dfs2(int k) {
vis2[k] = true;
g1[k] = g1[b[k]] + g2[b[k]] - g2[k] - f2[k] * a[k] + f1[k] * a[k];
for (Node *p = N[k]; p; p = p->next) if (!vis2[p->nextNode]) dfs2(p->nextNode);
}
int main(int argc, const char *argv[]) {
scanf("%d", &n);
rep(i, 1, n) {scanf("%d", &c[i]); tot += c[i];}
int x, y, l;
rep(i, 1, n - 1) {
scanf("%d %d %d", &x, &y, &l);
addedge(x, y, l); addedge(y, x, l);
}
dfs1(1);
g2[0] = g2[1];
dfs2(1);
int ans1;
long long ans2 = 1LL << 60;
rep(i, 1, n) {
if (g1[i] + g2[i] < ans2) {
ans2 = g1[i] + g2[i];
ans1 = i;
}
}
printf("%d\n%lld\n", ans1, ans2);
return 0;
} -
0
var n,min,ans:int64;
i,j,k,x,y,z,num:longint;
w:array[0..1001] of int64;
g:array[0..1001,0..1001] of int64;
begin
readln(n);
fillchar(g,sizeof(g),0);
for i:=1 to n do read(w[i]);
for i:=1 to n-1 do begin readln(x,y,z);g[x,y]:=z;g[y,x]:=z;end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
begin
if g[i,j]<>0 then continue;
if (i=k) or (i=j) or (j=k) then continue;
if (g[k,j]=0) or (g[i,k]=0) then continue;
g[i,j]:=g[i,k]+g[k,j];
g[j,i]:=g[i,j];
end;
min:=10000000000000;
for k:=1 to n do
begin
ans:=0;
for i:=1 to n do if i<>k then inc(ans,g[i,k]*w[i]);
if ans<min then begin min:=ans;num:=k;end;
end;
writeln(num);
writeln(min);
end.
请问这段代码哪里不对？为什么1个超时，6个runtime？ -
0
├ 测试数据 01：答案正确... (0ms, 3356KB)
├ 测试数据 02：答案正确... (0ms, 3356KB)
├ 测试数据 03：答案正确... (0ms, 3356KB)
├ 测试数据 04：答案正确... (0ms, 3392KB)
├ 测试数据 05：答案正确... (0ms, 3464KB)
├ 测试数据 06：答案正确... (0ms, 3536KB)
├ 测试数据 07：答案正确... (0ms, 3968KB)
├ 测试数据 08：答案正确... (0ms, 5232KB)
├ 测试数据 09：答案正确... (0ms, 9636KB)
├ 测试数据 10：答案正确... (0ms, 9636KB)
先随便抓个根建树 不用转成二叉
在这个过程中
可以顺便 算出
1各个点的size（表示以这个点为根的树包含的人数）
2各个点到根的距离
于是一个待定的解就出来了，先假设在根A处集合
然后从A开始遍历，设在A处集合时，所有人走的距离的和为B。
若C是A的儿子则所有人在C处集合的走的距离是C=B+(该边权值)*(总人数-2*size[C]) 这个很好理解吧 话一下图 重要的就是 根据已有的结果在O（1）的时间内算出另外一个
这样做的话一共是O(N)的 秒杀啊…… 记得开INT64 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 119ms
├ 测试数据 10：答案正确... 56ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：175ms一次AC，太感动了。。。。。。
-
0
写了个很丑的链表.....
总算是把建树弄的懂了....
---|---|---|---|---|---|---|---|---|---|---|
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 88ms
├ 测试数据 09：答案正确... 541ms
├ 测试数据 10：答案正确... 572ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1201ms -
0
可怜的我交了n次....
最后发现几个递归调用的子程序名称用混了......
泪奔..........
type
link=^point;
point=record
no,l:int64;
next:link;
end;
var
n,all,min,g:int64;
po,q:array[0..100000]of link;
pe,f,dis,pass:array[0..100000]of int64;
procedure build(a,b,c:int64);
var
h:link;
begin
new(h);h^.no:=b;h^.l:=c;h^.next:=nil;
if po[a]^.next=nil then
begin
po[a]^.next:=h;
q[a]:=h;
end
else
begin
q[a]^.next:=h;
q[a]:=h;
end;
end;
procedure init;
var
a,b,l:int64;h:link;i:longint;
begin
readln(n);all:=0;
for i:=1 to n do
begin
read(pe[i]);
all:=all+pe[i];
new(po[i]);
po[i]^.next:=nil;
end;
readln;
for i:=1 to n-1 do
begin
readln(a,b,l);
build(a,b,l);
build(b,a,l);
end;
fillchar(dis,sizeof(dis),0);
fillchar(f,sizeof(f),255);
fillchar(pass,sizeof(pass),255);
end;
function find(root,m:longint):int64;
var
h:link;z:int64;
begin
if pass[m] -
0
yzl609271536 LV 10 @ 2009-09-27 21:56:57
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 103ms
├ 测试数据 10：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：191ms第一个点 怎么都过不了
于是 就 多了一条写语句 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 103ms
├ 测试数据 10：答案正确... 41ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：144ms树形DP
-
0
编译通过...
├ 测试数据 01：答案错误...程序输出比正确答案长
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 119ms
├ 测试数据 10：答案正确... 119ms
这种情况的，请注意你的循环：
void dfs(long long root, long long father)
{
long long now = p[root];
sum[root] = data[root];
while(now != 0)//不要写成 while(now!=0&&tn[now].id!=father)
{
if(tn[now].id != father)
{
long long son = tn[now].id;
dfs(son, root);
sum[root] += sum[son];
f[root] += f[son] + sum[son] * tn[now].len;
}
now = tn[now].next;
}
}
Sky1231 (sky1231)
LV 10
@ 2020-10-26 14:50:39
