题意：一个无向图（不一定联通）
求最长链长
n≤20，m≤50
1、dfs
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int m; struct node { int to; int dis; int nxt; }edge[200]; int head[60]; int cnt; bool vis[60]; int ans; inline void add(int from,int to,int dis) { cnt++; edge[cnt].to=to; edge[cnt].dis=dis; edge[cnt].nxt=head[from]; head[from]=cnt; } inline void dfs(int now,int dis) { ans=max(ans,dis); for(int i=head[now];i;i=edge[i].nxt) { int go=edge[i].to; if(!vis[go]) { vis[go]=true; dfs(go,dis+edge[i].dis); vis[go]=false; } } } int main() { n=read(); m=read(); for(int a,b,c,i=1;i<=m;i++) { a=read(); b=read(); c=read(); add(a,b,c); add(b,a,c); } for(int i=1;i<=n;i++) { vis[i]=true; dfs(i,0); vis[i]=false; } put(ans); return 0; }
2、状压DP（注意数组大小，MLE QAQ）
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define olinr return #define _ 0 #define love_nmr 0 #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int m; struct node { int to; int dis; int nxt; }edge[200]; int head[60]; int cnt; bool vis[60]; int ans; inline void add(int from,int to,int dis) { cnt++; edge[cnt].to=to; edge[cnt].dis=dis; edge[cnt].nxt=head[from]; head[from]=cnt; } int f[1<<20][21]; //f[状态][当前所在点] int main() { n=read(); m=read(); for(int a,b,c,i=1;i<=m;i++) { a=read(); b=read(); c=read(); add(a,b,c); add(b,a,c); } memset(f,-0x3f,sizeof f); //二进制每一位代表走没走过 for(int i=1;i<=n;i++) f[1<<(i-1)][i]=0; //一个点没有边所以是0 for(int i=1;i<=(1<<(n))-1;i++) //枚举状态 { for(int j=1;j<=n;j++) { if(i&(1<<(j-1))) //找到当前状态所有已遍历点 { for(int k=head[j];k;k=edge[k].nxt) //遍历与其相连的且未遍历的点 { int go=edge[k].to; if(!(i&(1<<(go-1)))) //未遍历 { f[i|(1<<(go-1))][go]=max(f[i|(1<<(go-1))][go],f[i][j]+edge[k].dis); //更新 ans=max(ans,f[i|(1<<(go-1))][go]); //取max } } } } } put(ans); return 0; }