首页 > 代码库 > [NOIP2009提高组]最优贸易 tarjan题解
[NOIP2009提高组]最优贸易 tarjan题解
今天刚刚学会了用tarjan写缩点（以前用两遍dfs写的），此题调了我很久，需要考虑的情况有些多，但是做出来还是挺开心的。
首先通过tarjan缩点，之后要干的事情就是计算答案。
答案有两种情况，一是在一个联通块中买进卖出，二是在一个联通块中买入，但在另外一个联通块中卖出。但是需要注意的是，以上两种情况中的联通块需要满足起点可以到达它，它也可以到达终点，并且不在一个联通块中时，买进必在卖出前。
代码中的dp(x)记录的是从起点到现在买进价最低的，每次只要用当前最大价钱减去这个值，再去和ans做比较，就是第二种情况，而第一种情况还是非常好写的。
下面是我的代码，请无视那么多的注释（调试信息）
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 using namespace std; 5 const int maxn=100005; 6 const int maxm=1000005; 7 int dfn[maxn],low[maxn],st[maxn]; 8 bool instack[maxn]; 9 int now; 10 int n,m; 11 int cnt; 12 int to[maxm],next[maxm],head[maxn]; 13 int dp[maxn]; 14 int col[maxn]; 15 int small[maxn],big[maxn]; 16 int val[maxn]; 17 int p[maxn]; 18 int u[maxm],h[maxm]; 19 int color; 20 int tim=0; 21 int vis[maxn]; 22 void add(int x,int y) 23 { 24 cnt++; 25 to[cnt]=y; 26 next[cnt]=head[x]; 27 head[x]=cnt; 28 } 29 vector <int >v[maxn],all; 30 vector <int > g[maxn]; 31 void tarjan(int x) 32 { 33 dfn[x]=low[x]=++tim; 34 st[++now]=x; 35 instack[x]=true; 36 for(int i=head[x];i;i=next[i]) 37 { 38 if(!dfn[to[i]]) 39 { 40 tarjan(to[i]); 41 low[x]=min(low[x],low[to[i]]); 42 } 43 else if(instack[to[i]]) 44 { 45 low[x]=min(low[x],dfn[to[i]]); 46 } 47 } 48 // cout<<x<<" "<<low[x]<<" "<<dfn[x]<<endl; 49 if(low[x]==dfn[x]) 50 { 51 // cout<<x<<endl; 52 color++; 53 int j=-1; 54 small[color]=19991231; 55 do 56 { 57 j=st[now--]; 58 big[color]=max(big[color],val[j]); 59 small[color]=min(small[color],val[j]); 60 instack[j]=false; 61 col[j]=color; 62 }while(x!=j); 63 } 64 } 65 int out[maxn]; 66 int ans; 67 int ss[maxn]; 68 void dfs(int x) 69 { 70 // cout<<x<<endl; 71 vis[x]=true; 72 for(int i=0;i<g[x].size();i++) 73 { 74 //cout<<x<<" "<<g[x][i]<<endl; 75 if(!vis[g[x][i]]) 76 { 77 dfs(g[x][i]); 78 } 79 } 80 } 81 void dfss(int x) 82 { 83 ss[x]=true; 84 for(int i=0;i<v[x].size();i++) 85 { 86 //cout<<x<<" "<<g[x][i]<<endl; 87 if(!ss[v[x][i]]) 88 { 89 dfss(v[x][i]); 90 } 91 } 92 } 93 int solve(int x) 94 { 95 //cout<<x<<" "; 96 if(dp[x])return dp[x]; 97 dp[x]=small[x]; 98 //cout<<x<<" "<<dp[x]<<endl; 99 for(int i=0;i<v[x].size();i++)100 {101 //cout<<x<<" "<<v[x][i]<<endl;102 if(!vis[v[x][i]] || !ss[v[x][i]] )continue;103 if(v[x][i]==x)continue;104 // cout<<dp[x]<<endl;105 dp[x]=min(dp[x],solve(v[x][i]));106 // cout<<v[x][i]<<" "<<dp[x]<<" "<<solvedp[v[x][i]]<<endl;107 }108 // cout<<x<<" "<<dp[x]<<endl;109 // cout<<x<<" "<<dp[x]<<" "<<big[x]<<endl;110 if(big[x]-dp[x]>ans)ans=big[x]-dp[x];111 //cout<<x<<" "<<ans<<endl;112 return dp[x];113 }114 int main()115 {116 scanf("%d%d",&n,&m);117 for(int i=1;i<=n;i++)scanf("%d",&val[i]);118 for(int i=1;i<=m;i++)119 {120 int x,y,z;121 scanf("%d%d%d",&x,&y,&z);122 add(x,y);123 if(z!=1)add(y,x);124 u[i]=x;125 h[i]=y;126 }127 // cout<<endl;128 129 for(int i=1;i<=n;i++)130 {131 if(!dfn[i])132 {133 tarjan(i);134 }135 }136 // cout<<col[1]<<endl;137 for(int i=1;i<=m;i++)138 {139 if(col[u[i]]!=col[h[i]])140 {141 // cout<<col[u[i]]<<" "<<col[h[i]]<<endl;142 v[col[h[i]]].push_back(col[u[i]]);143 g[col[u[i]]].push_back(col[h[i]]);144 }145 }146 // cout<<col[5]<<endl;147 // cout<<color<<endl;148 //for(int i=1;i<=n;i++)cout<<i<<" "<<col[i]<<endl;149 //for(int i=1;i<=color;i++)cout<<big[i]<<" "<<small[i]<<endl;150 dfs(col[1]);151 dfss(col[n]);152 // for(int i=1;i<=color;i++)cout<<i<<" "<<vis[i]<<endl;153 // cout<<ans<<endl;154 // cout<<color<<endl;155 int tmp=solve(col[n]);156 // cout<<ans<<endl;157 for(int i=1;i<=color;i++)158 {159 if(vis[i] && ss[i])ans=max(ans,big[i]-small[i]);160 // cout<<big[i]-small[i]<<endl;161 //cout<<vis[i]<<" "<<big[i]<<" "<<small[i]<<endl;162 }163 if(!vis[col[n]] || !ss[col[1]])ans=0;164 // cout<<vis[col[n]];165 printf("%d\n",ans);166 return 0;167 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。