题意：一个无向图（不一定联通）
求最长链长
n≤20，m≤50
1、dfs
#include#include #include #include #include using namespace std;#define olinr return#define _ 0#define love_nmr 0#define DB doubleinline 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); olinr ~~(0^_^0)+love_nmr;}
2、状压DP（注意数组大小，MLE QAQ）
#include#include #include #include #include using namespace std;#define olinr return#define _ 0#define love_nmr 0#define DB doubleinline 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); olinr ~~(0^_^0)+love_nmr;}