JLUCPC
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 233 Accepted Submission(s): 37
Problem Description
Dr. Skywind and Dr. Walkoncloud are planning to hold the annual JLU Collegiate Programming Contest. The contest was always held in the college of software in the past. However, they changed their minds and decided to find the most convenient location from all colleges this year.
Each college in JLU is located in one of the N (1 <= N <= 100,000) different locations (labeled as 1 to N) connected by N-1 roads. Any two colleges are reachable to each other. The Contest can be held at any one of these N colleges. Moreover, Road i connects college A_i and B_i (1 <= A_i <=N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). College i has T_i (0 <= T_i <= 1,000) teams participating in the contest.
When choosing the college to hold the Contest, Dr. Skywind wishes to minimize the inconvenience of the chosen location. The inconvenience of choosing college P is the sum of the distance that all teams need to reach college P (i.e., if the distance from college i to college P is 20, then the travel distance is T_i*20). Please help Dr. Skywind and Dr. Walkoncloud to choose the most convenient location for the contest.
Input
There are multiple test cases. For each case, the first line contains a single integer N, indicating the number of colleges. The next N lines describes T_1 to T_n. Then, each of the last N-1 lines will contain 3 integers, namely A_i, B_i and L_i.
Output
For each case, output the minimum inconvenience possible
Sample Input
3
1
1
2
1 2 2
2 3 1
4
100
1
1
1
1 2 1
2 3 1
2 4 1
Sample Output
Source
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3899
仔细想过之后发现想法很裸。
对于树中的每个结点进行切分，将树分为它左边的点集和它右边的点集（包括它自身）。即，如果给定根的话，这两部分又可分为该点的非子孙集合和子孙集合。
求出每个点的左集合与右集合的点权和。此处通过DFS或者BFS可以O(E)搞定。
求出任一点，比如1点到每一点的“不方便值”之和（BFS一遍O(E)搞定），设为DP[1]，就可以开始状态转移了。
状态转移方程：dp[i] = dp[j] + (l[i] - r[i]) * e[i][j] 转移的顺序即为DFS的访问顺序，j->i的转移的前提是j->i之间存在边，且i未被访问过。
此处l[i]为结点i的左集合权值和，r[i]为结点i的右集合权值和。
理论上2遍甚至1遍树的遍历即可搞定。
我为了清晰起见，做了1遍BFS（求1点到任意点的最短路），1遍DFS（求每点的r[i]），1遍DFS（dp状态转移）。
但是场上被卡了四个小时。这就是本题的第一个坑爹之处！！！
1.理论上超int范围的只有dp这一个数组而已，但是进行状态转移的时候会出现两个int型变量的乘法，此处导致的算术上溢我竟然一直没发现。还是太年轻啊！！
以后对于long long输出的题目，一切非标号数组还是都开long long的好。
2.long long 输出的问题以及long long定义的问题。。坑爹的杭电系统是windows。脑残不解释。
3.爆栈问题。。继续，坑爹的杭电，坑爹的windows。。。栈内存过小有木有！！！！！逼得哥用stack模拟递归！！！结果现在3899题哥的时间是倒数第一。。。
回头写个纯bfs版本的去。。我了个去。。（现场赛都不会有这些问题的，比如2.3.）代码中注释掉的是递归dfs。。
据说#pragma预处理可以设定栈内存，不会，求带。！
在
庄神的教导下，学会了编译预处理设定栈内存的写法：
#pragma comment(linker, "/STACK:1024000000,1024000000")
（这玩艺儿是mingw C++或者说VC++所独有的。。。。所以GNU C++不能用。。坑爹。。）
代码（栈模拟递归）如下：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
#define maxn 100005
struct edge
{
int from,to,next;
long long val;
edge(){}
edge(int a,int b,int c,long long d):from(a),to(b),next(c),val(d){}
}v[maxn],e[maxn * 2];
long long fuck,sum,ans,dp[maxn],l[maxn],r[maxn],d[maxn],t[maxn];
bool vis[maxn];
int n,tot;
stack <int> S1,S2;;
void init()
{
fuck = sum = ans = 0;
tot = 0;
for(int i = 0;i <= n;i++)
v[i].next = -1;
memset(d,0x7f,sizeof(d));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(dp,0,sizeof(dp));
}
void add(int p,int q,long long val)
{
e[tot] = edge(p,q,v[p].next,val);
v[p].next = tot++;
}
void bfs()
{
queue <int> Q;
d[1] = 0;
Q.push(1);
while(!Q.empty())
{
int o = Q.front();
Q.pop();
for(int k = v[o].next;~k;k = e[k].next)
{
if(d[e[k].to] > d[o] + e[k].val)
{
d[e[k].to] = d[o] + e[k].val;
Q.push(e[k].to);
}
}
}
}
void dfs1()
{
/*
vis[now] = true;
bool flag = false;
for(int k = v[now].next;~k;k = e[k].next)
{
if(!vis[e[k].to])
{
flag = true;
r[now] += dfs1(e[k].to);
}
}
if(flag)
r[now] += t[now];
else
r[now] = t[now];
return r[now];
*/
S1.push(v[0].next);
while(!S1.empty())
{
int arc = S1.top();
bool flag = false;
vis[e[arc].to] = true;
for(int k = v[e[arc].to].next;~k;k = e[k].next)
{
if(!vis[e[k].to])
{
S1.push(k);
flag = true;
break;
}
}
if(flag)
continue;
r[e[arc].to] += t[e[arc].to];
if(e[arc].from != 0)
r[e[arc].from] += r[e[arc].to];
S1.pop();
}
}
void dfs2()
{
/*
if(e[arc].to != 1)
{
dp[e[arc].to] = dp[e[arc].from] + (l[e[arc].to] - r[e[arc].to]) * e[arc].val;
if(ans > dp[e[arc].to])
ans = dp[e[arc].to];
}
vis[e[arc].to] = true;
for(int k = v[e[arc].to].next;~k;k = e[k].next)
if(!vis[e[k].to])
dfs2(k);
*/
S2.push(v[0].next);
while(!S2.empty())
{
int arc = S2.top();
bool flag = false;
vis[e[arc].to] = true;
if(e[arc].to != 1)
{
dp[e[arc].to] = dp[e[arc].from] + (l[e[arc].to] - r[e[arc].to]) * e[arc].val;
if(ans > dp[e[arc].to])
ans = dp[e[arc].to];
}
for(int k = v[e[arc].to].next;~k;k = e[k].next)
{
if(!vis[e[k].to])
{
flag = true;
S2.push(k);
v[e[arc].to].next = e[k].next;
break;
}
}
if(flag)
continue;
S2.pop();
}
}
int main()
{
while(scanf("%d",&n) == 1)
{
init();
for(int i = 1;i <= n;i++)
{
scanf("%lld",&t[i]);
sum += t[i];
}
for(int i = 1;i < n;i++)
{
int a,b;
long long c;
scanf("%d %d %lld",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
bfs();
for(int i = 1;i <= n;i++)
fuck += d[i] * t[i];
ans = dp[1] = fuck;
memset(vis,0,sizeof(vis));
add(0,1,0);
dfs1();
for(int i = 1;i <= n;i++)
l[i] = sum - r[i];
/*for(int i = 1;i <= n;i++)
printf("%lld%c",r[i],(i==n)?'\n':' ');
for(int i = 1;i <= n;i++)
printf("%lld%c",l[i],(i ==n)?'\n':' ');
*/memset(vis,0,sizeof(vis));
dfs2();
//for(int i = 1;i <= n;i++)
// printf("%lld%c",dp[i],(i ==n)?'\n':' ');
cout << ans << endl;//printf("%lld\n",ans);
}
}
Shift+0
forward paragraph
递归栈通过交C＋＋设定栈大小的代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 100005
struct edge
{
int from,to,next;
__int64 val;
edge(){}
edge(int a,int b,int c,__int64 d):from(a),to(b),next(c),val(d){}
}v[maxn],e[maxn * 2];
__int64 fuck,sum,ans,dp[maxn],l[maxn],r[maxn],d[maxn],t[maxn];
bool vis[maxn];
int n,tot;
void init()
{
fuck = sum = ans = 0;
tot = 0;
for(int i = 0;i <= n;i++)
v[i].next = -1;
memset(d,0x7f,sizeof(d));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(dp,0,sizeof(dp));
}
void add(int p,int q,__int64 val)
{
e[tot] = edge(p,q,v[p].next,val);
v[p].next = tot++;
}
void bfs()
{
queue <int> Q;
d[1] = 0;
Q.push(1);
while(!Q.empty())
{
int o = Q.front();
Q.pop();
for(int k = v[o].next;~k;k = e[k].next)
{
if(d[e[k].to] > d[o] + e[k].val)
{
d[e[k].to] = d[o] + e[k].val;
Q.push(e[k].to);
}
}
}
}
int dfs1(int now)
{
vis[now] = true;
bool flag = false;
for(int k = v[now].next;~k;k = e[k].next)
{
if(!vis[e[k].to])
{
flag = true;
r[now] += dfs1(e[k].to);
}
}
if(flag)
r[now] += t[now];
else
r[now] = t[now];
return r[now];
}
void dfs2(int arc)
{
if(e[arc].to != 1)
{
dp[e[arc].to] = dp[e[arc].from] + (l[e[arc].to] - r[e[arc].to]) * e[arc].val;
if(ans > dp[e[arc].to])
ans = dp[e[arc].to];
}
vis[e[arc].to] = true;
for(int k = v[e[arc].to].next;~k;k = e[k].next)
if(!vis[e[k].to])
dfs2(k);
}
int main()
{
while(scanf("%d",&n) == 1)
{
init();
for(int i = 1;i <= n;i++)
{
scanf("%I64d",&t[i]);
sum += t[i];
}
for(int i = 1;i < n;i++)
{
int a,b;
__int64 c;
scanf("%d %d %I64d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
bfs();
for(int i = 1;i <= n;i++)
fuck += d[i] * t[i];
ans = dp[1] = fuck;
memset(vis,0,sizeof(vis));
dfs1(1);
for(int i = 1;i <= n;i++)
l[i] = sum - r[i];
memset(vis,0,sizeof(vis));
add(0,1,0);
dfs2(v[0].next);
printf("%I64d\n",ans);
}
}