[POI2014]Ant colony

题目大意：
　　给定一棵$n(n\le10^6)$个结点的树。在每个叶子结点，有$g$群蚂蚁要从外面进来，其中第$i$群有$m_i$只蚂蚁。这些蚂蚁依次爬树（一群蚂蚁爬完后才会爬另一群），若当前经过结点度为$d+1$，蚂蚁数量为$m$，则接下来没走过的$d$个方向，每个方向爬$\lfloor\frac md\rfloor$只蚂蚁，剩下蚂蚁消失。在给定的一条边上有一只食蚁兽，若当前经过这条边的蚂蚁数量为$k$，则吃掉这些蚂蚁。问最后能吃到多少蚂蚁？

思路：
　　从给定边出发BFS，算出每条边会被吃掉的蚁群规模的上界和下界。若到了叶子节点，就在$\{m_i\}$中二分。然后洛谷和SZKOpuł上都能随便AC，BZOJ大力卡一波常才过。

 #include<cstdio>

 #include<algorithm>

 #include<sys/mman.h>

 #include<sys/stat.h>

 typedef long long int64;

 class BufferedInputStream {

     private:

         char *buf,*p;

         int size;

     public:

         BufferedInputStream() {

             register int fd=fileno(stdin);

             struct stat sb;

             fstat(fd,&sb);

             size=sb.st_size;

             p=buf=reinterpret_cast<char*>(mmap(,size,PROT_READ,MAP_PRIVATE,fileno(stdin),));

         }

         char getchar() {

             return (p==buf+size||*p==EOF)?EOF:*p++;

         }

 };

 BufferedInputStream in;

 inline int getint() {

     register char ch;

     while(!__builtin_isdigit(ch=in.getchar()));

     register int x=ch^'';

     while(__builtin_isdigit(ch=in.getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=1e6+;

 bool vis[N];

 int deg[N],q[N],head,tail,h[N],sz;

 int64 m[N],max[N],min[N];

 struct Edge {

     int to,next;

 };

 Edge e[N<<];

 inline void add_edge(const int &u,const int &v) {

     e[++sz]=(Edge){v,h[u]};h[u]=sz;deg[u]++;

     e[++sz]=(Edge){u,h[v]};h[v]=sz;deg[v]++;

 }

 int main() {

     const int n=getint(),g=getint(),k=getint();

     int64 lim=;

     for(register int i=;i<=g;i++) {

         lim=std::max(lim,m[i]=getint());

     }

     std::sort(&m[],&m[g]+);

     for(register int i=;i<n;i++) {

         const int u=getint(),v=getint();

         if(i==) {

             max[u]=min[u]=max[v]=min[v]=k;

             vis[u]=vis[v]=true;

             q[tail++]=u;

             q[tail++]=v;

         }

         add_edge(u,v);

     }

     int64 ans=;

     while(head<tail) {

         const int &x=q[head++];

         if(deg[x]==) {

             ans+=(int64)(std::upper_bound(&m[],&m[g]+,max[x])-std::lower_bound(&m[],&m[g]+,min[x]))*k;

         }

         for(register int i=h[x];i;i=e[i].next) {

             const int &y=e[i].to;

             if(vis[y]) continue;

             max[y]=std::min((max[x]+)*(deg[x]-)-,lim);

             min[y]=min[x]*(deg[x]-);

             vis[y]=true;

             if(min[y]<=lim) q[tail++]=y;

         }

     }

     __builtin_printf("%lld\n",ans);

     return ;

 }

巴特西

[POI2014]Ant colony

最新文章

热门文章