题解 - Vijos

4

ToSoul LV 5 @ 2017-09-11 21:58:17

这道题的题意就不多说了，主要说下这里的两个主流做法。

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;
    
}

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

Fellyhosn LV 8 @ 2018-09-09 11:35:22

不带任何高级技巧的搜索+乱搞哈希

适合蒟蒻阅读

First:

我不会链式前向星，但是邻接矩阵肯定会爆，所以用了很神奇的结构体存图

struct point{
    int val;
    int tox;//点的出度
    int to[500];//所连接的点数组
}q[100000];

只存了最多500个点，怕爆空间，可以水过。

Second:

搜索的时候用一个sta变量表示阶段。

通过阅读可得，贸易可以分为三个阶段：

买珠宝、卖珠宝、去终点

由于三个阶段是顺序做的事情，所以可以分别搜索

最后关于判重：乱搞哈希

我搜索时用到的三个变量：现在所在的地点now，拥有的钱money，以及现处阶段sta。于是就乱搞了这个判重语句：

 int hash(int a,int b,int c)
{
    return (a*133%MOD+b*97%MOD+c*17%MOD)%MOD;
}//哈希函数
void dfs(int now,int money,int sta)
{
    int ha=hash(now,money,sta);
    if(HASH[ha]) return ;
    HASH[ha]=true;
    ......
}

#完整AC程序

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct point{
    int val;
    int tox;
    int to[500];
}q[100000];
int i,n,m,ans;
int MOD=9999990;
bool HASH[9999990];//哈希判重

void add(int x,int y)
{
    q[x].tox++;q[x].to[q[x].tox]=y;
}
int has(int a,int b,int c)
{
    return (a*133%MOD+b*97%MOD+c*17%MOD)%MOD;
}
void dfs(int now,int money,int sta)
{
    int j,k;
    int ha=has(now,money,sta);
    if(HASH[ha]) return ;
    HASH[ha]=true;
    if(now==n&&sta==3)
    {
        if(money>ans) ans=money;
        return ;
    }//到达终点
    if(sta==1)
    {
        for(j=1;j<=q[now].tox;j++)
        {
            //在这里买
            dfs(q[now].to[j],q[now].val,2);
            //不在这里买 
            dfs(q[now].to[j],money,1);
        }
    }
    else if(sta==2) //卖 
    {
        for(j=1;j<=q[now].tox;j++)
        {
            //在这里卖 
            if(q[now].val-money>ans) 
            dfs(q[now].to[j],q[now].val-money,3);
            //不卖 
            dfs(q[now].to[j],money,2);
        }
    }
    else
    {
        for(j=1;j<=q[now].tox;j++)
        dfs(q[now].to[j],money,3);
    }//去终点
    return ;
}
int main()
{
    cin>>n>>m;  
    for(i=1;i<=n;i++)
    cin>>q[i].val;
    for(i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y);
        if(z==2) add(y,x); 
    }

    dfs(1,0,1);
    cout<<ans;
}

1

WiFi LV 8 @ 2018-08-23 13:08:43

tarjan缩点成为DAG图，然后记忆化搜索

#include<bits/stdc++.h>
using namespace std;
const int maxn=100004,maxm=500004;
int n,m,cnt=0,dep=0,sum=0;
stack<int>s;
int ans[maxn],dp[maxn][2],price[maxn],head[maxn<<1],dfn[maxn],low[maxn],vis[maxn],col[maxn],maxx[maxn],minn[maxn];
struct node{
    int to,next;
}e[maxm<<2];
void add(int u,int v){
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
void tarjan(int u){
    dfn[u]=low[u]=++dep;
    vis[u]=1;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        col[u]=++sum;vis[u]=0;
        maxx[sum]=minn[sum]=price[u];
        while(1){
            int x=s.top();s.pop();vis[x]=0;
            col[x]=sum;
            maxx[sum]=max(maxx[sum],price[x]);
            minn[sum]=min(minn[sum],price[x]);
            if(x==u) break;
        }
    }
}
void shrink_point(){
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=e[j].next){
            int v=e[j].to;
            if(col[v]==col[i]) continue;
            add(col[v]+n,col[i]+n);
        }
    }
}
void dfs(int u){
    if(dp[u][0]) return;
    dp[u][0]=maxx[u],dp[u][1]=minn[u];
    for(int i=head[u+n];i;i=e[i].next){
        int v=e[i].to;
        v-=n;
        dfs(v);
        ans[u]=max(ans[u],ans[v]);
        dp[u][1]=min(dp[u][1],dp[v][1]);
    }
    ans[u]=max(ans[u],dp[u][0]-dp[u][1]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&price[i]);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(z==1) add(x,y);
        else {add(x,y);add(y,x);}
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    shrink_point();
    dp[col[1]][0]=maxx[col[1]],dp[col[1]][1]=minn[col[1]];
    ans[col[1]]=maxx[col[1]]-minn[col[1]];
    dfs(col[n]);
    printf("%d",ans[col[n]]);
}

1

天神塞勒涅 LV 10 @ 2018-07-06 14:17:42

看了一下题解区。。。没发现用C的，我先来一发~
正向spfa+反向bfs==AC

#define _USE_MATH_DEFINES
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <float.h>
#include <limits.h>
#include <malloc.h>
#include <memory.h>
#include <complex.h>
#include <errno.h>
#include <time.h>
#include <assert.h>
#define Swap(X,Y) ((X)=(X)^(Y),(Y)=(X)^(Y),(X)=(X)^(Y))
#define Max(X,Y) ((X)>(Y) ? (X) : (Y))
#define Min(X,Y) ((X)<(Y) ? (X) : (Y))
#define EPS 1e-7
#define MOD 998244353
#define M 500005
#define N 100005
int n,m,i,a[M],b[M],c[N],e[M],r[N],rr[N],*g[N],*gg[N],d[N<<1],f[N],
    max,op,ed,dis[N];

