题解 - Vijos

0

绿色的云 LV 10 @ 2013-11-02 21:28:45

裸的最短路算法，用SPFA求最长路即可，稍微改一下dist数组以便理解dist[v][0]表示到达这个位置从未买过东西的最大值，
dist[v][1]表示到达这个位置买过东西还没有卖掉的最大值，dist[v][2]表示到达这个位置且东西已卖掉的最大值，然后裸跑一次SPFA即可，答案就是max(dist[n][0],dist[n][1],dist[n][2])
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 10436 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 10436 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 10428 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 10468 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 10544 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 10440 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 10436 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 10464 KiB, score = 10
测试数据 #8: Accepted, time = 93 ms, mem = 10556 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 10540 KiB, score = 10
Accepted, time = 418 ms, mem = 10556 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

#define MAXN 100010
#define MAXM 1000010
#define inf 0x7fffffff

int head[MAXN],V=0;
int next[MAXM],T[MAXM];

void AddEdge(int s,int t) {
T[++V]=t;
next[V]=head[s];
head[s]=V;
}

int n,m,Price[MAXN];

void Init() {
scanf("%d%d",&n,&m);
for (int i=0;i++<n;) scanf("%d",&Price[i]);
memset(head,0,sizeof(head));
while (m--) {
int s,t,x;
scanf("%d%d%d",&s,&t,&x);
if (x==1) AddEdge(s,t); else AddEdge(s,t),AddEdge(t,s);
}
// for (int i=0;i++<n;) printf("%d ",head[i]);printf("\n");
}

queue<int>Q;
int dist[MAXN][3];
bool f[MAXN];

int spfa() {
memset(f,false,sizeof(f));
f[1]=true;
for (int i=0;i++<n;) dist[i][0]=dist[i][1]=dist[i][2]=-inf;
dist[1][0]=0,dist[1][1]=-Price[1];
while (!Q.empty()) Q.pop();
Q.push(1);
while (!Q.empty()) {
int v=Q.front();
Q.pop();
f[v]=false;
for (int i=head[v];i;i=next[i]) {
if (dist[T[i]][0]<dist[v][0]) {
dist[T[i]][0]=dist[v][0];
if (!f[T[i]]) f[T[i]]=true,Q.push(T[i]);
}
if (dist[T[i]][1]<dist[v][0]-Price[T[i]]) {
dist[T[i]][1]=dist[v][0]-Price[T[i]];
if (!f[T[i]]) f[T[i]]=true,Q.push(T[i]);
}
if (dist[T[i]][1]<dist[v][1]) {
dist[T[i]][1]=dist[v][1];
if (!f[T[i]]) f[T[i]]=true,Q.push(T[i]);
}
if (dist[T[i]][2]<dist[v][1]+Price[T[i]]) {
dist[T[i]][2]=dist[v][1]+Price[T[i]];
if (!f[T[i]]) f[T[i]]=true,Q.push(T[i]);
}
if (dist[T[i]][2]<dist[v][2]) {
dist[T[i]][2]=dist[v][2];
if (!f[T[i]]) f[T[i]]=true,Q.push(T[i]);
}
}
}
return max(max(dist[n][0],dist[n][1]),dist[n][2]);
}

int main() {
/* freopen("trade.in","r",stdin);
freopen("trade.out","w",stdout);*/
Init();
printf("%d\n",spfa());
// fclose(stdin),fclose(stdout);
return 0;
}

0

miaoyiflyride LV 8 @ 2013-08-29 10:16:43

真是水的数据，非常渣的程序也能过...

