[ CCO 2015 ] Artskjid

(\)

(Description)

---

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

• (Nin[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
",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
",ans);
  return 0;
}