题解

7 条题解

  • 7
    @ 2015-08-05 11:40:54

    555老子的AC率……交了7遍,就因为一个要开LL的变量手贱打成int……
    发现楼下的思路不是特别详细,我来讲得更完善一点吧。
    首先判断无解的情况。什么情况下一定有解?仔细想想就能发现,只要将所有军队都移到根节点的儿子上,就一定有解。所以读入的时候就可以做检查,如果军队数 < 根节点的儿子数就无解了。这里将“根节点的儿子”称为“目标点”。
    二分答案,问题就变成了判断所有军队能不能在给定的时间T内控制所有叶子节点。
    很容易就可以想到贪心处理。首先将每个军队向根节点移动(这很显然也很重要,因为向上移动就可能控制到更多的叶子节点),如果一个军队到不了根节点那么就停下,并且在那个点上打个标记。然后DFS一遍,如果一个点的所有儿子都被打上了标记,那么也给这个点打上标记。打完标记后就可以知道,有些目标点已经搞定了(就是打了标记的那些)。
    接下来就只要考虑如何分配剩余的军队到合适的目标点上了。把剩余的军队和目标点扔进两个数组里,按照剩余时间/目标点到根节点的距离从小到大排序。枚举一个军队,如果那个军队经过的目标点还没有搞定,那么就分配给它,因为它肯定能到那里,且目前它最没用;否则就找个离根节点最近的目标点分配给它,过不去就算了。最后检查所有的目标点是不是都被分配了,问题就解决了。

  • 2
    @ 2015-08-09 11:07:31

    #include<cstdio>
    #include<cctype>
    #include<cstring>
    #include<algorithm>

    #define For(i,x,y) for (int i=x;i<y;i++)
    #define Mid (L+R>>1)
    using namespace std;

    int IN()
    {
    int c,x;
    while (!isdigit(c=getchar()));x=c-'0';
    while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return x;
    }

    typedef long long LL;
    const int N=50000+19;
    typedef int one[N];
    struct Edge {int y,z,nxt;} E[N*2];
    struct Army
    {
    int B;LL D;
    bool operator < (const Army& Ar) const {return D<Ar.D;}
    } A[N],C[N];
    one Last,W,vis,Bel,Q;
    int Fa[N][16];LL D[N][16];
    int n,m,cnt,x,y,z,tot,Time,An,ID,Cn,cur;
    LL L,R,res;

    void Link(int x,int y,int z)
    {
    E[cnt]=(Edge){y,z,Last[x]};Last[x]=cnt++;
    E[cnt]=(Edge){x,z,Last[y]};Last[y]=cnt++;
    }
    void DFS(int x,int Anc)
    {
    Bel[x]=Anc;Q[++ID]=x;
    for (int i=Last[x];~i;i=E[i].nxt)
    if (E[i].y!=Fa[x][0]) Fa[E[i].y][0]=x,D[E[i].y][0]=E[i].z,DFS(E[i].y,Anc);
    }
    bool Check(LL T)
    {
    An=Cn=0,cur=1,Time++;
    For(i,1,m+1)
    {
    int x=W[i];LL y=T;
    for (int j=15;~j;j--) if (y>=D[x][j]) y-=D[x][j],x=Fa[x][j];
    if (x==0) A[++An]=(Army){Bel[W[i]],y};else vis[x]=Time;
    }
    for (int x=ID;x;x--)
    if (vis[Q[x]]!=Time&&~Last[Q[x]])
    {
    vis[Q[x]]=Time;
    for (int i=Last[Q[x]];~i;i=E[i].nxt)
    if (vis[E[i].y]!=Time) vis[Q[x]]=Time-1;
    }
    for (int i=Last[1];~i;i=E[i].nxt)
    if (vis[E[i].y]!=Time) C[++Cn]=(Army){E[i].y,D[E[i].y][0]};
    sort(A+1,A+An+1);
    sort(C+1,C+Cn+1);
    while (cur<=Cn&&vis[C[cur].B]==Time) cur++;
    For(i,1,An+1)
    {
    if (vis[A[i].B]!=Time) vis[A[i].B]=Time;else
    if (cur<=n&&A[i].D>=C[cur].D) vis[C[cur++].B]=Time;
    while (cur<=Cn&&vis[C[cur].B]==Time) cur++;
    }
    return cur>Cn;
    }

    int main()
    {
    memset(Last,-1,sizeof(Last));
    n=IN();
    For(i,1,n) x=IN(),y=IN(),z=IN(),Link(x,y,z);
    m=IN();
    For(i,1,m+1) W[i]=IN();
    Q[++ID]=1;
    for (int i=Last[1];~i;i=E[i].nxt)
    {
    Fa[E[i].y][0]=1,D[E[i].y][0]=E[i].z;
    DFS(E[i].y,E[i].y),tot++;
    }
    if (m<tot) return puts("-1"),0;
    For(i,1,16) for (x=1;x<=n;x++) Fa[x][i]=Fa[Fa[x][i-1]][i-1],D[x][i]=D[x][i-1]+D[Fa[x][i-1]][i-1];
    L=0,R=1LL<<60;
    while (L<=R) if (Check(Mid)) res=Mid,R=Mid-1;else L=Mid+1;
    printf("%lld\n",res);
    }

  • 2
    @ 2014-08-15 06:39:39

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int Son[50004],Parent[50004],Ecnt,Belong[50004],Bcnt;
    long long Least_Cost[50004],Deep[50004];
    struct Edge
    {
    int next,link;
    long long len;
    }ed[100005];
    inline void Add(int u,int v,long long l)
    {
    ed[++Ecnt].next=Son[u],ed[Ecnt].link=v,ed[Ecnt].len=l;
    Son[u]=Ecnt;
    }
    void Get_Deep_and_Parent(int x,int pa,long long dep)
    {
    Parent[x]=pa,Deep[x]=dep;
    for (int i=Son[x];i;i=ed[i].next)
    if (ed[i].link!=pa) Get_Deep_and_Parent(ed[i].link,x,dep+ed[i].len);
    }
    void Get_Least_Cost(int x,bool sep,long long len)
    {
    if (!sep)
    for (int i=Son[x],s=0;i;i=ed[i].next)
    if (ed[i].link!=Parent[x])
    {
    s++;
    if (s>=2)
    {
    sep=true;
    break;
    }
    }
    Least_Cost[x]=len;
    for (int i=Son[x];i;i=ed[i].next)
    if (ed[i].link!=Parent[x])
    {
    Belong[ed[i].link]=Belong[x];
    if (sep) Get_Least_Cost(ed[i].link,sep,len+ed[i].len);
    else Get_Least_Cost(ed[i].link,sep,0);
    }
    }
    int Length[50004];
    inline bool Cmp(const int& A,const int& B)
    {
    return Deep[A]<Deep[B];
    }
    inline bool Cmp1(const int &A,const int& B)
    {
    return Length[A]>Length[B];
    }
    inline bool Cmp2(const long long& A,const long long& B)
    {
    return A>B;
    }
    int Seq[50004];
    long long Sum=0;
    bool Go[50004];
    long long Rest[50004];
    int N[50004];
    int m,n;
    int Last[50004],Cur[50004];
    bool Vs[50004];
    bool Check(long long Dis)
    {
    for (int i=Son[1];i;i=ed[i].next) Go[ed[i].link]=false,Cur[ed[i].link]=0;
    Rest[0]=0;
    for (int i=1;i<=m;i++)
    {
    if (Dis>Deep[Seq[i]])
    {
    Rest[++Rest[0]]=Dis-Deep[Seq[i]];
    Last[Rest[0]]=Cur[Belong[Seq[i]]];
    Cur[Belong[Seq[i]]]=Rest[0];
    Vs[Rest[0]]=false;
    continue;
    }
    if (!Go[Belong[Seq[i]]] && Dis>=Least_Cost[Seq[i]]) Go[Belong[Seq[i]]]=true;
    }
    N[0]=0;
    for (int i=Son[1];i;i=ed[i].next)
    if (!Go[ed[i].link]) N[++N[0]]=ed[i].link;
    sort(Rest+1,Rest+Rest[0]+1,Cmp2);
    sort(N+1,N+N[0]+1,Cmp1);
    if (N[0]>Rest[0]) return false;
    for (int i=1,j=1;i<=N[0]&&j<=Rest[0];i++)
    {
    while (Vs[Cur[N[i]]]) Cur[N[i]]=Last[Cur[N[i]]];
    if (Cur[N[i]]) Vs[Cur[N[i]]]=true;
    else
    {
    if (Rest[j]<Length[N[i]]) return false;
    Vs[j]=true;
    }
    while (Vs[j]) j++;
    }
    return true;
    }
    int main()
    {
    scanf("%d",&n);
    for (int i=1,u,v,l;i<n;i++) scanf("%d%d%d",&u,&v,&l),Add(u,v,l),Add(v,u,l),Sum=Sum+l;
    Get_Deep_and_Parent(1,0,0);
    for (int i=Son[1];i;i=ed[i].next) Length[ed[i].link]=ed[i].len,Belong[ed[i].link]=ed[i].link,Bcnt++,Get_Least_Cost(ed[i].link,false,0);
    scanf("%d",&m);
    if (m<Bcnt)
    {
    puts("-1");
    return 0;
    }
    for (int i=1;i<=m;i++) scanf("%d",Seq+i);
    sort(Seq+1,Seq+m+1,Cmp);
    long long l=0,r=Sum,mid;
    while (l<r-1)
    {
    mid=(l+r)>>1;
    if (Check(mid)) r=mid;
    else l=mid;
    }
    for (long long i=l;i<=r;i++)
    if (Check(i))
    {
    printf("%I64d\n",i);
    return 0;
    }
    puts("-1");
    return 0;
    }

    • @ 2014-08-20 21:21:10

      桂兰浩东
      我是看你的题解长大的!!

    • @ 2014-10-28 23:11:06

      我也是

  • 2
    @ 2012-11-18 14:20:45

    二分搜索最短控制时间,在给定的时间内所有军队都尽可能向根运动,并将到达根节点的军队按剩余时间越多就向尽可能远的根节点下面的第一个城市调动,然后检查是否已经将所有的叶子节点与根节点隔离了。

  • 1
    @ 2018-11-06 22:33:10

    将根节点下一层的所有点称为"目标点"
    然后二分答案求将所有军队控制所有目标点所需时间即可
    具体看有良心的代码注释a,a
    这个代码十分快,排序做了预处理,总复杂度O(nlogn+nlogL)(L为答案范围)

    状态 耗时 内存占用

    #1 Accepted 4ms 8.574 MiB
    #2 Accepted 4ms 8.559 MiB
    #3 Accepted 4ms 8.559 MiB
    #4 Accepted 5ms 8.574 MiB
    #5 Accepted 5ms 8.805 MiB
    #6 Accepted 13ms 9.809 MiB
    #7 Accepted 10ms 9.457 MiB
    #8 Accepted 38ms 13.684 MiB
    #9 Accepted 75ms 18.684 MiB
    #10 Accepted 4ms 8.332 MiB

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cstdio>
    #define N 50001
    #define M 200001
    #define next nextt
    #define ms(a) memset(a,0,sizeof(a))
    using namespace std;
    typedef long long ll;
    int n,m;
    int to[M],next[M],ce[N],cnt=0,dep[N];//dep保存深度,根的深度为0,邻接表(用ce表示头指针head) 
    int f[20][N];//倍增父亲 
    ll dis[20][M],len[M];//倍增距离和保存边距离 
    int pcnt=0;//标记目标点个数 
    struct arm{
        int p,s;
        ll d;
        
    }army[N];//保存初始军队位置、对应目标点和到根节点距离 
    bool operator < (arm a,arm b){//军队从大到小排序(用mid减去后就是从小到大啦) 
            return a.d>b.d;
    }
    struct point{
        int id;
        ll d;
    }aim[N];//保存目标点(排序) 
    bool operator<(point a,point b){
            return a.d<b.d;
        }
    void link(int u,int v,ll w){//连边 
        to[++cnt]=v;
        next[cnt]=ce[u];
        len[cnt]=w;
        ce[u]=cnt;
        to[++cnt]=u;
        next[cnt]=ce[v];
        len[cnt]=w;
        ce[v]=cnt;
    }
    void budtree(int v){//倍增预处理 
        int p;
        for(p=ce[v];p;p=next[p]){
            if(to[p]==f[0][v]) continue;
            f[0][to[p]]=v;
            dis[0][to[p]]=len[p];
            dep[to[p]]=dep[v]+1;
            budtree(to[p]);
        }
    }
    int getaim(int s,ll x){//求点s往上跑x距离到达的店 
        int i,v=s;
        ll p=x;
        for(i=19;i>=0;i--){
            if(p>=dis[i][v]){
                p-=dis[i][v];
                v=f[i][v];
            }
        }
        return v;
    }
    int getp(int s){//求s对应目标点 (即上升到深度为1) 
        int p=dep[s]-1,i=0,v=s;
        while(p){
            if(p&1) v=f[i][v];
            p>>=1;
            i++;
        }
        return v;
    }
    int vis[N],acnt;//vis记录是否被控制,acnt记录剩余军队数 
    arm las[N];//表示剩余军队及其剩余时间
    int dfs(int v){   //搜索控制点 
        if(vis[v]) return 1;
        int p,fl=-1;//fl表示是否满足所有儿子都被控制 
        for(p=ce[v];p;p=next[p]){
            if(to[p]==f[0][v]) continue;
            if(dfs(to[p])==0) fl=0;
            else if(fl==-1) fl=1;
        }
        if(fl!=1) return 0;
        vis[v]=1;
        return 1;
    }
    int check(ll mid){
        int i,j,pc;//pc表示未被控制的目标点 
        acnt=0;
        ms(vis);
        for(i=1;i<=m;i++){//枚举军队 
            if(mid>=army[i].d){ //若军队可以到达根,则记录 
                las[++acnt].d=mid-army[i].d;
                las[acnt].p=army[i].p; 
            }else{//若军队不可以到达根,则控制可以到达的最远的点 
                vis[getaim(army[i].s,mid)]=1; 
            }
        }
        dfs(1);//上传控制点 
        pc=pcnt;//pc记录剩余未被控制的目标点 
        for(i=1;i<=pcnt;i++){//搜索控制点,求pc初始值 
            if(vis[aim[i].id]) pc--;
        }
        if(acnt<pc) return 0;//若根节点军队少于未控制点,返回不可行 
        j=1;//j表示当前搜索到的目标点 
        for(i=1;i<=acnt;i++){//枚举根节点的军队 (剩余时间已经为升序) 
            if(vis[las[i].p]==0){//若军队来源的点未被控制,则控制该点 
                vis[las[i].p]=1;
                continue;
            }
            while(vis[aim[j].id] && j<=pcnt) j++;//找下一个未控制点(目标点到根距离按升序排序) 
            if(j>pcnt) return 1;//若所有点已经被控制,返回可行 
            if(aim[j].d<=las[i].d){//若剩余时间可以控制下一个目标点,则控制该点 
                vis[aim[j].id]=1;
                j++;
            }
        }
        while(vis[aim[j].id] && j<=pcnt) j++;//最后找一次是否还有剩余目标点 
        if(j>pcnt) return 1;//全部控制返回可行 
        else return 0;//还有目标点未控制返回不可行 
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin>>n;
        int i,j,a,b;
        ll c;
        for(i=1;i<n;i++){//读边 
            cin>>a>>b;
            cin>>c;
            link(a,b,c);
        }
        f[0][1]=1;
        dis[0][1]=0;
        dep[1]=0;
        budtree(1);//预处理倍增 
        for(j=1;j<=19;j++){//倍增 
            for(i=1;i<=n;i++){
                f[j][i]=f[j-1][f[j-1][i]];
                dis[j][i]=dis[j-1][i]+dis[j-1][f[j-1][i]];
            }
        }
        cin>>m;
        for(i=1;i<=m;i++){//读入军队并保存对应目标点,起点,到根距离(用dis[19][a]表示) 
            cin>>a;
            army[i].p=getp(a);
            army[i].d=dis[19][a];
            army[i].s=a;
        }
        sort(army+1,army+m+1);//军队到根距离降序排序 
        for(i=ce[1];i;i=next[i]){//求目标点,保存目标点编号以及到根距离 
            aim[++pcnt].id=to[i];
            aim[pcnt].d=len[i];
        }
        sort(aim+1,aim+pcnt+1);//目标点到根距离升序排序 
        if(pcnt>m){//如果目标点数大于军队数,返回-1 
            cout<<"-1";
            return 0;
        }
        ll l=0,r=1e14,mid;
        while(l<r){//二分答案 
            mid=(l+r)>>1;
            a=check(mid);
            if(a) r=mid;
            else l=mid+1;
        }
        cout<<l;
        return 0;
    }
    
  • -4
    @ 2013-10-31 13:57:51

    目测了一下,应该是贪心+二分查找答案+树上倍增, 有时间再来写写看。。。

  • -18
    @ 2012-11-20 17:39:29

    居然不是沙发

  • 1

信息

ID
1783
难度
8
分类
贪心 | 数据结构 点击显示
标签
递交数
2114
已通过
267
通过率
13%
被复制
1
上传者