题解

38 条题解

  • 4
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2018-02-11 21:58:12

    呵呵呵~~想了1小时没想出来,后来无意中看到了SPFA4个字母,就AC了~~!

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2015-10-02 15:31:59

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

  • 0
    @ 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行 ,但都是好慢啊。。。

    • @ 2015-10-02 15:29:19

      表示用DFS不怕萎吗

  • 0
    @ 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]最大值

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

      就只有90行,看下面都醉了

    • @ 2015-11-02 10:15:52

      有没有代码

  • 0
    @ 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;
    }
    }

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

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

  • 0
    @ 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
    @ 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
    @ 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;
    }

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

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

  • 0
    @ 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
    @ 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;
    }

信息

ID
1754
难度
6
分类
图结构 | 最短路 点击显示
标签
递交数
2896
已通过
744
通过率
26%
被复制
6
上传者