題目大意：
n個點，m條邊
在n個點有一個物品買入和賣出的價值
m條邊中保證x<y(連接的兩個點)
問 對一個物品買賣一次的最大利潤是多少
Solution 1：
因為邊中保證了x<y，所以可以看出有向無環圖
mi[]定義為到達i點之前（不包括i點）的最小出買賣值
那么如果在i點進行交易的話，得到的利潤為 val[i] - mi[i]
只需要列舉每個點 更新答案
然后用每個點的邊集再更新一邊 mi陣列
復雜度O（N+M）
Solution 2：
如果題目的邊中不保證x<y，是一個普通的有向圖
對所有的點的買賣價值升序排列
選最便宜的點，然后進行bfs列舉他能夠到達的所有點
更新答案
ans = max(ans,val[u]-minn1)
然后選第二便宜的點
重復上述操作
走過的點可以不用再走
因為先選的minn1 所能夠達到的點
如果minn2所能夠到達的點中和minn1到達的點中有相同的點，那么一定是minn1更優
所以minn2的再次經過時可以忽略
Code1:
ll n,m,val[maxn];
vector<ll>e[maxn];
ll ans=-inf,mi[maxn];
int main() {
n=read(),m=read();
rep(i,1,n) val[i] = read(),mi[i] = inf;
for(int i=1 ; i<=m ; i++) {
int u,v;
u=read(),v=read();
e[u].push_back(v);
}
for(int i=1 ; i<=n ; i++) {
ans = max(ans,val[i] - mi[i]);
mi[i] = min(mi[i],val[i]);
for(int j:e[i]) {
mi[j] = min(mi[j],mi[i]);
}
}
out(ans);
return 0;
}
Code2:
int n,m,ans=-inf,vis[maxn],val[maxn];
vector<int>e[maxn];
struct node {
int num,id;
} a[maxn];
bool cmp(node x,node y) {
return x.num<y.num;
}
void bfs(int st) {
queue<int>q;
q.push(a[st].id);
while(q.size()) {
int fr =q.front();
q.pop();
for(int v:e[fr]) {
if(vis[v]) continue;
vis[v]=1;
ans = max(ans,val[v] - a[st].num);
q.push(v);
}
}
}
int main() {
n=read(),m=read();
for(int i=1 ; i<=n ; i++) {
a[i].id = i;
val[i] = a[i].num = read();
}
sort(a+1,a+1+n,cmp);
for(int i=1 ; i<=m ; i++) {
int u,v;
u=read(),v=read();
e[u].push_back(v);
}
for(int i=1 ; i<=n ; i++) {
if(vis[i]) continue;
bfs(i);
}
out(ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/247715.html
標籤：其他