var
a:array[1..500000] of longint;
f,b:array[1..100000] of longint;
first,last:array[1..100000] of longint;
next:array[1..500000] of longint;
i,j,k,n,m,x,y,z,h,t,ans,ii:longint;
lb:array[0..2000000] of longint;
vist:array[1..100000] of longint;
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
begin
assign(input,'p1754.in');
assign(output,'p1754.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do
read(b[i]);
for i:=1 to m do
begin
readln(x,y,z);
if first[y]=0 then
begin
inc(ii);
first[y]:=ii;
last[y]:=ii;
a[ii]:=x;
end
else
begin
inc(ii);
next[last[y]]:=ii;
last[y]:=ii;
a[ii]:=x;
end;
if z=2 then
if first[x]=0 then
begin
inc(ii);
first[x]:=ii;
last[x]:=ii;
a[ii]:=y;
end
else
begin
inc(ii);
next[last[x]]:=ii;
last[x]:=ii;
a[ii]:=y;
end;
end;
h:=0;t:=1;lb[1]:=n;
for i:=1 to n do f[i]:=b[i];
f[n]:=b[n];
while h<t do
begin
inc(h);
x:=lb[h];
y:=first[x];
while y<>0 do
begin
if vist[a[y]]<100 then
begin
f[a[y]]:=max(f[a[y]],f[x]);
inc(t);
lb[t]:=a[y];
inc(vist[a[y]]);
end;
y:=next[y];
end;
end;
for i:=1 to n do
if (f[i]-b[i])>ans then ans:=f[i]-b[i];
writeln(ans);
close(input);
close(output);
end.

0

td650739 LV 8 @ 2013-08-07 09:48:39

两遍SPFA+链式前向星 =.= 普通前向星竟然可以过。。。
代码：
Var head,next,e,c,head1,next1,e1:array[1..1000001] of longint;
x,y,z,n,m,i,j,bian,ans:longint;
Function max(a,b:longint):longint;
Begin
iF A>B THEN exit(a) else exit(b);
ENd;
Function min(a,b:longint):longint;
Begin
If a<b then exit(a) else exit(b);
End;
Procedure insert(u,v,i:longint);
Begin
e[i]:=v;
next[i]:=head[u];
head[u]:=i;
End;
Procedure insert1(u,v,i:longint);
Begin
e1[i]:=v;
next1[i]:=head1[u];
head1[u]:=i;
End;
Procedure init;
Var i,j:longint;
Begin
Readln(n,m);
For i:=1 to n do read(c[i]);
For i:=1 to m do
Begin
readln(x,y,z);
Case z of
1:
Begin
inc(bian);
insert(x,y,bian);
insert1(y,x,bian);
End;
2:
Begin
inc(bian);
insert(x,y,bian);
insert1(x,y,bian);
inc(bian);
insert(y,x,bian);
insert1(y,x,bian);
End;
End;
End;
End;
Procedure spfa;
Var q,dmax,dmin:array[1..1000000] of longint;
v:array[1..1000000] of boolean;
i,j,h,t,h1,t1,now:longint;
Begin
fillchar(q,sizeof(q),0);
Fillchar(dmax,sizeof(dmax),0);
Fillchar(v,sizeof(v),false);
h:=1; t:=1; h1:=1; t1:=1;
dmax[n]:=c[n];
q[h]:=n;
v[n]:=true;
While h<=t do
Begin
now:=q[h];
i:=head1[now];
While i<>0 do
Begin
If dmax[e1[i]]<max(dmax[now],c[e1[i]]) then
Begin
dmax[e1[i]]:=max(dmax[now],c[e1[i]]);
If not v[e1[i]] then
begin
v[e1[i]]:=true;
inc(t);
q[t]:=e1[i];
End;
End;
i:=next1[i];
End;
v[q[h]]:=false;
inc(h);
End;
fillchar(q,sizeof(q),0);
fillchar(dmin,sizeof(dmin),63);
Fillchar(v,sizeof(v),false);
h:=1; t:=1; h1:=1; t1:=1;
dmin[1]:=c[1];
q[h]:=1;
v[1]:=true;
While h<=t do
Begin
now:=q[h];
i:=head[now];
While i<>0 do
Begin
If dmin[e[i]]>min(dmin[now],c[e[i]]) then
Begin
dmin[e[i]]:=min(dmin[now],c[e[i]]);
If not v[e[i]] then
begin
v[e[i]]:=true;
inc(t);
q[t]:=e[i];
End;
End;
i:=next[i];
End;
v[q[h]]:=false;
inc(h);
End;
For i:=1 to n do
ans:=max(ans,dmax[i]-dmin[i]);
End;
Begin
init;
spfa;
Writeln(ans);
Readln;
End.

0

Totoro LV 8 @ 2013-03-10 12:09:50

网上有很多SPFA的做法，但是我不会SPFA......

可以用tarjan算法求每个极大连通分量再缩点，DFS一遍就可以了。

-1

yyyz104 LV 8 @ 2017-11-08 21:46:31

这道题的题意就不多说了，主要说下这里的两个主流做法。
1.DP：
其实这就是我最初的想法，不如让我们想想，对于一个强联通分量而言，我们想从哪里进就进，想从哪里出就出，而他们中的最小值或最大值我们是可以随便取的。当把这些强联通分量进行了缩点操作后，他们自然就变成了一个普通的点（只不过保存最小值和最大值），而在整个图则变成了一个 DAG 图，不难想到以 F[i]（取当前城市作为出售处的最大利润）的状态设计，然后先处理 Z[i] （从1所属的强联通点到i所属的强联通点中作为购入处的最小代价），再跑一遍 F[i] 即可。
2.SPFA：
这是我从网上看到的解法，是在是佩服，对所有的有向边分别以原方向和反方向建两个图（无向边...），分别从 1点和 N点跑一遍 SPFA（SPFA的状态存的是经过点的最值，正向存最小值，反向存最大值，这一切目的都是为了保证购入点在卖出点前操作），然后枚举交接点，算出两者之和的最大值即可。
SPFA代码：
正反图，正反SPFA
这个还正常些...
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF (0x3f3f3f3f)
using namespace std;
int N, M, ans;
vector<int> E1[100005], E2[100005];
int A[100005], B[100005], C[100005], V[100005];
void SPFA1 () {

queue<int> Q;
Q.push(1);
memset(V, 0, sizeof(V));
memset(B, INF, sizeof(B));
V[1]=1;
while(!Q.empty()) {
int x=Q.front();
Q.pop();
B[x]=min(B[x], A[x]);
for(int i=0; i<E1[x].size(); i++) {
int v=E1[x][i];
if (B[x]<B[v]) {
B[v]=B[x];
if (!V[v]) {
V[v]=1;
Q.push(v);
}
}
}
V[x]=0;
}

}
void SPFA2 () {

queue<int> Q;
Q.push(N);
memset(V, 0, sizeof(V));
memset(C, 0, sizeof(C));
V[N]=1;
while(!Q.empty()) {
int x=Q.front();
Q.pop();
C[x]=max(C[x], A[x]);
for(int i=0; i<E2[x].size(); i++) {
int v=E2[x][i];
if (C[x]>C[v]) {
C[v]=C[x];
if (!V[v]) {
V[v]=1;
Q.push(v);
}
}
}
V[x]=0;
}

}
int main () {

ios::sync_with_stdio(false);
cin >> N >> M;
for(int i=1; i<=N; i++) cin >> A[i];
int u, v, k;
for(int i=1; i<=M; i++) {
cin >> u >> v >> k;
E1[u].push_back(v);
E2[v].push_back(u);
if (k>1) {
E1[v].push_back(u);
E2[u].push_back(v);
}
}
SPFA1();
SPFA2();
for(int i=1; i<=N; i++) ans=max(ans, C[i]-B[i]);
cout << ans;
return 0;

}
Copy
DP代码:
Tarjan缩点+Dp
DP我是用SPFA跑的，我跑BFS要挂...
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF (0x3f3f3f3f)
using namespace std;
int N, M, G, H;
stack<int> S;
vector<int> E1[100005], E2[100005];
int A[100005], F[100005], Z[100005], X[100005], C[100005], D[100005], L[100005], V[100005];
void DP () {

queue<int> Q;
Q.push(C[1]);
memset(V, 0, sizeof(V));
V[C[1]]=1;
memset(F, -INF, sizeof(F));
F[C[1]]=0;
while(!Q.empty()) {
int x=Q.front();
Q.pop();
F[x]=max(F[x], X[x]-Z[x]);
for(int i=0; i<E2[x].size(); i++) {
int v=E2[x][i];
if (Z[v]>Z[x]||F[v]<F[x]) {
Z[v]=min(Z[v], Z[x]);
F[v]=max(F[v], F[x]);

if (!V[v]) {
V[v]=1;
Q.push(v);

}
}

}

V[x]=0;
}

}
void TARJAN (int x){

D[x]=L[x]=++G;
V[x]=1;
S.push(x);
for(int i=0; i<E1[x].size(); i++) {
int v=E1[x][i];
if (!D[v]) {
TARJAN(v);
L[x]=min(L[x], L[v]);

}

else if (V[v]) L[x]=min(L[x], D[v]);
}
if (D[x]==L[x]) {
C[x]=++H;
V[x]=0;
while(x!=S.top()) {
C[S.top()]=H;
V[S.top()]=0;
S.pop();
}
S.pop();
}

}
int main () {

ios::sync_with_stdio(false);
cin >> N >> M;
for(int i=1; i<=N; i++) cin >> A[i];
int u, v, k;
for(int i=1; i<=M; i++) {
cin >> u >> v >> k;
E1[u].push_back(v);
if (k>1) E1[v].push_back(u);

}
for(int i=1; i<=N; i++) if (!D[i]) TARJAN(i);
for(int i=1; i<=N; i++)
for(int j=0; j<E1[i].size(); j++) {
int v=E1[i][j];
if (C[i]!=C[v]) E2[C[i]].push_back(C[v]);

}

memset(Z, INF, sizeof(Z));
memset(X, 0, sizeof(X));
for(int i=1; i<=N; i++) {
Z[C[i]]=min(Z[C[i]], A[i]);
X[C[i]]=max(X[C[i]], A[i]);
}

DP();

cout << F[C[N]];
return 0;

}

-1

ATHENS_ LV 9 @ 2017-10-16 18:53:08

tarjan后DP。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x){
    int _t;bool _flag=0;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9'));
    if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
    if(_flag)_x=-_x;
}
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int ans,x,y,z,n,m,num,cnt,ct,idx,top,vl[maxn],head[maxn],hd[maxn],S[maxn],dfn[maxn],low[maxn],f[maxn];
bool ins[maxn],vis[maxn];
int dp[maxn];
struct edge{
    int v,nxt;
}d[maxn*10],d1[maxn*10];
struct node{
    int mx,mi;
}e[maxn];
inline void add(int a,int b){
    d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
}
inline void ad(int a,int b){
    d1[++ct].v=b;d1[ct].nxt=hd[a];hd[a]=ct;
}
int find(int x){
    return x==f[x]? x:f[x]=find(f[x]);
}
void tj(int u){
    int v;
    low[u]=dfn[u]=++idx;
    ins[u]=1;S[++top]=u;
    for(register int i=head[u];i;i=d[i].nxt){
        v=d[i].v;
        if(!dfn[v]){
            tj(v);
            low[u]=min(low[v],low[u]);
        }
        else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    v=0;
    if(dfn[u]==low[u]){
        while(v!=u){
            v=S[top--];
            ins[v]=0;
            int f1=find(u),f2=find(v);
            f[f2]=f1;
        }
    }
}
void dfs(int u){
    if(u==f[n])dp[u]=max(dp[u],e[u].mx);
    for(int i=hd[u];i;i=d1[i].nxt){
        int v=d1[i].v;
        if(!vis[v])dfs(v),vis[v]=1;
        dp[u]=max(dp[u],dp[v]);
    }
    if(dp[u])dp[u]=max(dp[u],e[u].mx);
    ans=max(ans,dp[u]-e[u].mi);
}
int main(){
    read(n),read(m);
    for(register int i=1;i<=n;++i){
        read(vl[i]);e[i].mi=0x3f3f3f3f;
    }
    for(int register i=1;i<=m;++i){
        read(x),read(y),read(z);
        add(x,y);
        if(z==2)add(y,x);
    }
    for(register int i=1;i<=n;++i)f[i]=i;
    for(register int i=1;i<=n;++i)if(!dfn[i])tj(i);
    for(register int k=1;k<=n;++k){
        e[f[k]].mi=min(vl[k],e[f[k]].mi);
        e[f[k]].mx=max(vl[k],e[f[k]].mx);
        for(register int i=head[k];i;i=d[i].nxt){
                int v=d[i].v;
                if(f[v]!=f[k])ad(f[k],f[v]);
            }
    }
    dfs(f[1]);
    
    printf("%d",ans);
    return 0;
}

-1

Yakult100mL LV 8 @ 2017-10-01 10:43:55

#include<iostream>
#include<vector>
using namespace std;
vector<int> g[100001];
int v[100001],n,m,x,y,z,i,answer;
int8_t sale[100001];
bool to_n[100001];
void dfs(int x)
{
if(sale[x]>0)//x点搜过
return;
sale[x]=v[x];
int i,j;
for(i=0;i<g[x].size();i++)
{
dfs(j=g[x][i]);
if(to_n[j])
{
to_n[x]=true;
sale[x]=max(sale[x],sale[j]);
}
}
if(to_n[x])//x可以买入
answer=max(answer,sale[x] - v[x]);
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
cin >> v[i];
for(i=1;i<=m;i++)
{
cin>>x>>y>>z;
g[x].push_back(y);
}
sale[n] = v[n];
to_n[n] = true;
dfs(1);
cout<<answer<<endl;
return 0;
}

-1

darkXL LV 8 @ 2017-09-27 10:08:50

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100005;
const int INF=0x3f3f3f3f;
int n,m;
int price[maxn],minp[maxn],maxp[maxn];
bool exi[maxn];
vector<int> G[maxn],anti_G[maxn];
queue<int> q;
void spfa1(){
    q.push(1);
    exi[1]=true;
    minp[1]=price[1];
    while(q.size()){
        int u=q.front();
        q.pop();
        exi[u]=false;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(minp[u]<minp[v] || price[v]<minp[v]){
                minp[v]=min(price[v],minp[u]);
                if(!exi[v]){
                    q.push(v);
                    exi[v]=true;
                }
            }
        }
    }
}
void spfa2(){
    q.push(n);
    exi[n]=true;
    maxp[n]=price[n];
    while(q.size()){
        int u=q.front();
        q.pop();
        exi[u]=false;
        for(int i=0;i<anti_G[u].size();i++){
            int v=anti_G[u][i];
            if(maxp[u]>maxp[v] || price[v]>maxp[v]){
                maxp[v]=max(maxp[u],price[v]);
                if(!exi[v]){
                    q.push(v);
                    exi[v]=true;
                }
            }
        }
    }
}
int main(){
    int x,y,z,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&price[i]);
        minp[i]=INF;
        maxp[i]=-1;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(y);
        anti_G[y].push_back(x);
        if(z==2){
            G[y].push_back(x);
            anti_G[x].push_back(y);
        }
    }
    spfa1();
    memset(exi,0,sizeof exi);
    spfa2();
    for(int i=1;i<=n;i++)if(maxp[i]!=INF && minp[i]!=-1)ans=max(ans,maxp[i]-minp[i]);
    printf("%d",ans);
}

