[ CCO 2015 ] Artskjid

\(\\\)

\(Description\)

\(N\)个点\(M\)条边的有向图，求从\(0\)号节点出发，\(N-1\)号节点结束，且图中每个点至多经过一次的最长路。

\(N\in[2,18]\)

\(\\\)

\(Solution\)

状压\(DP\)最长路。

记忆化搜索的写法，可以通过调整回溯值来保证终点一定是\(N-1\)号节点\((\)无法到达就返回负无穷\()\)。

直接状压\(DP\)初始化要注意设成负无穷，然后统计答案只计算当前点是\(N-1\)号点的情况。

\(\\\)

\(Code\)

\(\\\)

记搜版本

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 20

#define M 410

#define R register

#define gc getchar

#define inf 2000000000

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

int n,m,tot,hd[N],f[1<<N][N];

struct edge{int w,to,nxt;}e[M];

inline void add(int u,int v,int w){

  e[++tot].to=v; e[tot].w=w;

  e[tot].nxt=hd[u]; hd[u]=tot;

}

int dfs(int u,int s){

  if(u==n-1) return 0;

  if(f[s][u]>0) return f[s][u];

  int ans=-inf;

  for(R int i=hd[u],v;i;i=e[i].nxt){

    v=e[i].to;

    if(s&(1<<v)) continue;

    ans=max(ans,e[i].w+dfs(v,(s|(1<<v))));

  }

  return f[s][u]=ans;

}

int main(){

  n=rd(); m=rd();

  for(R int i=1,u,v,w;i<=m;++i){

    u=rd(); v=rd(); w=rd(); add(u,v,w);

  }

  printf("%d\n",dfs(0,1));

  return 0;

}

\(\\\)

直接状压版本

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 20

#define M 410

#define R register

#define gc getchar

#define inf 2000000000

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

int n,m,tot,ans,hd[N],f[1<<N][N];

struct edge{int w,to,nxt;}e[M];

inline void add(int u,int v,int w){

  e[++tot].to=v; e[tot].w=w;

  e[tot].nxt=hd[u]; hd[u]=tot;

}

int main(){

  n=rd(); m=rd();

  for(R int i=1,u,v,w;i<=m;++i){

    u=rd(); v=rd(); w=rd(); add(u,v,w);

  }

  int lim=(1<<n);

  for(R int s=0;s<lim;++s)

  	for(R int u=0;u<n;++u) f[s][u]=-inf;

  f[1][0]=0;

  for(R int s=1;s<lim;++s){

    for(R int u=0;u<n;++u)

      if(((s&(1<<u))>0)&&f[s][u]>=0)

        for(R int i=hd[u],v;i;i=e[i].nxt){

          v=e[i].to; if((s&(1<<v))>0) continue;

          f[s|(1<<v)][v]=max(f[s|(1<<v)][v],f[s][u]+e[i].w);

        }

    ans=max(ans,f[s][n-1]);

  }

  printf("%d\n",ans);

  return 0;

}

巴特西

[ CCO 2015 ] Artskjid

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章