void spfa(int x)
{
    int i;
    
    memset(dis,127/3,sizeof(dis));
    memset(f,0,sizeof(f));
    op=0; ed=f[x]=1; d[1]=x; dis[x]=c[x];
    while (op!=ed)
    {
        op=op>2*n+1 ? 1 : ++op;
        f[d[op]]=0;
        for (i=1;i<=r[d[op]];i++)
        if (dis[g[d[op]][i]]>dis[d[op]])
        {
            dis[g[d[op]][i]]=Min(dis[d[op]],c[g[d[op]][i]]);
            if (!f[g[d[op]][i]])
            {
                ed=ed>2*n+1 ? 1 : ++ed;
                d[ed]=g[d[op]][i];
                f[d[ed]]=1;
            }
        }
    }
}

void bfs(int x)
{
    int i;
    
    memset(f,0,sizeof(f));
    op=ed=f[x]=1; d[1]=x;
    while (op<=ed)
    {
        for (i=1;i<=rr[d[op]];i++)
        if (!f[gg[d[op]][i]])
        {
            d[++ed]=gg[d[op]][i];
            f[d[ed]]=1;
        }
        op++;
    }
}

int main()
{
    memset(r,0,sizeof(r));
    memset(rr,0,sizeof(rr));
    scanf("%d %d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&c[i]);
    for (i=1;i<=m;i++) 
    {
        scanf("%d %d %d",&a[i],&b[i],&e[i]);
        if (e[i]&1) 
        {
            r[a[i]]++;
            rr[b[i]]++;
        }
        else 
        {
            r[a[i]]++;
            r[b[i]]++;
            rr[a[i]]++;
            rr[b[i]]++;
        }
    }
    for (i=1;i<=n;i++) 
    {
        g[i]=(int *) malloc((r[i]+1)*sizeof(int));
        gg[i]=(int *) malloc((rr[i]+1)*sizeof(int));
    }
    memset(r,0,sizeof(r));
    memset(rr,0,sizeof(rr));
    for (i=1;i<=m;i++) 
    if (e[i]&1) 
    {
        g[a[i]][++r[a[i]]]=b[i];
        gg[b[i]][++rr[b[i]]]=a[i];
    }
    else 
    {
        g[a[i]][++r[a[i]]]=b[i];
        g[b[i]][++r[b[i]]]=a[i];
        gg[a[i]][++rr[a[i]]]=b[i];
        gg[b[i]][++rr[b[i]]]=a[i];
    }
    spfa(1);
    bfs(n);
    for (i=1,max=INT_MIN;i<=ed;i++) max=Max(max,c[d[i]]-dis[d[i]]);
    printf("%d\n",max);
    return 0;
}

May the father of understanding guide U ！

1

paulzrm LV 7 @ 2018-02-10 21:27:58

题目大意：

给你一个图，他又n个点和m条边。这些边可能是双向的也可能是单向的。先在，你要从1号点出发，要你到n号点上去，且不能经过所有点。每个点可以经过多次。现在，由于你知道了每个点上的水晶球的价格是不相同的，所以你要去做一次买卖：在一个点
上买进一个水晶球且在另一个点上卖出那个水晶球。他要求买卖获得的差价最高是多少。

题解思路：

输入的存法：v[i][j]表示第i个点的第j条路线的另外一个端点。
u[i]j表示第j条能到达i号点的路的另外一个端点。

先用一个接近与SPFA和BFS的东西来预处理出从一号点到x号点这条路径上能所买到的水晶球的最低价格，用dis[x]来存。弄完以后，我们有DFS来找：找过的就return,没找过就取做大值max(ans,a[x]-dis[x]);
最后输出ans

程序：
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <set>
#include <queue>
#include <limits>
#include <deque>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <map>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>
#include <cwchar>
#include <cwctype>
#define mp make_pair
#define fs first
#define se second
#define memset(a,t) memset(a,t,sizeof(a))
#define all(v) v.begin(),v.end()
#define eprintf(...) fprintf(stderr, VA_ARGS),fflush(stderr)
#define MN 0LL
#define Mx 200000005
#define Mn -Mx
#define MX 20000000000000005
using namespace std;
int readint(){
char c;
while(c=getchar(),(c<'0'||c>'9')&&c!='-');
bool flag=(c=='-');
if(flag)c=getchar();
int x=0;
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return flag?-x:x;
}
inline string tos(int x){
string s;
while(x) s=(char)(x%10+'0')+s,x/=10;
return s;
}
int n,m;
int a[100005];
vector<int> v[100005];
vector<int> u[100005];
int dis[100005];
queue<int> q;
int ans=0;
bool vd[100005];
inline void dfs(int x){
if(vd[x]) return;
vd[x]=1;
ans=max(ans,(a[x]-dis[x]));
for(int i=0;i<u[x].size();i++){
dfs(u[x][i]);
}
}
int main(){
int i,j,x,y,z,p;
cin>>n>>m;
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<m;i++){
cin>>x>>y>>z;
x--,y--,z--;
v[x].push_back(y);
u[y].push_back(x);
if(z) v[y].push_back(x),u[x].push_back(y);
}
memset(dis,63);
dis[0]=a[0];
q.push(0);
while(!q.empty()){
p=q.front();
q.pop();
dis[p]=min(dis[p],a[p]);
for(i=0;i<v[p].size();i++){
x=v[p][i];
if(dis[x]>dis[p]){
dis[x]=dis[p];
q.push(x);
}
}
}
// for(i=0;i<n;i++) cout<<dis[i]<<' ';
// cout<<endl;
dfs(n-1);
cout<<ans<<endl;
return 0;

}

0

luxiuyuan2002 LV 8 @ 2018-07-06 16:33:13