-1

Lantern LV 8 @ 2016-11-17 17:17:34

#include <bits/stdc++.h>
#define MAXN 100000 + 10
using namespace std;
queue<int> l1, l2;
vector<int> g[MAXN], reg[MAXN];
int V, E, n, v[MAXN], d1[MAXN], d2[MAXN], vis[MAXN], ans;
int solve() {
    memset(d1, 0x3f, sizeof d1);
    memset(d2, 0, sizeof d2);
    d1[0] = v[0], d2[n] = v[V - 1];
    l1.push(0); vis[0] = 1;
    while (!l1.empty()) {
        int t = l1.front(); l1.pop(); vis[t] = 0;
        for (int i = 0; i < g[t].size(); i++) {
            int p = g[t][i];
            int mint = min(d1[t], v[p]);
            if (mint < d1[p]) {
                d1[p] = mint;
                if (!vis[p]) l1.push(p); vis[p] = 1;
            }
        }
    }
    memset(vis, 0, sizeof vis);
    l2.push(n); vis[n] = 1;
    while (!l2.empty()) {
        int t = l2.front(); l2.pop(), vis[t] = 0;
        for (int i = 0; i < reg[t].size(); i++) {
            int p = reg[t][i];
            int maxt = max(d2[t], v[p]);
            if (maxt > d2[p]) {
                d2[p] = maxt;
                if (!vis[p]) l2.push(p); vis[p] = 1;
            }
        }
    }
    for (int i = 0; i < V; i++) {
        ans = max(ans, d2[i] - d1[i]);
    }
    return ans;
}
int main() {
    cin >> V >> E;
    n = V - 1;
    for (int i = 0; i < V; i++) cin >> v[i];
    for (int i = 0, a, b, c; i < E; i++) {
        cin >> a >> b >> c;
        a--, b--;
        g[a].push_back(b);
        reg[b].push_back(a);
        if (c == 2) {
            g[b].push_back(a);
            reg[a].push_back(b);
        }
    }
    cout << solve() << endl;
    return 0;
}

