讨论 / 新手也来发个题解……
lx865712528 2014-03-11 07:58:02
点我顶贴 收藏 删除
新手也来发个题解……

Tarjan缩强连通分量+拓扑序dp

对缩点后的连通分量保存各分量内最大和最小值

测试点1 Accepted / 61ms / 11580kB

测试点2 Accepted / 65ms / 11580kB

测试点3 Accepted / 69ms / 11580kB

测试点4 Accepted / 183ms / 12768kB

测试点5 Accepted / 242ms / 13032kB

测试点6 Accepted / 71ms / 11580kB

测试点7 Accepted / 78ms / 11580kB

测试点8 Accepted / 121ms / 12088kB

测试点9 Accepted / 218ms / 13300kB

测试点10 Accepted / 196ms / 13284kB

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

}

查看更多回复
提交回复