反向DFS+正向DFS（深搜的点能够达到n）=AC

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct kk{
  int f,t,pre;
}edge1[500010],edge2[500010];
int dist1[100010],dist2[100010],v[100010],num,ans,i,j,z,y,x,m,n,next1[100010],next2[100010];
bool vis1[100010],vis2[100010];
void dfs2(int x)
{
  int i;
  for (i=next2[x];i>0;i=edge2[i].pre)
    {
      if (vis2[edge2[i].t]==false)
        {
          vis2[edge2[i].t]=true;
          dist2[edge2[i].t]=max(v[edge2[i].t],dist2[edge2[i].f]);
          dfs2(edge2[i].t);
        }
    }
}
void dfs1(int x)
{
  int i;
  for (i=next1[x];i>0;i=edge1[i].pre)
    {
      if (vis1[edge1[i].t]==false && vis2[edge2[i].t]==true)
        {
          vis1[edge1[i].t]=true;
          dist1[edge1[i].t]=min(v[edge1[i].t],dist1[edge1[i].f]);
          dfs1(edge1[i].t);
        }
    }
}
int main()
{
  scanf("%d%d",&n,&m);
  num=0;
  ans=0;
  for (i=1;i<=n;++i)
    scanf("%d",&v[i]);
  for (i=1;i<=m;++i)
    {
      scanf("%d%d%d",&x,&y,&z);
      edge1[++num].f=x;
      edge1[num].t=y;
      edge1[num].pre=next1[x];
      next1[x]=num;
      edge2[num].f=y;
      edge2[num].t=x;
      edge2[num].pre=next2[y];
      next2[y]=num;
      if (z==2) 
        {
          edge1[++num].f=y;
          edge1[num].t=x;
          edge1[num].pre=next1[y];
          next1[y]=num;
          edge2[num].f=x;
          edge2[num].t=y;
          edge2[num].pre=next2[x];
          next2[x]=num;
        }
    }
  dist2[n]=v[n];
  dist1[1]=v[1];
  dfs2(n);
  dfs1(1);
  for (i=1;i<=n;++i)
    ans=max(ans,dist2[i]-dist1[i]);
  printf("%d",ans);
}

0

paul20051106 LV 8 @ 2018-02-11 21:58:12

呵呵呵～～想了1小时没想出来，后来无意中看到了SPFA4个字母，就AC了～～！

0

2351599120 LV 9 @ 2017-10-27 16:44:25

SPFA*2

#include <bits/stdc++.h>
using namespace std;
int n,m,ss,maxx,minn=1000,ans=0;
dis[100001]；
diss[100001];
int pri[100001]；
bool used[100001];
struct edge
{
    int u;
    edge *next;
}
e[1000002],*p=e,*point[100001];
struct edge1
{
    int u;
    edge1 *next;
}
e1[1000002],*p1=e1,*point1[100001];
queue<int>q;
inline void add(int x,int y)
{
    p++;
    p->u=y;
    p->next=point[x];
    point[x]=p;
}
inline void add1(int x,int y)
{
    p1++;
    p1->u=y;
    p1->next=point1[x];
    point1[x]=p1;
}
void spfa()
{
    memset(dis,127,sizeof(dis));
    memset(used,0,sizeof(used));
    q.push(ss);
    used[ss]=1;
    while(!q.empty())
    {
        int s=q.front();
        q.pop();
        used[s]=0;
        dis[s]=min(dis[s],pri[s]);
        for(p=point[s];p;p=p->next)
        {
            if(dis[s]<dis[p->u])
            {
                dis[p->u]=dis[s];
                if(!used[p->u])
                {
                    used[p->u]=1;
                    q.push(p->u);
                }
            }
        }
    }
    return;
}
void Spfa()
{
    memset(diss,0,sizeof(diss));
    memset(used,0,sizeof(used));
    q.push(ss);
    used[ss]=1;
    while(!q.empty())
    {
        int s=q.front();
        q.pop();
        used[s]=0;
        diss[s]=max(pri[s],diss[s]);
        for(p1=point1[s];p1;p1=p1->next)
        {
            if(diss[s]>diss[p1->u])
            {
                diss[p1->u]=diss[s];
                if(!used[p1->u])
                {
                    used[p1->u]=1;
                    q.push(p1->u);
                }
            }
        }
    }
    return;
}
int main()
{
//  freopen("trade.in","r",stdin);
//  freopen("trade.out","w",stdout);
    int z,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&pri[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y);
        add1(y,x);
        if(z==2)
        {
            add(y,x);
            add1(x,y);
        }
    }
    ss=1;
    spfa();
    ss=n;
    Spfa();
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,diss[i]-dis[i]);
    }
    printf("%d",ans);
    return 0;
}

0

孤的千年 LV 8 @ 2017-10-24 21:58:49

#include <stdio.h>
#include <algorithm>
#include <stack>
#include <string.h>
using namespace std;

const int MAXN=1e5+5;
const int MAXM=5e5+5;
const int INF=0x7f7f7f7f;

struct Edge{
    int v,next;
}E[MAXM<<1];
int head[MAXN],Ecnt;

int w[MAXN];
int n,m;

void add(int u,int v){
    E[++Ecnt]=(Edge){v,head[u]};head[u]=Ecnt;
}

int low[MAXN],dfn[MAXN],idx;
int in[MAXN];
stack<int>sta;

int MAX[MAXN],MIN[MAXN];
int belong[MAXN];
int Bcnt;

void tarjan(int u){
    low[u]=dfn[u]=++idx;
    in[u]=1;
    int v;
    sta.push(u);
    for(int i=head[u];i;i=E[i].next){
        v=E[i].v;
        if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if(in[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        Bcnt++;
        do{
            v=sta.top();
            sta.pop();
            in[v]=0;
            belong[v]=Bcnt;
            MAX[Bcnt]=max(MAX[Bcnt],w[v]);
            MIN[Bcnt]=min(MIN[Bcnt],w[v]);
        }while(u!=v);
    }
}

int f[MAXM],t[MAXM];
int dp[MAXN];
int ans;

int vis[MAXN];

void dfs(int u){
    if(u==belong[n]) dp[u]=max(dp[u],MAX[u]);
    for(int i=head[u];i;i=E[i].next){
        int v=E[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],MAX[u]);
    ans=max(ans,dp[u]-MIN[u]);
}

void solve(){

    memset(MIN,INF,sizeof MIN);
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }

    Ecnt=0;
    memset(head,0,sizeof head);

    for(int i=1;i<=m;i++){
        int pu=belong[f[i]];
        int pv=belong[t[i]];
        if(pu==pv) continue;
        add(pu,pv);
    }

    vis[belong[1]]=1;
    dfs(belong[1]);
    printf("%d",ans);
}

int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }

    for(int i=1;i<=m;i++){
        int u,v,op;
        scanf("%d%d%d",&u,&v,&op);
        f[i]=u;t[i]=v;
        if(op==1) add(u,v);
        else add(u,v),add(v,u);
    }

    solve();
    return 0;

}