-1

GloriaSeven LV 8 @ 2016-11-17 14:38:57

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100000 + 7;
const int MAXM = 1000000 + 7;
const int INF = 0x3f3f3f3f;
int n,m;
int dis1[MAXN],dis2[MAXM];
int u[MAXM],v[MAXM],w[MAXN];
 
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    #endif
     
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
 
    int j = 1; 
    for(int i = 1; i <= m; i++) 
    {
        int x,y,z;
        scanf("%d %d %d", &x, &y, &z);
        u[j] = x;
        v[j] = y;
        if(z == 2)
        {
            j++;//
            u[j] = y; 
            v[j] = x; 
        }
        j++; 
    }
     
    for(int i = 1; i <= n; i++)
    {
        dis1[i] = INF;
        dis2[i] = 0;
    }
    dis1[1] = w[1];
    dis2[n] = w[n];
     
    for(int k = 1; k <= n - 1; k++)
    {
        int temp = 0;
        for(int i = 1;i <= j - 1; i++)
        {
            if(dis1[u[i]] != INF && (dis1[v[i]] > dis1[u[i]] || dis1[v[i]] > w[v[i]]))
            {
                dis1[v[i]] = min(dis1[v[i]], dis1[u[i]]);
                dis1[v[i]] = min(dis1[v[i]], w[v[i]]);
                temp = 1;
            }
        }
        if(temp == 0)
            break;
    }
      
    for(int k = 1; k <= n - 1; k++)
    {
        int temp = 0;
        for(int i = 1; i <= j - 1; i++)
        {
            if(dis2[v[i]] != 0 && (dis2[u[i]] < dis2[v[i]] || dis2[u[i]] < w[u[i]]))
            {
                dis2[u[i]] = max(dis2[u[i]], dis2[v[i]]);
                dis2[u[i]] = max(dis2[u[i]], w[u[i]]);
                temp = 1;
            }
        }
        if(temp == 0)
            break;
    }
     
    int ans = 0;
    for(int i = 1;i <= n; i++)
    {
        if(dis1[i] != INF && dis2[i] != 0 && dis2[i] - dis1[i] > ans)
        {
            ans = dis2[i] - dis1[i];
        }
    }
  
    printf("%d\n", ans);
    return 0;
}

