這個題好像有一萬種解法，有spfa雙向擴搜的，有分層圖轉移的，bfs的，，，，，
題目描述：
n個點m條邊，每個點有一個權值代表在這個點買或者賣水晶球的價格
有一個人從1走到n問你能夠賺的最多的差價是多少（只能買賣一次）
題目思路：
這是一個帶環的有向圖
首先可以把環縮成一個點，記錄這個點的買賣的最高價格和最低價格
（因為對于一個環內所有的點，這些點可以相互到達）
那么現在圖就變成了一個DAG
對于當前點u滿足
dp[u] = max(max(dp[u],dp[v]),val_max[u]-minn[v]);
其中max(dp[u],dp[v])記錄能夠到達n點的路徑上的最大差值
一開始推成了dp[v] =val_max[v] - minn[v];
然后掃了一邊取最大值
這樣有可能最后到達的那個點并不是n點
Code：
int head[maxn],cnt,n,m,val[maxn],vis[maxn],dfn[maxn],low[maxn],indexx,minn[maxn];
int block,id[maxn],cnt1,head1[maxn],in[maxn],valma[maxn],valmi[maxn],dp[maxn];
stack<int>st;
struct node {
int u,v,next;
} e[maxn],zan[maxn];
void add1(int u,int v ) {
zan[cnt1].u=u;
zan[cnt1].v=v;
zan[cnt1].next=head1[u];
head1[u]=cnt1++;
}
void add(int u,int v ) {
e[cnt].u=u;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++indexx;
vis[u] = 1;
st.push(u);
for(int i=head1[u]; ~i; i=zan[i].next) {
int v = zan[i].v;
if(dfn[v]==0) tarjan(v), low [u] = min(low[u],low[v]);
else if(vis[v]) low[u] = min(low[u],dfn[v]);
}
int ma = -inf,mi = inf;
if(low[u] == dfn[u]) {
int yy;
block++;
do {
yy = st.top();
st.pop();
vis[yy] =0 ;
ma =max(ma,val[yy]);
mi =min(mi,val[yy]);
id[yy] = block;
} while(yy!=u);
valmi[block] = mi;
valma[block] = ma;
}
}
void top_sort() {
queue<int>q;
q.push(id[1]);
while(q.size()) {
int u = q.front();
q.pop();
for(int i =head[u]; ~i; i=e[i].next) {
int v = e[i].v;
minn[v] = min (minn[u],valmi[v]);
dp[v] = max(max(dp[u],dp[v]),valma[v]-minn[v]);
in[v]--;
if(in[v]==0) q.push(v);
}
}
}
int main() {
mst(head1,-1);
n=read(),m=read(),mst(head,-1);
rep(i,1,n) val[i] = read(),minn[i] = inf;
for(int i=1 ; i<=m ; i++) {
int op,u,v;
u=read(),v=read(),op=read();
add1(u,v);
if(op==2) add1(v,u);
}
tarjan(1);
for(int i = 0 ; i<cnt1 ; i++) {
int u = zan[i].u;
int v = zan[i].v;
if(id[u]!=id[v]) add(id[u],id[v]),in[id[v]]++;
}
top_sort();
out(dp[id[n]]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/229956.html
標籤：其他