0

chronix LV 8 @ 2016-04-11 18:54:28

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 11892 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 11892 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 11888 KiB, score = 10

测试数据 #3: Accepted, time = 93 ms, mem = 11924 KiB, score = 10

测试数据 #4: Accepted, time = 109 ms, mem = 11988 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 11888 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 11892 KiB, score = 10

测试数据 #7: Accepted, time = 46 ms, mem = 11920 KiB, score = 10

测试数据 #8: Accepted, time = 140 ms, mem = 11996 KiB, score = 10

测试数据 #9: Accepted, time = 109 ms, mem = 11984 KiB, score = 10

Accepted, time = 527 ms, mem = 11996 KiB, score = 100
代码

//正向SPFA 获得最小买入价格
//反向SPFA 获得最大卖出价格

#include <cstdio>
#include <queue>

//#define debug

using std::queue;

struct edge{
int d;
struct edge *link;
};

int top=1,n,m;
int price[100010];
edge graph[100010]={0};
edge graph2[100010]={0};
edge node[500050*2];

void read(int s,int d){
edge *l;
l=&node[top];
l->d=d;
l->link=graph[s].link;
graph[s].link=l;
top++;
}

void read2(int s,int d){
edge *l;
l=&node[top];
l->d=d;
l->link=graph2[s].link;
graph2[s].link=l;
top++;
}

void build(){
scanf("%d%d",&n,&m);
int s,d,z;
for(int i=1;i<=n;i++)
scanf("%d",&price[i]);

for(int i=1;i<=m;i++){
scanf("%d%d%d",&s,&d,&z);
read(s,d);
read2(d,s);
if(z==2){
read(d,s);
read2(s,d);
}
}
}

//SPFA

int inque[100010]={0};
int dist[100010];
queue <int> q;

void spfa(int s){
for(int i=1;i<=n;i++)
dist[i]=9999;
q.push(s);
inque[s]=1;
dist[s]=price[s];
edge *l;
int t;
while(!q.empty()){
t=q.front();
q.pop();
inque[t]=0;
l=graph[t].link;
int minthis;
while(l){
minthis=dist[t]<price[l->d]?dist[t]:price[l->d];
if(minthis<dist[l->d]){
dist[l->d]=minthis;

if(!inque[l->d]){
q.push(l->d);
inque[l->d]=1;
}
}
l=l->link;
}
}
}

int dist2[100010];

void spfa2(int s){
for(int i=1;i<=n;i++)
dist2[i]=-9999;
q.push(s);
inque[s]=1;
dist2[s]=price[s];
edge *l;
int t;
while(!q.empty()){
t=q.front();
q.pop();
inque[t]=0;
l=graph2[t].link;
int maxthis;
while(l){
maxthis=dist2[t]>price[l->d]?dist2[t]:price[l->d];
if(maxthis>dist2[l->d]){
dist2[l->d]=maxthis;

if(!inque[l->d]){
q.push(l->d);
inque[l->d]=1;
}
}
l=l->link;
}
}
}

int calculate(){
int money[100010];
for(int i=1;i<=n;i++)
money[i]=dist2[i]-dist[i];
int maxx=-9999;
for(int i=1;i<=n;i++)
maxx=maxx>money[i]?maxx:money[i];
if(maxx<0)
maxx=0;

return maxx;
}

int main(){
#ifdef debug
freopen("in.txt","r",stdin);
#endif

build();

spfa(1); //正向SPFA

spfa2(n); //反向SPFA

printf("%d",calculate());

return 0;
}

0

starli LV 10 @ 2015-11-05 14:55:09

加边的时候存一张反图，从n开始dfs 把所有能够到达n的点打上标记
然后从1开始spfa 用dis[i]表示到达i点之前可能获得的最小价格水晶球然后SPFA搞一搞
最后扫一遍所有打过标记的点 ans=max(ans,v[i]-dis[i]) (i点可以到达n) 注意不要忘了判断能否到达n表示被坑好多次

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N=100010,INF=2099999999;
int e[N*10],pre[N*10],now[N],tail,n,m,x,y,z,v[N],inq[N],dis[N],ans,e2[N*10],pre2[N*10],now2[N],tail2,vis[N];//dis[i]表示到城市i前可以获得的最小价值的水晶球

void add(int u,int v){e[++tail]=v;pre[tail]=now[u];now[u]=tail;}
void add2(int u,int v){e2[++tail2]=v;pre2[tail2]=now2[u];now2[u]=tail2;}

void dfs(int a){
if(vis[a])return;vis[a]=true;
for(int i=now2[a];i;i=pre2[i]) dfs(e2[i]);
}

int main(){
freopen("1754.in","r",stdin);freopen("1754.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]),dis[i]=INF;
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&x,&y,&z);
if(z==1) add(x,y),add2(y,x);else add(x,y),add2(y,x),add(y,x),add2(x,y);
}
dfs(n);
queue<int> q;
q.push(1);inq[1]=true;dis[1]=v[1];
while(!q.empty()){
int x=q.front();q.pop();inq[x]=false;
for(int i=now[x];i;i=pre[i]){
if(dis[x] < dis[e[i]] || v[e[i]]<dis[e[i]]){
dis[e[i]]=min(dis[e[i]],v[e[i]]);
dis[e[i]]=min(dis[e[i]],dis[x]);
if(!inq[e[i]]) {
q.push(e[i]);inq[e[i]]=true;
}
}
}
}
for(int i=1;i<=n;i++) if(vis[i]) ans=max(ans,v[i]-dis[i]);
printf("%d",ans);
return 0;
}

