题目链接：https://nanti.jisuanke.com/t/30994
分析：场上ltx用dfs爆过去了，学习之后发现和状压dp的思想一致
dfs：类似topo_sort的思想，选择度为0的点进行dfs，不断更新最大值，这里和状压dp类似的地方就是使用了一个state变量。
状压dp：对每一种状态进行二进制枚举，枚举到一种状态时，判断这个状态里的顺序是否符合题意，符合的话更新dp数组
dfs代码：
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define mod 1000000007
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define FRER() freopen("in.txt","r",stdin);
#define FREW() freopen("out.txt","w",stdout);using namespace std;typedef pair<int,int> pii;
const int maxn = 25 , inf = 0x3f3f3f3f ;
const int N = 1<<20;
int n,nEdge,ans,sum,state,t;
int nxt[maxn*maxn],to[maxn*maxn],head[maxn*maxn],a[maxn],b[maxn],d[N],degree[maxn],vis[maxn];void AddEdge(int u,int v){nxt[nEdge] = head[u],to[nEdge] = v,head[u] = nEdge++;degree[v]++;
}
void dfs(int u){vis[u] = 1;state^=1<<(u-1);sum += t*a[u] + b[u];if(sum>d[state]){t++;d[state] = sum;ans = max(ans,sum);for(int e = head[u];~e;e=nxt[e])degree[to[e]]--;for(int i=1;i<=n;i++)if(degree[i]==0&&!vis[i]) dfs(i);for(int e = head[u];~e;e=nxt[e])degree[to[e]]++;t--;}sum -= t*a[u]+b[u];vis[u] = 0 , state^=1<<(u-1);
}
int main(){//FRER();mem(vis,0);mem(head,-1);t = 1;nEdge = ans = sum = state = 0;scanf("%d",&n);for(int i=1;i<=n;i++){int ai,bi,ki,k;scanf("%d%d%d",&a[i],&b[i],&ki);while(ki--){scanf("%d",&k);AddEdge(k,i);}}d[0] = 0;for(int i=1;i<=n;i++){if(degree[i]==0){dfs(i);}}printf("%d\n",ans);
}状压dp代码：
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define mod 1000000007
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define FRER() freopen("in.txt","r",stdin);
#define FREW() freopen("out.txt","w",stdout);using namespace std;typedef pair<int,int> pii;
const int maxn = (1<<20) + 7 , inf = 0x3f3f3f3f ;
int n,nEdge;
int dp[maxn],a[25],b[25],nxt[25*25],to[25*25],head[25*25];void AddEdge(int u,int v){to[nEdge] = v , nxt[nEdge] = head[u] , head[u] = nEdge++;
}bool check(int u){for(int i=1;i<=n;i++){if(!((1<<(i-1))&u)) continue;for(int e=head[i];~e;e=nxt[e]){int v = to[e];if(!((1<<(v-1))&u)) return false;}}return true;
}void solve(int u){for(int i=1;i<=n;i++){if(!(1<<(i-1)&u)) continue;int t = 0 , tmp = u;while(tmp){if(tmp&1) t++;tmp>>=1;}dp[u]=max(dp[u],dp[u^(1<<(i-1))]+t*a[i]+b[i]);}
}int main(){//FRER();nEdge = 0;mem(dp,0);mem(head,-1);scanf("%d",&n);for(int i=1;i<=n;i++){int ai,bi,ki,k;scanf("%d%d%d",&a[i],&b[i],&ki);while(ki--){scanf("%d",&k);AddEdge(i,k);}}for(int i=0;i<(1<<n);i++){if(!check(i)) continue;solve(i);}printf("%d\n",dp[(1<<n)-1]);return 0;
}