-1

tcc750124 LV 8 @ 2016-11-16 21:45:59

很简单，邻接表存储。做两遍spfa，一次正向（最小买入价格），一次反向（最大卖出价格）。有没有环根本没有影响。
最后枚举顶点，求**max{y(i)-x(i)}**。 x是最低买入价估计，y是最高卖出价估计
（还可以用强连通做，官方解法：将环缩成点，用dp）
代码如下：
```c++
#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
const int MAXN = 100001;
const int MAXM = 500001 ;
int Price[MAXN] ;
int tot = 0 ;
int Head[MAXN] ;
int Adj[MAXM] ;
int Next[MAXM] ;
int L[MAXN] ;
int rtot = 0 ;
int rHead[MAXN] ;
int rAdj[MAXM] ;
int rNext[MAXM] ;
int H[MAXN] ;
int n, m ;
bool Inqueue[MAXN] ;

void AddEdge(int u, int v){//正向
tot++ ;
Adj[tot] = v ;
Next[tot] = Head[u] ;
Head[u] = tot ;
return ;
}

void rAddEdge(int u, int v){//反向
rtot++ ;
rAdj[tot] = v ;
rNext[tot] = rHead[u] ;
rHead[u] = tot ;
return ;
}
void init()//输入
{
scanf("%d%d",&n,&m);
int i,t1,t2,t3;
for(i=1;i<=n;i++)
scanf("%d", Price+i);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
if(t1==t2)continue;//小小优化，自环不要考虑
AddEdge(t1, t2) ;
rAddEdge(t2, t1) ;
if(t3==2){
AddEdge(t2, t1) ;
rAddEdge(t1, t2) ;
}
}
}

void SpfaL(){
int e ;
queue<int> Q ;//stl队列
memset(L, 0x7F, sizeof(L)) ;//初始化
memset(Inqueue, false, sizeof(Inqueue)) ;
L[1] = Price[1] ;
Q.push(1) ;
Inqueue[1] = true ;
while(!Q.empty()){
int top = Q.front() ;
Inqueue[top] = false ;
Q.pop() ;
for(e = Head[top] ; e != 0 ; e = Next[e]){
if(L[Adj[e]] > min(L[top], Price[Adj[e]])){
L[Adj[e]] = min(L[top], Price[Adj[e]]) ;
if(!Inqueue[Adj[e]]){
Q.push(Adj[e]) ;
Inqueue[Adj[e]] = true ;
}
}
}
}
}

void SpfaH(){
int e ;
queue<int> Q ;
memset(H, 0, sizeof(L)) ;
memset(Inqueue, false, sizeof(Inqueue)) ;
H[n] = Price[n] ;
Q.push(n) ;
Inqueue[n] = true ;
while(!Q.empty()){
int top = Q.front() ;
Inqueue[top] = false ;
Q.pop() ;
for(e = rHead[top] ; e != 0 ; e = rNext[e]){
if(H[rAdj[e]] < max(H[top], Price[rAdj[e]])){
H[rAdj[e]] = max(H[top], Price[rAdj[e]]) ;
if(!Inqueue[rAdj[e]]){
Q.push(rAdj[e]) ;
Inqueue[rAdj[e]] = true ;
}
}
}
}
}

void work(){
SpfaL() ;
SpfaH() ;
int ans = 0 ;
for(int i= 1; i <= n ; i++)//枚举顶点
ans = max(ans, H[i] - L[i]) ;
cout << ans ;
}
int main()
{
freopen("trade.in","r",stdin);
freopen("trade.out","w",stdout);
init();
work();
return 0;
}
```