0

yql LV 8 @ 2015-10-02 15:31:59

反向BFS去掉不能到达的点，正向SPFA记录每个点，以这个点为卖出的话，能够买入的最小钱，即来的路上的最小价格。时间是O（n）的

0

尘世美 LV 8 @ 2015-09-30 20:53:02

/*

Author : Slience_K
Belong : C++
Pro : NOIP 2009 - 3

*/
#include <cstdio>
#include <vector>
#include <algorithm>
#define sz 100005
using namespace std;
int n , m , u , v , w , ans;
int maxn[ sz ] , minn[ sz ] , p[ sz ];
vector <int> map[ sz ];
vector <int> pic[ sz ];
void Dfs1( int x , int k ){
minn[ x ] = min( minn[ x ] , k );
for( int i = 0 ; i < map[ x ].size() ; i++ ){
int v = map[ x ][ i ];
if ( minn[ v ] > k ) Dfs1( v , min( k , p[ v ] ) );
}
}
void Dfs2( int x , int k ){
maxn[ x ] = max( maxn[ x ] , k );
for( int i = 0 ; i < pic[ x ].size() ; i++ ){
int v = pic[ x ][ i ];
if ( maxn[ v ] < k ) Dfs2( v , max( k , p[ v ] ) );
}
}
int main(){
// freopen( "trade.in" , "r" , stdin );
// freopen( "trade.out" , "w" ,stdout );
scanf( "%d%d" , &n , &m );
for( int i = 1 ; i <= n ; i++ )
scanf( "%d" , &p[ i ] );
for( int i = 1 ; i <= m ; i++ ){
scanf( "%d%d%d" , &u , &v , &w );
map[ u ].push_back( v );
pic[ v ].push_back( u );
if ( w == 2 ){
map[ v ].push_back( u );
pic[ u ].push_back( v );
}
}
for( int i = 1 ; i <= n ; i++ )
maxn[ i ] = -sz , minn[ i ] = sz;
Dfs1( 1 , p[ 1 ] );
Dfs2( n , p[ n ] );
ans = 0;
for( int i = 1 ; i <= n ; i++ )
if (( minn[ i ] != sz )&&( maxn[ i ] != -sz )) ans = max( ans , maxn[ i ] - minn[ i ] );
printf( "%d" , ans );
// fclose( stdin );
// fclose( stdout );
return 0;
}

尘世美 @ 2015-09-30 20:54:19

好像不到60行，但都是好慢啊。。。
yql @ 2015-10-02 15:29:19

表示用DFS不怕萎吗

0

Clare LV 8 @ 2015-09-27 17:28:16

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 16416 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 16420 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 16420 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 16428 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 16512 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 16416 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 16420 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 16428 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 16520 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 16496 KiB, score = 10
Accepted, time = 106 ms, mem = 16520 KiB, score = 100

spfa维护到i时Min[i]最小值,Ans[i]最大值

Clare @ 2015-09-27 17:29:33

就只有90行，看下面都醉了
Yolla @ 2015-11-02 10:15:52

有没有代码

0

wang_yanheng LV 10 @ 2015-08-14 21:39:46

用强联通分量+拓扑排序+dp AC，不过有180行

测试数据 #0: Accepted, time = 0 ms, mem = 4792 KiB, score = 10
测试数据 #1: Accepted, time = 4 ms, mem = 4792 KiB, score = 10
测试数据 #2: Accepted, time = 37 ms, mem = 5260 KiB, score = 10
测试数据 #3: Accepted, time = 515 ms, mem = 14180 KiB, score = 10
测试数据 #4: Accepted, time = 500 ms, mem = 14180 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 4828 KiB, score = 10
测试数据 #6: Accepted, time = 65 ms, mem = 5732 KiB, score = 10
测试数据 #7: Accepted, time = 250 ms, mem = 9608 KiB, score = 10
测试数据 #8: Accepted, time = 515 ms, mem = 14664 KiB, score = 10
测试数据 #9: Accepted, time = 468 ms, mem = 14652 KiB, score = 10

时间不太好看，主要是因为用了Kosaraju，在数据量大的情况下2遍dfs是很慢的。改成Tarjan应该快很多。
用链表存边，正反向都要。边界点定义：

typedef struct _node{
int to;
struct _node* next;
} node;

强联通完之后再生成一张新图。由于有正向图、反向图、缩点图共三幅，所以把添加边写成了一个函数，以便重用：

void addEdge(node **G, int from, int to){
node p=G[from];
if(from==to) //请注意：缺少这个判断将造成自环，以致后面的入度计算有误。这是50分和100分的差别。
return;
if(G[from]==NULL){
G[from] = (node)malloc(sizeof(node*));
G[from]->to = to;
G[from]->next = NULL;
}else{
while(p->next != NULL){
if(p->to==to)
return;
p = p->next;
}
if(p->to==to)
return;
p->next = (node*)malloc(sizeof(node*));
p = p->next;
p->to = to;
p->next = NULL;
}
}

在进行强联通分量求解时，需要对反向dfs增加一些步骤（以在行后注明）。使用Tarjan类同。

void dfsReversed(int indexSCC, int index, int size){ //indexSCC指的是这一个强联通分量在全局中是第几个，由主程序传入
node *p = reversedGraph[index];
if(searched[index])
return;
//price数组存储数据输入的每个城市的物价
value[indexSCC] = MAX(value[indexSCC], price[index]); //更新该强联通分量的最大收益
cost[indexSCC] = MIN(cost[indexSCC], price[index]); //更新该强联通分量的最小消耗
searched[index] = 1;
id[index] = indexSCC;
while(p!=NULL){
dfsReversed(indexSCC, p->to, size);
p = p->next;
}
}

