题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3875
题意：见 loj 题面。
做不上原题的我真是太弱了 T.T
如果考虑 dp 的话，式子是很好写出的：\(dp_i=min(k_i,\sum dp_{son[i]})\)
如果原图是个 dag 可以按照拓扑序搞，然而不是...
之前做 fks 大爷模拟赛的时候学到了用 spfa 迭代同层后效性 dp，然而一做题就忘了...
对于某些 dp 是具有同层后效性的，也就是说同层的 dp 值可以相互转移（尽管此题只有一层）
我们可以对应转移关系建立图论模型，跑 spfa 来多次迭代，每次松弛就将这个点能更新到的点都入队，就跑的飞起了...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 200010 #define M 1000010 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to; }edge[M],Edge[M]; int cnt=1,head[N],Head[N]; void add(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt; Edge[cnt].to=from; Edge[cnt].next=Head[to]; Head[to]=cnt++; } int n; ll s[N],k[N],dp[N]; queue<int> q; bool vis[N]; void spfa() { for(int i=1;i<=n;i++) q.push(i),vis[i]=1; while(!q.empty()) { int x=q.front();q.pop(); vis[x]=0; ll tmp=s[x]; for(int i=head[x];i;i=edge[i].next) tmp+=dp[edge[i].to]; if(tmp<dp[x]) { dp[x]=tmp; for(int i=Head[x];i;i=Edge[i].next) if(!vis[Edge[i].to]) { vis[Edge[i].to]=1; q.push(Edge[i].to); } } } } int main() { n=read(); for(int i=1;i<=n;i++) { s[i]=read(),k[i]=read(); int tmp=read(); for(int j=1;j<=tmp;j++) { int x=read(); add(i,x); } } for(int i=1;i<=n;i++)dp[i]=k[i]; spfa(); printf("%lld\n",dp[1]); } |
Comments | NOTHING