-1

qq872191552 LV 9 @ 2016-11-13 14:44:18

去掉n不能到达的点后，缩点+拓扑图dp
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#define N 100005
#define M 1000005
#define orz 2000000000
using namespace std;
inline int read( )
{
int sum=0;char c=getchar( );bool f=0;
while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}
while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}
if(f) return -sum;
return sum;
}
struct E
{
struct e{int num,next;}map[M];
int head[N],len;
inline void link(int x,int y)
{
len++;map[len].num=y;map[len].next=head[x];head[x]=len;
}
}G1,G2,G3;
int n,m,v[N];
bool vis[N];
inline void DFS(int k)
{
vis[k]=1;
for(int i=G2.head[k];i;i=G2.map[i].next)
if(!vis[G2.map[i].num]) DFS(G2.map[i].num);
}
int num[N],low[N],st[N],top,cnt;
int f[N],m1[N],m2[N],inc;
bool in[N];
inline void dfs(int k)
{
num[k]=low[k]=++cnt;st[++top]=k;in[k]=1;
int i,x;
for(i=G1.head[k];i;i=G1.map[i].next)
{
x=G1.map[i].num;
if(in[x]) low[k]=min(low[k],num[x]);
else if(!num[x]) dfs(x),low[k]=min(low[k],low[x]);
}
if(low[k]==num[k])
{
inc++;m2[inc]=orz;
while(st[top+1]!=k)
{
x=st[top--];in[x]=0;f[x]=inc;
m1[inc]=max(m1[inc],v[x]);
m2[inc]=min(m2[inc],v[x]);
}
}
}
int d[N],mn[N],ans;
queue<int>q;
int main( )
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int i,j,x,y,z;
n=read( );m=read( );
for(i=1;i<=n;i++) v[i]=read( );
for(i=1;i<=m;i++)
{
x=read( );y=read( );z=read( );
G2.link(y,x);if(z==2) G2.link(x,y);
}
DFS(n);
for(i=1;i<=n;i++)
if(vis[i])
for(j=G2.head[i];j;j=G2.map[j].next)
if(vis[G2.map[j].num]) G1.link(G2.map[j].num,i);
dfs(1);
for(i=1;i<=n;i++)
{
x=f[i];
if(x)
for(j=G1.head[i];j;j=G1.map[j].next)
{
y=f[G1.map[j].num];
if(y&&x!=y) G3.link(x,y),d[y]++;
}
}
for(i=1;i<=inc;i++) if(!d[i]) q.push(i);
for(i=1;i<=inc;i++) mn[i]=m2[i];
while(!q.empty( ))
{
x=q.front( );q.pop( );
ans=max(ans,m1[x]-mn[x]);
for(i=G3.head[x];i;i=G3.map[i].next)
{
y=G3.map[i].num;
mn[y]=min(mn[y],mn[x]);
d[y]--;if(!d[y]) q.push(y);
}
}
printf("%d",ans);
return 0;
}