生成缩点图并计算入度：

for(i=0; i<numVertex; i++){
p = graph[i];
while(p!=NULL){
addEdge(newGraph, id[i], id[p->to]);
p = p->next;
}
}
for(i=0; i<numSCC; i++){
p = newGraph[i];
while(p!=NULL){
in[p->to]++;
p = p->next;
}
}

最后，拓扑排序+动态规划。这里用到了队列以降低复杂度。把每一个入读为零的点加入队列，一直执行直至队列为空。

for(i=0; i<numSCC; i++)
best[i] = value[i]-cost[i]; //先进行预处理，防止孤立的点产生错误
push(id[0]); //push函数将数据加至队尾
while((i = shift())>=0){ //shift函数返回队头
p = newGraph[i];
in[i] = -1;
while(p!=NULL){
in[p->to]--;
if(in[p->to]==0){
in[p->to] = -1;
push(p->to);
}
/*
接下来两行是重点。首先更新一路走来到达p->to点的最小花费。
best[x]记录x点及之前经过的点出售后获利的最大值。
1. 若之前的点已出售，则 best[x] = best[y]，其中y是x的前继
2. 若之前的点还未出售，则best[x] = value[x]-cost[x]
综合而言， best[x]为1，2情况的最大值
*/
cost[p->to] = MIN(cost[p->to], cost[i]);
best[p->to] = MAX(best[p->to], MAX(best[i], value[p->to]-cost[p->to]));
p = p->next;
}
}

1464942666 @ 2016-07-26 22:21:44

很少有这样负责任的题解了。。。
但是还是要吐槽你的Kosaraju。。。虽然复杂度是一样的。。。

0

nzhtl1477 LV 10 @ 2015-08-03 14:57:53

P1754最优贸易
Accepted

记录信息

评测状态 Accepted
题目 P1754 最优贸易
递交时间 2015-08-03 14:57:12
代码语言 C++
评测机 Jtwd2
消耗时间 1040 ms
消耗内存 9580 KiB
评测时间 2015-08-03 14:57:14

评测结果

编译成功

foo.cpp: In function 'void dfs(point*, int)':
foo.cpp:36:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
foo.cpp: In function 'void dfs2(point*)':
foo.cpp:47:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
foo.cpp: In function 'int main()':
foo.cpp:91:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

测试数据 #0: Accepted, time = 15 ms, mem = 4784 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 4780 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 4900 KiB, score = 10

测试数据 #3: Accepted, time = 124 ms, mem = 6608 KiB, score = 10

测试数据 #4: Accepted, time = 202 ms, mem = 8064 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 4796 KiB, score = 10

测试数据 #6: Accepted, time = 31 ms, mem = 5020 KiB, score = 10

测试数据 #7: Accepted, time = 93 ms, mem = 6344 KiB, score = 10

测试数据 #8: Accepted, time = 265 ms, mem = 9432 KiB, score = 10

测试数据 #9: Accepted, time = 265 ms, mem = 9580 KiB, score = 10

Accepted, time = 1040 ms, mem = 9580 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n , m;
int i;
int x , y;
int s;

struct point
{
vector < point * > link;
vector < point * > link2;
int inprice;
int outprice;
int visit;
int num;
int reach;
};

point line[100000 + 2];
vector < point * > order[100 + 2];

void dfs( point * a , int v )
{
if( !a -> reach )
return;
if( a -> visit )
return;
a -> visit = 1;
a -> inprice = v;
int i;
for( i = 0 ; i < a -> link.size() ; i++ )
dfs( a -> link[i] , v );
return;
}

void dfs2( point * a )
{
if( a -> reach )
return;
a -> reach = 1;
int i;
for( i = 0 ; i < a -> link2.size() ; i++ )
dfs2( a -> link2[i] );
return;
}

int maxd;
int j;

int max( int a , int b )
{
if( a > b )

return a;
return b;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
{
line[i].num = i;
scanf( "%d" , &line[i].outprice );
line[i].inprice = line[i].outprice;
}
for( i = 0 ; i < m ; i++ )
{
scanf( "%d %d %d" , &x , &y , &s );
if( s == 2 )
{
line[x].link.push_back( &line[y] );
line[y].link.push_back( &line[x] );
line[x].link2.push_back( &line[y] );
line[y].link2.push_back( &line[x] );
}
else
{
line[x].link.push_back( &line[y] );
line[y].link2.push_back( &line[x] );
}
}
for( i = 1 ; i <= n ; i++ )
order[ line[i].outprice ].push_back( &line[i] );
dfs2( &line[n] );
for( i = 1 ; i <= 100 ; i++ )
for( j = 0 ; j < order[i].size() ; j++ )
dfs( order[i][j] , i );
for( i = 1 ; i <= n ; i++ )
maxd = max( maxd , line[i].outprice - line[i].inprice );
cout << maxd << endl;
return 0;
}
读题的重要性！

0

liuzikai LV 8 @ 2015-06-21 17:31:59

测试数据 #0: Accepted, time = 0 ms, mem = 5856 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5852 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5848 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 5852 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 5928 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 5852 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 5852 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 5848 KiB, score = 10
测试数据 #8: Accepted, time = 93 ms, mem = 5944 KiB, score = 10
测试数据 #9: Accepted, time = 78 ms, mem = 5920 KiB, score = 10
Accepted, time = 325 ms, mem = 5944 KiB, score = 100

SPFA。
唉...C++党一定要注意用标准输入输出，不然过都过不了...
用数值代替指针的话会快一点。

一次SPFA即可。
f[i]：到第i个城市的最大收益。
b[i]：到第i个城市的最小买入价格。

每次到达一个城市有三个选择：先前到达时的最大收益、在之前经过的城市卖出获得的收益，在先前某个城市买入、该城市卖出的收益，f[TO[e]]=max(f[TO[e]],f[i],w[TO[e]]-b[i])。

