科普网站建设的支持力度,网络推广培训公司,企业邮箱申请流程,wordpress open social正题
题目链接:https://www.luogu.org/problem/U94222?contestId23574 题目大意 nnn个点若条有向边,求一条路径要求
经过一个酒店经过权值最大消费最小起点编号最小
按照顺序满足。 解题思路
将强连通分量缩成一个点#xff0c;然后用gi,0/1g_{i,0/1}gi,0/1到达第iii个…正题
题目链接:https://www.luogu.org/problem/U94222?contestId23574 题目大意
nnn个点若条有向边,求一条路径要求
经过一个酒店经过权值最大消费最小起点编号最小
按照顺序满足。 解题思路
将强连通分量缩成一个点然后用gi,0/1g_{i,0/1}gi,0/1到达第iii个点是否经过酒店的最大权值fi,0/1f_{i,0/1}fi,0/1最小消费nui,0/1nu_{i,0/1}nui,0/1最小编号即可。然后跑DAGdpDAGdpDAGdp即可 codecodecode
#includecstdio
#includestack
#includequeue
#includecstring
#define ll long long
using namespace std;
const ll N110000;
stackll Stack;
queuell q;
struct line{ll to,from,next;
}a[N];
ll n,m,x,y,tot,maxs,top,num;
ll in[N],ls[N],fl[N],cost[N],f[N][2],g[N][2];
ll J[N],low[N],dfn[N],anc[N],anv[N],val[N],nu[N][2];
bool ins[N],v[N],hotel[N];
void addl(ll x,ll y,ll tot)
{a[tot].toy;a[tot].fromx;a[tot].nextls[x];ls[x]tot;
}
void tarjan(ll x)
{ins[x]true;dfn[x]low[x]top;Stack.push(x);for (ll ils[x];i;ia[i].next)if (!dfn[a[i].to]){tarjan(a[i].to);low[x]min(low[x],low[a[i].to]);}else if (ins[a[i].to])low[x]min(low[x],dfn[a[i].to]);if (low[x]dfn[x]){while (Stack.top()!x){ll yStack.top();fl[y]x;anc[x]cost[y];anv[x]val[y];hotel[x]|hotel[y];Stack.pop();ins[y]0;nu[x][0]min(nu[x][0],y);}fl[x]x;anc[x]cost[x];anv[x]val[x];ins[x]0;nu[x][0]min(nu[x][0],x);nu[x][1]nu[x][0];Stack.pop();}
}
void bfs()
{while (!q.empty()){ll xq.front();q.pop();for (ll ils[x];i;ia[i].next){ll ya[i].to;if(g[x][0]anv[y]g[y][hotel[y]])g[y][hotel[y]]g[x][0]anv[y],f[y][hotel[y]]f[x][0]anc[y],nu[y][hotel[y]]nu[x][0];else if(g[x][0]anv[y]g[y][hotel[y]]f[y][hotel[y]]f[x][0]anc[y])f[y][hotel[y]]f[x][0]anc[y],nu[y][hotel[y]]nu[x][0];else if(g[x][0]anv[y]g[y][hotel[y]]f[y][hotel[y]]f[x][0]anc[y])nu[y][hotel[y]]min(nu[y][hotel[y]],nu[x][0]);if(g[x][1]anv[y]g[y][1])g[y][1]g[x][1]anv[y],f[y][1]f[x][1]anc[y],nu[y][1]nu[x][1];else if(g[x][1]anv[y]g[y][1]f[y][1]f[x][1]anc[y])f[y][1]f[x][1]anc[y],nu[y][1]nu[x][1];else if(g[x][1]anv[y]g[y][1]f[y][1]f[x][1]anc[y])nu[y][1]min(nu[y][1],nu[x][1]);if(g[x][0]anv[y]g[y][0])g[y][0]g[x][0]anv[y],f[y][0]f[x][0]anc[y],nu[y][0]nu[x][0];else if(g[x][0]anv[y]g[y][0]f[y][0]f[x][0]anc[y])f[y][0]f[x][0]anc[y],nu[y][0]nu[x][0];else if(g[x][0]anv[y]g[y][0]f[y][0]f[x][0]anc[y])nu[y][0]min(nu[y][0],nu[x][0]);in[y]--;if (!in[y]!v[y]){q.push(y);v[y]1;}}}
}
int main()
{memset(nu,0x3f,sizeof(nu));scanf(%lld,n);for(ll i1;in;i)scanf(%lld,cost[i]);for(ll i1;in;i)scanf(%lld,val[i]);scanf(%lld,m);for(ll i1;im;i)scanf(%lld,J[i]);for(ll i1;im;i)while(1){ll x;scanf(%lld,x);if(!x) break;addl(x,(xJ[i]-1)%n1,tot);}for(ll i1;in;i)scanf(%lld,hotel[i]);for(ll i1;in;i)if (!dfn[i])tarjan(i);ll Tottot;tot0;memset(ls,0,sizeof(ls));for (ll i1;iTot;i){xa[i].from;ya[i].to;if (fl[x]!fl[y]){tot;addl(fl[x],fl[y],tot);in[fl[y]];}}memset(g,-127,sizeof(g));for (ll i1;in;i)if (fl[i]i!in[i]){q.push(i);v[i]true;g[i][0]g[i][hotel[i]]anv[i];f[i][0]f[i][hotel[i]]anc[i];}bfs();maxs0;g[0][0]g[0][1]0;ll mark0,Mark0;for(ll i1;in;i)if(fl[i]i){if(g[i][0]g[mark][0]) marki;else if(g[i][0]g[mark][0]f[i][0]f[mark][0])marki;else if(g[i][0]g[mark][0]f[i][0]f[mark][0]nu[i][0]nu[mark][0])marki;if(g[i][1]g[Mark][1]) Marki;else if(g[i][1]g[Mark][1]f[i][1]f[Mark][1])Marki;else if(g[i][1]g[Mark][1]f[i][1]f[Mark][1]nu[i][1]nu[Mark][1])Marki;}if(!Mark)printf(%lld %lld %lld,-nu[mark][0],-g[mark][0],-f[mark][0]);else printf(%lld %lld %lld,nu[Mark][1],g[Mark][1],f[Mark][1]);
}