-1

2233702013 LV 8 @ 2016-10-25 23:13:27

唉……为啥VIJOS上的cin和cout慢成这样……即使我关了流同步依然很慢，直接超时。
别的oj上我关掉流同步就快得多，而vijos上的效果微乎其微……
换成scanf printf果断通过

简洁明了，输入时创建正向图和反向图，先在正向图上从节点1跑一遍spfa，获得每个点的最小买入成本，再在反向图上从节点n跑一遍spfa，获得每个点的最大卖出进账，最后枚举每个点的最大卖出进账-最小买入成本，其中最大值就是答案。
spfa的时候有3个要对比的量，注意看我的代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,v[100005],ans=0,maxn[100005],minn[100005],a,b,c;
bool book[100005];
vector<int> l1[100005],l2[100005];
queue<int> que;
int main()
{
    scanf("%d%d",&n,&m); 
    for(int i=1;i<=n;i++)scanf("%d",&v[i]),minn[i]=100000000;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        l1[a].push_back(b),l2[b].push_back(a);
        if(c==2)l1[b].push_back(a),l2[a].push_back(b);
    }
    que.push(1),book[1]=1,minn[1]=v[1];
    while(!que.empty())
    {
        for(vector<int>::iterator i=l1[que.front()].begin();i!=l1[que.front()].end();i++)
        {
            int minv=min(v[que.front()],min(minn[que.front()],v[*i]));
            if(minn[*i]>minv){minn[*i]=minv;if(!book[*i])que.push(*i),book[*i]=1;}
        }
        book[que.front()]=0,que.pop();
    }
    que.push(n),book[n]=1,maxn[n]=v[n];
    while(!que.empty())
    {
        for(vector<int>::iterator i=l2[que.front()].begin();i!=l2[que.front()].end();i++)
        {
            int maxv=max(v[que.front()],max(maxn[que.front()],v[*i]));
            if(maxn[*i]<maxv){maxn[*i]=maxv;if(!book[*i])que.push(*i),book[*i]=1; } 
        }
        book[que.front()]=0,que.pop();
    }
    for(int i=1;i<=n;i++)ans=max(ans,maxn[i]-minn[i]);
    printf("%d",ans);
    return 0;
}

-1

Hory LV 10 @ 2016-10-18 20:25:41

测试数据 #0: Accepted, time = 0 ms, mem = 10444 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 10444 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 10440 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 10476 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 10536 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 10448 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 10444 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 10468 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 10548 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 10536 KiB, score = 10
Accepted, time = 76 ms, mem = 10548 KiB, score = 100

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define M 500001
#define N 100001
using namespace std;
int head[N],head1[N],mx[N],mi[N],num[N];
bool vis[N];
int n,m,ans = 0,k = 0;
struct node {
    int to,next;
}e[2*M];
inline int read() {
    int t = 1,x = 0;
    char ch = getchar();
    while ( ch < '0' || ch > '9' ) {
        if ( ch == '-' ) t = -1;
        ch = getchar();
    }
    while ( ch >= '0' && ch <= '9' ) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return t * x;
}
inline void add(int u,int v) {
    e[k].to = v; e[k].next = head[u]; head[u] = k++;
    e[k].to = u; e[k].next = head1[v]; head1[v] = k++;
}
void spfa() {
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(1); 
    vis[1] = 1; mi[1] = num[1];
    while ( !q.empty() ) {
        int now = q.front();
        q.pop(); vis[now] = 0; 
        for (int i=head[now];~i;i=e[i].next) 
            if ( mi[e[i].to] > mi[now] || mi[e[i].to] > num[e[i].to] ){
                mi[e[i].to] = min( mi[now],num[e[i].to] );
                if ( !vis[e[i].to] ) {
                    q.push(e[i].to);
                    vis[e[i].to] = 1;
                }
            }
    }
}
void spfa1() {
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(n); 
    vis[n] = 1; mx[n] = num[n];
    ans = max(ans,mx[n] - mi[n]);
    while ( !q.empty() ) {
        int now = q.front();
        q.pop(); vis[now] = 0;
        for (int i=head1[now];~i;i=e[i].next)
            if ( mx[e[i].to] < mx[now] || mx[e[i].to] < num[e[i].to] ) {
                mx[e[i].to] = max( num[e[i].to],mx[now] );
                ans = max( ans,mx[e[i].to] - mi[e[i].to] );
                if ( !vis[e[i].to] ) {
                    q.push(e[i].to);
                    vis[e[i].to] = 1;
                }
            }
    }
}
int main() {
    memset(head,-1,sizeof head);
    memset(head1,-1,sizeof head1);
    n = read(); m = read();
    for (int i=1;i<=n;i++) {
        num[i] = read();
        mi[i] = 105;
    }
    for (int i=1;i<=m;i++) {
        int u,v,w;
        u = read(); v = read(); w = read();
        add (u,v);
        if ( w == 2 ) add (v,u);
    }
    spfa();
    spfa1();
    cout<<ans<<endl;
    return 0;
}

