题目大意:给个无向图,每条边有个限制,每个点最多能买入和卖出一定黄金;然后按顺序走过n个点,求每个卖出黄金的点最多能卖出多少黄金
一开始有点懵,想着怎么再图上做这个问题,后来知道要先建一棵最大生成树
然后就好做了,做的时候黄金全都拿,不必考虑第一个条件,因为就算花不完也能在之前某个地方少买一点黄金
然后没个询问找前后两个点lca,求路径上的最小边的限制,这样就可以求出卖出多少黄金了
最后要谴责一下非常脑残的数据,有个数据点是两条链,dfs时会爆栈= =,WA了我两天十几次
话说出数据时不应该这样戏弄别人,非常浪费时间和精力又没有意义
一定要手写栈!!
#include<stdio.h> #include<string.h> #include<algorithm> #define LL long long #define INF 21474836470000 using namespace std; ; struct node{ int from,to,next; LL cost; }E[maxn*],e[maxn*]; ],Fa[maxn],dep[maxn],head[maxn],tot,logn,order[maxn],scc[maxn],bel,st[maxn*]; LL pre[maxn][]; void insert(int u, int v, LL c){ e[++tot].to=v; e[tot].next=head[u]; e[tot].cost=c; head[u]=tot; } bool cmp(node a, node b){ return a.cost>b.cost; } int find(int x){ return Fa[x]==x?x:Fa[x]=find(Fa[x]); } void dfs(int u, int f){ ; st[++top]=u; while (top){ u=st[top--]; f=fa[u][]; dep[u]=dep[f]+; ; i<=logn; i++) fa[u][i]=fa[fa[u][i-]][i-]; ; i<=logn; i++) pre[u][i]=min(pre[u][i-],pre[fa[u][i-]][i-]); for (int i=head[u]; i; i=e[i].next) if (e[i].to!=f){ fa[e[i].to][]=u; pre[e[i].to][]=e[i].cost; st[++top]=e[i].to; } } } LL lca(int u, int v){ LL ret=INF; if (dep[u]<dep[v]) swap(u,v); while (dep[u]>dep[v]){ ; i--) if (dep[fa[u][i]]>dep[v]){ ret=min(ret,pre[u][i]); u=fa[u][i]; } ret=min(ret,pre[u][]); u=fa[u][]; } if (u==v) return ret; ; i--) if (fa[u][i]!=fa[v][i]){ ret=min(ret,pre[u][i]); ret=min(ret,pre[v][i]); u=fa[u][i]; v=fa[v][i]; } ret=min(ret,min(pre[v][],pre[u][])); return ret; } int main(){ //freopen("motorcycle6.in","r",stdin); //freopen("test.out","w",stdout); scanf("%d%d%d", &n, &m, &q); <<logn)<n) logn++; tot=; memset(pre,,sizeof(pre)); ; i<=n; i++) scanf("%d", &order[i]),Fa[i]=i;// shunxu ; i<=n; i++) scanf("%d", &trade[i]);// yaoqiu ; i<=m; i++) scanf("%d%d%lld", &E[i].from, &E[i].to, &E[i].cost); bel=n; ,x; i<=q; i++) scanf(,bel=min(bel,x); sort(E+,E++m,cmp); ; else num=n-q; ,hehe=; i<=m; i++){ int x=E[i].from, y=E[i].to; if (scc[x]) x=bel; if (scc[y]) y=bel; int fx=find(x), fy=find(y); if (fx!=fy){ Fa[fx]=fy; insert(x,y,E[i].cost); insert(y,x,E[i].cost); hehe++; if (hehe==num) break; } } fa[][]=; dfs(,); LL now=; ]]<) puts(]]; ; i<=n; i++){ ], y=order[i]; if (scc[x]) x=bel; if (scc[y]) y=bel; now=min(now,lca(x,y)); x=order[i-]; y=order[i]; ) now+=(LL)trade[y]; else{ ){ now+=(LL)trade[y]; printf("%d\n", -trade[y]); }else{ printf("%lld\n", now); now=0LL; } } //printf("%lld\n", now); } ; }