网站开发流程表,设计房子装修效果图软件,如何零基础学编程,德国室内设计不难看出#xff0c;这是一道在图上 D P DP DP的问题。设 f i f_i fi表示从 i i i出发#xff0c;能够不停的游走下去#xff0c;所需要的最少的初始资产。可以写出粗略的转移#xff1a; f u min ( f u , max ( f v − p i , r i ) ) f_u\min(f_u,\max(f_v-p_i,r…不难看出这是一道在图上 D P DP DP的问题。设 f i f_i fi表示从 i i i出发能够不停的游走下去所需要的最少的初始资产。可以写出粗略的转移 f u min ( f u , max ( f v − p i , r i ) ) f_u\min(f_u,\max(f_v-p_i,r_i)) fumin(fu,max(fv−pi,ri))。
一个粗略的想法是我们找出所有的环然后跑 spfa \text{spfa} spfa。但是找环需要枚举环上的一个点难以优化。
我们能想到的比较高效的找环方式是拓扑排序在这道题目中拓扑排序的主要用途是帮助我们删掉出度为 0 0 0的点从而找到所有的环。因此考虑删掉所有出度为 0 0 0的点此时每个点都至少在一个环中因此 f u f_u fu的初值是 r m a x r_{max} rmax。事实上我们甚至可以通过拓扑排序找到包含节点 u u u的所有环中 r m a x r_{max} rmax的最小值这一点后面会提到。
考虑如何求出 f u f_u fu。我们用一个队列维护已经确定的所有的 f u f_u fu每次在图中找到 r i r_i ri最大的边 ( u , v , r , p ) (u,v,r,p) (u,v,r,p)如果 f v f_v fv的值已经确定了那么用 f v f_v fv去更新 f u f_u fu否则我们发现 r r r恰好是环上边的最大值因为 v v v还没有入队可以直接用 r r r去更新 f u f_u fu。然后我们将这条最大的边从图中删去将出度为 0 0 0的点加入队列即可。注意每次操作完要将队列清空保证每个点至少在一个环中。
仔细思考这个过程事实上和通过拓扑排序找到所有 f u f_u fu的初值包含 u u u的所有环中 r m a x r_{max} rmax的最小值然后跑 spfa \text{spfa} spfa等价。当然 spfa \text{spfa} spfa更慢
复杂度 O ( m log m ) O(m\log m) O(mlogm)。瓶颈在于排序。
考场上居然没想到用拓扑排序找环。。。可能还是因为惯性思维因为不是 D A G DAG DAG所以没想到拓扑排序吧。
#includebits/stdc.h
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N2e55;
int n,m,du[N],vs[N];
struct node{int u,v,r,p;bool operator (const node a)const{return ra.r;}
}e[N];
ll f[N];
queueintQ;
vectorintG[N];
void chmin(ll x,ll y){xmin(x,y);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;for(int i1;im;i){cine[i].ue[i].ve[i].re[i].p;}sort(e1,e1m);for(int i1;im;i){G[e[i].v].pb(i),du[e[i].u];}memset(f,0x3f,sizeof f);for(int i1;in;i)if(du[i]0)Q.push(i);for(int i1;im;i){while(Q.size()){int uQ.front();Q.pop();for(auto id:G[u]){if(vs[id])continue;int ve[id].u;if(f[u]!inf)chmin(f[v],max(f[u]-e[id].p,1ll*e[id].r));vs[id]1;if(--du[v]0)Q.push(v);}}if(!vs[i]){vs[i]1;chmin(f[e[i].u],e[i].r);if(--du[e[i].u]0)Q.push(e[i].u);}}for(int i1;in;i)cout(f[i]inf?-1:f[i]) ;
}