-1

Pia LV 9 @ 2016-08-09 20:07:15

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 100000 + 50;
const int INF = 1000000000;
int n, m, top = 1, price[maxn], dist[maxn], dist2[maxn], inque[maxn];
vector<int> g[maxn];
vector<int> g2[maxn];
queue<int> q;
void init(){
    freopen ( "in.txt" , "r" , stdin);
    cin >> n >> m;
    int s, d, z;
    for(int i = 1; i <= n; i++) cin >> price[i];
    
    for(int i = 1; i <= m; i++){
        cin >> s >> d >> z;
        g[s].push_back(d);
        g2[d].push_back(s);
        if(z == 2) {
            g[d].push_back(s);
            g2[s].push_back(d);
        }
    }
}

void spfa(int s){
    for(int i = 1; i <= n; i++)
        dist[i] = 9999;
    q.push(s); inque[s] = 1;
    dist[s]=price[s];
    while(!q.empty()){
        int t = q.front(); q.pop(); inque[t] = 0;
        for(int i = 0; i < g[t].size(); i++){
            int v = g[t][i];
            int minthis = min(dist[t], price[v]);
            if(minthis<dist[v]){
                dist[v]=minthis;
                if(!inque[v]){
                    q.push(v); inque[v]=1;
                }
            }
        }
    }
}

void spfa2(int s){
    for(int i = 1; i <= n; i++)
        dist2[i] = -9999;
    q.push(s); inque[s] = 1;
    dist2[s] = price[s];
    while(!q.empty()){
        int t = q.front(); q.pop(); inque[t] = 0;
        for(int i = 0; i < g2[t].size(); i++){
            int v = g2[t][i];
            int maxthis = max(dist2[t], price[v]);
            if(maxthis>dist2[v]){
                dist2[v]=maxthis;
                if(!inque[v]){
                    q.push(v); inque[v]=1;
                }
            }
        }
    }
}
void work(){
    spfa(1);
    spfa2(n);
    int w[maxn];
    int ans = -9999;
    for(int i = 1; i <= n; i++){
        w[i] = dist2[i] - dist[i];
        ans = max(ans, w[i]);
        //cout << dist[i] << " " << dist2[i] << endl;
    }
    cout << ans;
}
int main(){
    init();
    work();
    return 0;
}

-1

Kanosword LV 7 @ 2016-07-26 20:35:00

贴题解：http://blog.csdn.net/kanosword/article/details/52006860
如果仅仅是为了完成这道题目，向下可以找到SPFA算法与强联通分量算法。
题解给出了30%数据和50%数据作法。

-1

Master_Fan LV 8 @ 2016-07-24 10:53:26

水水的dfs+简单动规
不用正反向那啥
```c++
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN=100005;

int N,M;
vector<int> way[MAXN];
int price[MAXN],low[MAXN],profit[MAXN];

void dfs(int k)
{
for (int i=0;i<way[k].size();i++)
if (!low[way[k][i]]||low[way[k][i]]>low[k]||profit[way[k][i]]<profit[k])
{
int kk=way[k][i];
if (!profit[kk]) profit[kk]=price[kk]-low[k];
profit[kk]=max(profit[kk],price[kk]-low[k]);
profit[kk]=max(profit[kk],profit[k]);
if (!low[kk]) low[kk]=price[kk];
low[kk]=min(low[k],low[kk]);
dfs(kk);
}

return;
}

int main()
{
memset(low,0,sizeof(low));
memset(profit,0,sizeof(profit));
scanf("%d%d",&N,&M);
for (int i=1;i<=N;i++)
scanf("%d",&price[i]);
for (int i=1,a,b,t;i<=M;i++)
{
scanf("%d%d%d",&a,&b,&t);
way[a].push_back(b);
if (t==2) way[b].push_back(a);
}
low[1]=price[1];
dfs(1);
printf("%d",profit[N]);

return 0;
}
```

-1

ljt12138 LV 10 @ 2016-07-23 14:50:06

又一次手残致wa。。。。
构反图dfs找到所有能到达n的点集P；
再正向spfa求1到达i(i属于P)所经过的最小价值dis[i]
最后枚举每个点做为卖出点，最大化money[i]-disi

题解

38 条题解

最优贸易

信息

状态

开发

支持

题解

38 条题解

最优贸易

信息

状态

开发

支持

还没有账户？

登录