BZOJ 4027 兔子与樱花

原来想的是给所有点排序。。。。但是要修改啊。。。然后发现对于儿子排序就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 2000050
#define maxv 2000050
#define maxe 4000050
using namespace std;
int n,m,c[maxn],s[maxn],x,top=,ans=,g[maxv],nume=,fath[maxv],tot[maxv];
bool vis[maxn];
struct pnt
{
int id,rank;
}p[maxn];
struct edge
{
int v,nxt;
}e[maxe];
struct value
{
int val,id;
}ret[maxn];
queue <int> q;
int read()
{
char ch;int data=;
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='')
{
data=data*+ch-'';
ch=getchar();
}
return data;
}
bool cmp1(pnt x,pnt y) {return x.rank<y.rank;}
bool cmp2(value x,value y) {return x.val<y.val;}
void addedge(int u,int v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void topusort()
{
p[].id=;p[].rank=;q.push();
while (!q.empty())
{
int head=q.front();q.pop();
for (int i=g[head];i;i=e[i].nxt)
{
int v=e[i].v;
p[v].id=v;p[v].rank=p[head].rank+;
q.push(v);
}
}
sort(p+,p+n+,cmp1);
}
int main()
{
n=read();m=read();
for (int i=;i<=n;i++) c[i]=read();
for (int i=;i<=n;i++)
{
s[i]=read();
for (int j=;j<=s[i];j++)
{
x=read();x++;
addedge(i,x);fath[x]=i;tot[i]+=c[x];
}
}
topusort();
for (int i=n;i>=;i--)
{
top=;int now=p[i].id;
for (int j=g[now];j;j=e[j].nxt)
{
int v=e[j].v;
ret[++top].val=c[v]+s[v]-;
ret[top].id=v;
}
sort(ret+,ret+top+,cmp2);
for (int j=;j<=top;j++)
{
if (c[now]+s[now]+ret[j].val<=m)
{
ans++;
tot[now]+=tot[ret[j].id];
c[now]+=c[ret[j].id];
s[now]+=s[ret[j].id]-;
}
}
}
printf("%d\n",ans);
return ;
}
上一篇:lnmp 60秒的服务器缓存时间


下一篇:浅谈__declspec(dllexport)和__declspec(dllimport)