[NOI2008]奥运物流

C++14(g++5.4) 解法, 执行用时: 425ms, 内存消耗: 1768K, 提交时间: 2019-08-20 21:49:27

#include<bits/stdc++.h>

#define FOG(x,y,z) for(register int x=y,x##_=z;x<=x##_;++x)
#define DOG(x,y,z) for(register int x=y,x##_=z;x>=x##_;--x)
#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)

#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)

#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)

#define ts (*this)
#define sf scanf
#define pf printf

#define ll long long
#define ull unsigned long long
#define db double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)


using namespace std;

template<class T>bool tomin(T &x,T y){return y<x?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
    char c;
    x=0;
    int f=1;
    while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
    do x=(x<<3)+(x<<1)+(c^48);
    while(c=getchar(),c>='0'&&c<='9');
    x*=f;
}

const db Pi=acos(-1);
const int maxn=65;
int n,m;
int fa[maxn];
db k,c[maxn],K[maxn];
namespace P3{
    struct Edge{
        int e,to;
    }edge[maxn];
    int head[maxn],tot;
    void Add(int x,int y){
        edge[++tot]=(Edge){y,head[x]};
        head[x]=tot;
    }
    db sum;
    void dfs(int u,int f,int dep){
        sum+=c[u]*K[dep++];
        EOR(u,v)if(v!=f&&v!=1)dfs(v,u,dep);
    }
    bool mark[maxn];
    db solve(){
        sum=tot=0;
        FOR(i,1,n)head[i]=mark[i]=0;
        FOR(i,1,n)Add(fa[i],i);
        int x=1,s=0;
        do{
            ++s;
            mark[x]=1;
            x=fa[x];
        }while(!mark[x]);
        if(x!=1)return 0;
        dfs(1,0,0);
        return sum/(1.0-K[s]);
    }
}
namespace P4{
    void solve(){
        db ans=P3::solve();
        FOR(i,2,n)FOR(j,1,n)if(i!=j){
            int tmp=fa[i];
            fa[i]=j;
            tomax(ans,P3::solve());
            fa[i]=tmp;
        }pf("%.2lf",ans);
    }
}
namespace P1{
    db ans;
    void dfs(int u,int s){
        if(!s||u==n+1){
            tomax(ans,P3::solve());
            return;
        }
        dfs(u+1,s);
        FOR(i,1,n)if(i!=fa[u]){
            int tmp=fa[u];
            fa[u]=i;
            dfs(u+1,s-1);
            fa[u]=tmp;
        }
    }
    void solve(){
        dfs(2,m);
        pf("%.2lf",ans);
    }
}
namespace P5{
    int tmp[maxn];
    void solve(){
        db ans=0;
        FOR(i,2,n){
            FOR(j,1,n)tmp[i]=fa[i];
            FOR(j,2,n)if(i!=j)fa[j]=1;
            tomax(ans,P3::solve());
            FOR(j,1,n)fa[i]=tmp[i];
        }pf("%.2lf",ans);
    }
}
namespace P10{
    db dp[maxn][maxn][maxn];
    bool eg[maxn][maxn];
    int D;
    void dfs(int u){
        FOG(d,0,n)FOG(C,0,m)dp[u][C][d]=c[u]*K[d];
        FOG(v,1,n)if(eg[u][v]){
            dfs(v);
            FOG(d,0,n)DOG(c,m,0){
                db res=-(db)1e22;
                FOG(cc,0,c-1)tomax(res,dp[u][cc][d]+dp[v][c-cc-1][1]);
                FOG(cc,0,c)tomax(res,dp[u][cc][d]+dp[v][c-cc][d+1]);
                dp[u][c][d]=res;
            }
        }
        if(u==fa[1])FOG(d,0,n)if(d!=D)FOG(c,0,m)dp[u][c][d]=-(db)1e22;
    }
    void solve(){
        FOG(i,2,n)eg[fa[i]][i]=1;
        db ans=0;
        FOG(d,1,n-1){
            D=d;
            dfs(1);
            db res=0;
            FOG(c,0,m)tomax(res,dp[1][c][0]);
            tomax(ans,res/(1.0-K[d+1]));
        }
        pf("%.2lf",ans);
    }
}
int main(){
    srand(time(NULL));
    read2(n,m);
    sf("%lf",&k);
    K[0]=1;FOR(i,1,n)K[i]=K[i-1]*k;
    FOR(i,1,n)read(fa[i]);
    FOR(i,1,n)sf("%lf",&c[i]);
    if(m==0)pf("%.2lf",P3::solve());
    else if(m==1)P4::solve();
    else if(m==n-2)P5::solve();
    else if(n<=6)P1::solve();
    else P10::solve();
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 744ms, 内存消耗: 2540K, 提交时间: 2019-03-16 15:25:00

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 65;
const double oo = 1e22;
int Nxt[N], to[N], nxt[N], head[N], totE, n, m, Siz[N];
#define Adde(a,b) (to[totE] = b, nxt[totE] = head[a], head[a] = totE++)
double kk[N], dp[N][N][N], C[N], tmp[N][N], k, _MinT;
#define cans(a) ((_MinT = (a)) > ans ? ans = _MinT : 1)

void init() {
    for (int i = 0; i <= n; head[i++] = -1)
      for (int j = 0; j <= n; ++j)
        for (int k = 0; k <= n; ++k)
          dp[i][j][k] = -oo;
    totE = 0;
}

void Cal(int u, int dep) {
    for (int i = 0; i <= Siz[u]; ++i)
      for (int j = 0; j <= m; ++j)
        tmp[i][j] = -oo;
    tmp[0][0] = 0.;
    for (int i = head[u], s = 1; ~i; i = nxt[i], ++s) {
        int v = to[i];
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k)
                tmp[s][j] = max(tmp[s][j], tmp[s-1][k] + dp[v][j-k][dep]);
            
    }
}

void dfs(int u) {
    Siz[u] = 0;
    for (int i = head[u]; ~i; i = nxt[i], ++Siz[u]) dfs(to[i]);
    Cal(u, 2);
    for (int i = 0; i <= n; ++i)
      for (int j = 1; j <= m; ++j)
        dp[u][j][i] = tmp[Siz[u]][j-1] + C[u] * k;//直接将此站接到1后面

    for (int i = 0; i <= n; ++i) {
        Cal(u, i + 1);
        for (int j = 0; j <= m; ++j)
          dp[u][j][i] = max(dp[u][j][i], tmp[Siz[u]][j] + C[u] * kk[i]);
    }
}

int main() {
    scanf("%d%d%lf", &n, &m, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", Nxt + i);
    for (int i = 1; i <= n; ++i) scanf("%lf", C + i);
    kk[0] = 1; kk[1] = k;
    double ans = -oo;
    for (int i = 2; i < N; ++i) kk[i] = kk[i-1] * k;
    for (int i = Nxt[1], len = 2, j; i ^ 1; i = Nxt[i], ++len) {
        init();
        for (j = 2; j <= n; ++j) 
          if (j ^ i) Adde(Nxt[j], j); else Adde(1, j);
        dfs(1);
        cans(dp[1][m - (Nxt[i] != 1)][0] / (1. - kk[len]));
    }
    printf("%.2lf\n", ans);
    
    return 0;
}

详情