如果收益增加了或者买入价格降低了就进行拓展。

最后f[N]就是最大收益。

参考：http://blog.sina.com.cn/s/blog_8442ec3b0100uosn.html

Block Code

#include<climits>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;

int N,M;

int NEXT[500003],TO[500003],V=0;

int w[100003],first[100003];

void add_edge(int n,int t)
{
V++;
TO[V]=t;
NEXT[V]=first[n];
first[n]=V;
}

int f[MAXN],b[MAXN];

queue<int> q;
bool in[MAXN];

int main()
{

scanf("%d%d",&N,&M);

for(int i=1;i<=N;i++)
{
scanf("%d",&w[i]);
first[i]=0;
f[i]=INT_MIN;
b[i]=w[i];
}
for(int i=1;i<=M;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y);
if(z==2) add_edge(y,x);
}

memset(in,false,sizeof(in));
q.push(1);
f[1]=0;
in[1]=true;

while(!q.empty())
{
int i=q.front();
q.pop();
in[i]=false;

int e=first[i];
while(e!=0)
{
bool flag=false;

if(f[TO[e]]<max(f[i],w[TO[e]]-b[i]))
{
f[TO[e]]=max(f[i],w[TO[e]]-b[i]);
flag=true;
}

if(b[TO[e]]>b[i])
{
b[TO[e]]=b[i];
flag=true;
}

if(flag&&!in[TO[e]])
{
q.push(TO[e]);
in[TO[e]]=true;
}
e=NEXT[e];
}
}

printf("%d\n",f[N]);

return 0;
}

0

dkfleet LV 10 @ 2015-01-28 22:17:34

严格O(nlogn+m)的算法.三个DFS.
读边的时候记下它的反向边存好.
第一次DFS,从起点开始,记录哪些节点能从起点到达.
第二次DFS,从终点,使用反向边,记录哪些节点能从终点到达.
把城市按照价值升序排序,开一个数组minv记录"对于所有到达此城市的路径,所能得出的最小购买价格".
从价值小的城市开始对每个城市做DFS,遍历它能达到的所有节点,给minv赋值.
很明显节点的minv有值以后就不再对它做DFS.因此,这n此操作复杂度是O(n+m).
最后统计,城市的minv与售价的差值,取最大输出.

PS:ORZ SPFA的强连通分量缩点的拓扑图DP的都是些啥

测试数据 #0: Accepted, time = 3 ms, mem = 33976 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 33976 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 33976 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 33984 KiB, score = 10

测试数据 #4: Accepted, time = 19 ms, mem = 33976 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 33984 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 33984 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 34104 KiB, score = 10

测试数据 #8: Accepted, time = 46 ms, mem = 34364 KiB, score = 10

测试数据 #9: Accepted, time = 66 ms, mem = 34364 KiB, score = 10

###Block code

const int INF=(1<<30)-1;

struct edge
{
int in;
edge*nxt;
}pool[4005000];
edge*et=pool;
edge*eds[100050];
edge*edp[100050];
void addedge(int i,int j)
{ et->in=j; et->nxt=eds[i]; eds[i]=et++; }
void addrevedge(int i,int j)
{ et->in=j; et->nxt=edp[i]; edp[i]=et++; }
#define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)
#define FOREACH_REV_EDGE(i,j) for(edge*i=edp[j];i;i=i->nxt)

int getint()
{
int res=0;
char c=getchar();
while( c<'0' || '9'<c ) c=getchar();
while( '0'<=c && c<='9' )
{ res=res*10+c-'0'; c=getchar(); }
return res;
}

int v[100050];
int n,m;

int st,ed;

bool rch[100050]; //can this node be reached?

void rchDFS(int x)
{
rch[x]=true;
FOREACH_EDGE(i,x)
if(!rch[i->in]) rchDFS(i->in);
}

bool red[100050]; //can we reach terminal from this node?

void redDFS(int x)
{
red[x]=true;
FOREACH_REV_EDGE(i,x)
if(!red[i->in]) redDFS(i->in);
}

int p[100050];
bool cmp(int a,int b)
{ return v[a]<v[b]; }

int cv;
int minv[100050];
void DFS(int x)
{
minv[x]=cv;
FOREACH_EDGE(i,x)
if(minv[i->in]==INF) DFS(i->in);
}

int main()
{
n=getint();
m=getint();
for(int i=0;i<n;i++)
v[i]=getint();
for(int i=0;i<m;i++)
{
int a=getint();
int b=getint();
int c=getint();
a--,b--;
addedge(a,b);
addrevedge(b,a);
if(c==2) addedge(b,a),addrevedge(a,b);
}

st=0;
ed=n-1;

rchDFS(st);
redDFS(ed);

for(int i=0;i<n;i++)
p[i]=i,minv[i]=INF;
sort(p,p+n,cmp);

for(int i=0;i<n;i++)
if(rch[p[i]] && minv[p[i]]==INF)
{ cv=v[p[i]]; DFS(p[i]); }

int res=0;

for(int i=0;i<n;i++)
if(rch[i] && red[i] && v[i]-minv[i]>res )
res=v[i]-minv[i];

printf("%d\n",res);

return 0;
}

choversky @ 2015-09-07 19:27:52

PS:ORZ SPFA的强连通分量缩点的拓扑图DP的都是些啥
2333我也是笑了呀

0

lx865712528 LV 6 @ 2014-08-08 02:11:19

