[CCF] 201503-5 最小花费
题目:
思路:
思路是LCA求出路径,然后再贪心,价钱最低的时候把后面需要的粮食都卖了
只得了30分
我觉得肯定是tle了,应该不会RE,它数据量太大了,离线处理想不到什么好办法,
在线处理的话我觉得就是找LCA,求出路径再贪心。
LCA可以O1, 求路径就On了,再加个sort,妥妥地TLE
我的30分代码
/*
CCF 201503-5 最小花费
xzc
30分 运行错误??
2019.12.9
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int maxm = 2e5+20;
struct Edge{
int to,Next;
}edge[maxm];
int head[maxn],tot;
int n;//城市数量
int price[maxn];//物品价格
int dfn[maxn*2]; //记录欧拉序
int deep[maxn*2]; //记录深度
int father[maxn]; //记录每个节点父节点的编号
int Fir[maxn]; //记录每个节点在欧拉序中首次出现的位置
int cnt; //用于给dfn标号
int Min[maxn*2][23]; //ST表
int suffixSum[maxn]; //用于记录路程的后缀和
int Log2[maxn*2]={-1}; //用来快速求对数
int num[maxn]; //辅助数组
int downFirstLess[maxn]; //往下走(远离根节点)第一个物价比当前节点小的
int upFirstLess[maxn]; //往上走(靠近根节点)第一个物价比当前节点小的
void DFS(int u,int fa)
{
for(int i=head[u];i!=-1;i=edge[i].Next)
{
int v = edge[i].to;
if(price[v])
}
}
vector<int> route,Dis; //route存的是一路上经过的点,Dis存的是路的长度
bool cmp(int,int);
int LCA (int,int); //求最近公共祖先
void RMQ(); //用于预处理ST表
void dfs(int,int,int); //对树进行先序遍历并回溯,生成欧拉序和深度信息等
void initEdge(); //初始化邻接表
void addedge(int,int); //邻接表加边
int main()
{
int u,v,d,m;
// while(cin>>n>>m)
// {
cin>>n>>m;
map<pair<int,int>,int> mp; //用于存放边的长度
initEdge(); //初始化邻接表
for(int i=1;i<=n;++i) //输入每个点的物品价格
scanf("%d",price+i);
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&u,&v,&d);
addedge(u,v); //存边
addedge(v,u);
mp[make_pair(u,v)] = d; //记录边长
mp[make_pair(v,u)] = d;
}
cnt = 0; //初始化序号为0
dfs(1,1,1); //获得欧拉序,深度,和首次出现的位置
RMQ(); //预处理ST表
while(m--)
{
scanf("%d%d",&u,&v);
int lca = LCA(u,v); //求出两点的lca
route.clear();
Dis.clear();
while(true)
{
route.push_back(u);
if(u==lca) break;
u = father[u];
}
stack<int> st;
while(v!=lca)
{
st.push(v);
v = father[v];
}
while(!st.empty())
{
route.push_back(st.top());
st.pop();
}
//得到了路线图,一路上经过route.size() = len个点,len-1条边
//然后贪心,物价从小到大遍历点,每次在点把后面的路的粮食都买好
int len = route.size();
for(int i=0;i<len-1;++i)
Dis.push_back(mp[make_pair(route[i],route[i+1])]);
for(int i=0;i<len;++i)
num[i] = route[i];
sort(num,num+len,cmp); //排序
map<int,int> PointToDfn;
for(int i=0;i<len;++i)
{
PointToDfn[route[i]] = i; //记录每个点在路径中的编号
}
suffixSum[len-1] = 0;
for(int i=len-2;i>=0;--i)
suffixSum[i] = suffixSum[i+1]+Dis[i];
int Left = len-1; //Left之前的路都还没买粮食
long long res = 0;
for(int i=0;i<len;++i)
{
int node = num[i]; //node号节点
int pos = PointToDfn[node]; //在路径中是第pos个
if(pos<Left)
{ //价钱 路程之和(后缀和维护)
res += 1ll*price[node]*(suffixSum[pos]-suffixSum[Left]);
Left = pos;
if(pos==0) break;
}
}
printf("%lld\n",res);
}
// }
return 0;
}
void RMQ()
{
int N = n*2-1;
for(int i=1;i<=N;++i)
Min[i][0] = i, Log2[i] = Log2[i/2]+1;
for(int j=1;(1<<j)<=N;++j)
{
for(int i=1;i+(1<<j)-1<=N;++i)
{
int a = Min[i][j-1];
int b = Min[i+(1<<(j-1))][j-1];
Min[i][j] = deep[a]>deep[b]?b:a;
}
}
}
int LCA (int u,int v)
{
int x = Fir[u], y = Fir[v];
if(x>y) swap(x,y);
int j = Log2[y-x+1];
int a = Min[x][j], b = Min[y-(1<<j)+1][j];
return deep[a]>deep[b]?dfn[b]:dfn[a];
}
void initEdge()
{
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int from,int to)
{
edge[tot].to = to;
edge[tot].Next = head[from];
head[from] = tot++;
}
void dfs(int u,int fa,int dep)
{
father[u] = fa;
dfn[++cnt] = u;
deep[cnt] = dep;
Fir[u] = cnt;
for(int i=head[u];i!=-1;i=edge[i].Next)
{
int v = edge[i].to;
if(v==fa) continue;
dfs(v,u,dep+1);
dfn[++cnt] = u;
deep[cnt] = dep;
}
}
bool cmp(int x,int y)
{
return price[x]<price[y];
}
感谢wyt学姐提供的思路
日后有空再实现这个思路吧~