NOIP 2015 疫情控制

評測傳送

二分答案+貪心。

越往上越優，是以在枚舉的範圍内，能往上就往上。

細節處理很重要。

我的代碼有一處是待優化的，調了一下午，身心俱疲，不想再寫了。

就這樣吧 95分。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
const int N=50009;
int n,m;
int head[N],nxt[2*N],to[2*N],w[2*N],tot;
LL dis[N][20],dep[N],maxn;
int f[N][20];
int vis[N],leaf,siz[N],used[N];
int qe[N],num[N],r;
struct H{
    int x;
    LL rest;
}q[N];
H qq[N];
bool cmp1(H a,H b){return a.rest>b.rest;}
void add(int x,int y,int z)
{
    siz[x]++;
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    w[tot]=z;
}
void dfs(int x)
{
    for(int i=head[x];i;i=nxt[i])
    {
        if(!dep[to[i]]&&to[i]!=1)
        {
            dep[to[i]]=dep[x]+1;
            f[to[i]][0]=x;
            dis[to[i]][0]=w[i];
            dfs(to[i]);
        }
    }
}
void dfs_check(int father,int x)
{
    if(vis[x]) return;
    if(siz[x]==1&&!vis[x]) {leaf=1;return;};
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]!=father&&!vis[to[i]])
         dfs_check(x,to[i]);
    }
}
bool check(LL len)
{
    int n1=0,n2=0;
    memset(vis,0,sizeof(vis));
    memset(used,0,sizeof(used));
    for(int i=1;i<=r;i++)
    {
        int x=qe[i];LL res=len;
        for(int j=16;j>=0;j--)
        {
            while(f[x][j]&&f[x][j]!=1&&dis[x][j]<=res) res-=dis[x][j],x=f[x][j];
        }
        if(f[x][0]==1&&dis[x][0]<res) 
        for(int j=1;j<=num[qe[i]];j++) q[++n1]=((H){x,res-dis[x][0]});
        else 
        vis[x]=1;
    }
    sort(q+1,q+n1+1,cmp1);

    for(int i=head[1];i;i=nxt[i])
    {
        leaf=0;dfs_check(1,to[i]);
        if(leaf) qq[++n2]=(H){to[i],w[i]}; 
    }
    sort(qq+1,qq+n2+1,cmp1);

    if(n1<n2) return 0;

    int i,j,flag=0;
    for(i=1;i<=n2;i++)
    {
        for(j=n1;j>=1;j--)
        if(!used[j])
        if(qq[i].x==q[j].x||q[j].rest>=qq[i].rest) 
        {
            used[j]=1;
            vis[qq[i].x]=1;
            break;
        }
    }
    for(int i=1;i<=n2;i++)
    if(!vis[qq[i].x]) return 0;
    return 1;
}
int main()
{
    //freopen("sick.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    tot=0;
    dfs(1);

    for(int j=1;(1<<j)<=n;j++)
      for(int i=1;i<=n;i++)
        if(f[f[i][j-1]][j-1]){
            f[i][j]=f[f[i][j-1]][j-1];
            dis[i][j]=dis[f[i][j-1]][j-1]+dis[i][j-1];
    }  
    scanf("%d",&m);     
    for(int x,i=1;i<=m;i++)
    {
        scanf("%d",&x);
        num[x]++;   
    }
    for(int i=1;i<=n;i++) if(num[i]) qe[++r]=i;
    LL L=0,R=(n+5)*(1e9),mid;maxn=R;
    while(L<=R)
    {
        mid=(L+R)>>1;
        if(check(mid)) R=mid-1;
        else L=mid+1;
    }
    if(L<maxn)printf("%lld\n",L);
    else printf("-1\n");
    //cout<<check(9);
    return 0;
}