上次发的观看效果不太好，竟然不能编辑我自己的帖子，只能重发。
Tarjan强连通分量缩点+拓扑序dp
对缩点后的连通分量维护各分量内最大和最小值
测试数据 #0: Accepted, time = 0 ms, mem = 8788 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 8788 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 8880 KiB, score = 10
测试数据 #3: Accepted, time = 140 ms, mem = 10316 KiB, score = 10
测试数据 #4: Accepted, time = 171 ms, mem = 11424 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 8796 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 8932 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 9764 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 11740 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 11720 KiB, score = 10
Accepted, time = 667 ms, mem = 11740 KiB, score = 100
代码如下
###Block code
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
#define MAXN 100010
#define MAXM 1000010
#define INF 0x3f3f3f3f
typedef long long LL;
LL dp[MAXN],f[MAXN],a[MAXN],bin[MAXN],sout[MAXN];
int n,m,bcc[MAXN],dfsno,bccno,s[MAXN],stop,dfn[MAXN],low[MAXN],ind[MAXN];
bool ins[MAXN];
vector<vector<int> > adj(MAXN),map(MAXN);
void tarjan(int u) {
dfn[u]=low[u]=++dfsno;
ins[u]=true;
s[stop++]=u;
for(int i=0;i<adj[u].size();i++) {
int v=adj[u][i];
if(dfn[v]==0) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
bccno++;
while(1) {
int p=s[--stop];
ins[p]=false;
bcc[p]=bccno;
bin[bccno]=min(bin[bccno],a[p]);
sout[bccno]=max(sout[bccno],a[p]);
if(p==u) break;
}
}
}
int main() {
fill(bin,bin+MAXN,INF);
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=0;i<m;i++) {
scanf("%d%d%d",&x,&y,&z);
adj[x].push_back(y);
if(z==2) adj[y].push_back(x);
}
tarjan(1);
for(int u=1;u<=n;u++) {
for(int i=0;i<adj[u].size();i++) {
int v=adj[u][i];
if(bcc[u]!=bcc[v]) {
ind[bcc[v]]++;
map[bcc[u]].push_back(bcc[v]);
}
}
}
queue<int> q;
q.push(bcc[1]);
dp[bcc[1]]=0ll;
f[bcc[1]]=bin[bcc[1]];
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<map[u].size();i++) {
int v=map[u][i];
f[v]=min(f[u],bin[v]);
dp[v]=max(dp[u],sout[v]-f[v]);
ind[v]--;
if(ind[v]==0) q.push(v);
}
}
printf("%lld\n",dp[bcc[n]]);
return 0;
}

0

lx865712528 LV 6 @ 2014-03-11 22:55:37

新手也来发个题解……
Tarjan缩强连通分量+拓扑序dp
对缩点后的连通分量保存各分量内最大和最小值

测试数据 #0: Accepted, time = 0 ms, mem = 8788 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 8788 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 8880 KiB, score = 10
测试数据 #3: Accepted, time = 140 ms, mem = 10316 KiB, score = 10
测试数据 #4: Accepted, time = 171 ms, mem = 11424 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 8796 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 8932 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 9764 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 11740 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 11720 KiB, score = 10
Accepted, time = 667 ms, mem = 11740 KiB, score = 100

#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
#define MAXN 100010
#define MAXM 1000010
#define INF 0x3f3f3f3f
typedef long long LL;
LL dp[MAXN],f[MAXN],a[MAXN],bin[MAXN],sout[MAXN];
int n,m,bcc[MAXN],dfsno,bccno,s[MAXN],stop,dfn[MAXN],low[MAXN],ind[MAXN];
bool ins[MAXN];
vector<vector<int> > adj(MAXN),map(MAXN);
void tarjan(int u) {
dfn[u]=low[u]=++dfsno;
ins[u]=true;
s[stop++]=u;
for(int i=0;i<adj[u].size();i++) {
int v=adj[u][i];
if(dfn[v]==0) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
bccno++;
while(1) {
int p=s[--stop];
ins[p]=false;
bcc[p]=bccno;
bin[bccno]=min(bin[bccno],a[p]);
sout[bccno]=max(sout[bccno],a[p]);
if(p==u) break;
}
}
}
int main() {
fill(bin,bin+MAXN,INF);
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=0;i<m;i++) {
scanf("%d%d%d",&x,&y,&z);
adj[x].push_back(y);
if(z==2) adj[y].push_back(x);
}
tarjan(1);
for(int u=1;u<=n;u++) {
for(int i=0;i<adj[u].size();i++) {
int v=adj[u][i];
if(bcc[u]!=bcc[v]) {
ind[bcc[v]]++;
map[bcc[u]].push_back(bcc[v]);
}
}
}
queue<int> q;
q.push(bcc[1]);
dp[bcc[1]]=0ll;
f[bcc[1]]=bin[bcc[1]];
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<map[u].size();i++) {
int v=map[u][i];
f[v]=min(f[u],bin[v]);
dp[v]=max(dp[u],sout[v]-f[v]);
ind[v]--;
if(ind[v]==0) q.push(v);
}
}
printf("%lld\n",dp[bcc[n]]);
return 0;
}

题解

38 条题解

不带任何高级技巧的搜索+乱搞哈希

适合蒟蒻阅读

First:

我不会链式前向星，但是邻接矩阵肯定会爆，所以用了很神奇的结构体存图

Second:

搜索的时候用一个sta变量表示阶段。

通过阅读可得，贸易可以分为三个阶段：

买珠宝、卖珠宝、去终点

由于三个阶段是顺序做的事情，所以可以分别搜索

最后关于判重：乱搞哈希

我搜索时用到的三个变量：现在所在的地点now，拥有的钱money，以及现处阶段sta。于是就乱搞了这个判重语句：

Block Code

最优贸易

信息

状态

开发

支持

题解

38 条题解

不带任何高级技巧的搜索+乱搞哈希

适合蒟蒻阅读

First:

我不会链式前向星，但是邻接矩阵肯定会爆，所以用了很神奇的结构体存图

Second:

搜索的时候用一个sta变量表示阶段。

通过阅读可得，贸易可以分为三个阶段：

买珠宝、卖珠宝、去终点

由于三个阶段是顺序做的事情，所以可以分别搜索

最后关于判重：乱搞哈希

我搜索时用到的三个变量：现在所在的地点now，拥有的钱money，以及现处阶段sta。于是就乱搞了这个判重语句：

Block Code

最优贸易

信息

状态

开发

支持

还没有账户？

登录