题目背景
缩点+DP
题目描述
给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入输出格式
输入格式：
第一行，n,m
第二行，n个整数，依次代表点权
第三至m+2行，每行两个整数u,v，表示u->v有一条有向边
输出格式：
共一行，最大的点权之和。
输入输出样例
输入样例#1：
2 2
1 1
1 2
2 1
输出样例#1：
2
说明 n<=10^4 ,m <=10^5 ,点权 <= 1000
算法：Tarjan缩点+DAGdp
思路 : 题目的思路很清晰，都有提示，但是我第一次写的时候 WA了一组 ，T了一组
代码如下 :
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 50;
const int maxm = 1e5 + 50;
struct edge {
int nxt ,to ;
}ss[maxm * 10 ];
stack<int>sta ;
int head[maxn] ,dfn[maxn] ,low[maxn] ,w[maxn] ;
int cnt ,Index ,scc ,n ,m ,flag[maxn] ;
int sum[maxn] ,in[maxn] ,dp[maxn] ;
bool vis[maxn] ;
void init() {
memset(head ,-1 ,sizeof(head));
memset(vis ,false ,sizeof(vis));
}
inline int Min(int a,int b) { return a > b ? b : a ; }
inline int Max(int a,int b) { return a > b ? a : b ; }
void add_edge (int u ,int v ){
ss[++cnt].to = v;
ss[cnt].nxt = head[u] ;
head[u] = cnt ;
}
void tarjan(int x) {
dfn[x] = low[x] = ++Index ;
vis[x] = true ; sta.push(x) ;
for (int i = head[x] ; ~i ; i = ss[i].nxt ) {
if ( !dfn[ss[i].to] ) {
tarjan(ss[i].to);
low[x] = Min(low[x] ,low[ss[i].to]) ;
} else if ( vis[ss[i].to] ) {
low[x] = Min(low[x] ,dfn[ss[i].to]) ;
}
}
if ( low[x] == dfn[x] ) {
scc ++;
int v;
do {
v = sta.top() ; sta.pop();
flag[v] = scc ;
} while ( x != v ) ;
}
}
void toposort() {
queue<int >que ;
for (int i = 1 ; i <= scc ; i ++ ) {
if( !in[i] ) {
que.push(i);
dp[i] = sum[i] ;
}
}
// for (int i = 1 ; i <= scc ; i ++ ) {
// if ( !in[i] ) {
// printf("%d %d
",i ,sum[i]) ;
// }
// } puts("") ;
while ( !que.empty() ) {
int top = que.front() ;que.pop();
for (int i = 1 ; i <= n ; i ++ ) {
if ( flag[i] == top ) {
for (int j = head[i] ; ~j ; j = ss[j].nxt ) {
if ( flag[i] != flag[ss[j].to] ) {
que.push(flag[ss[j].to]) ;
dp[flag[ss[j].to]] = Max(dp[flag[ss[j].to]] ,dp[flag[i]] + sum[flag[ss[j].to]]) ;
}
}
}
}
}
}
int main() {
//FILE *fp;
//fp = fopen("in.txt" ,"r") ;
init() ; int u ,v ;
//fscanf(fp, "%d %d" ,&n ,&m ) ;
scanf("%d %d",&n ,&m ) ;
for (int i = 1 ; i <= n ; i ++ ) {
//fscanf(fp ,"%d" ,&w[i] );
scanf("%d",&w[i]);
}
for (int i = 1 ; i <= m ; i ++ ) {
//fscanf(fp ,"%d %d",&u ,&v ) ;
scanf("%d %d" ,&u ,&v ) ;
add_edge(u ,v ) ;
}
for (int i = 1 ; i <= n ; i ++ ) {
if ( !vis[i] ) {
tarjan(i);
}
}
for (int i = 1 ; i <= n ; i ++ ) {
if ( !flag[i] ) flag[i] = ++ scc ;
}
// for (int i = 1 ; i <= n ; i ++ ) {
// printf("%d ",flag[i]) ;
// } puts("");
for (int i = 1 ; i <= n ; i ++ ) {
for (int j = head[i] ; ~j ; j = ss[j].nxt ) {
if ( flag[i] != flag[ss[j].to] ) {
in[flag[ss[j].to]] ++;
}
}
}
for (int i = 1 ; i <= n ; i ++ ) {
sum[flag[i]] += w[i];
}
// for (int i = 1 ; i <= scc ; i ++ ) {
// printf("%d ",sum[i]) ;
// } puts("");
toposort() ;
int maxx = -0x3f3f3f3f ;
for (int i = 1 ; i <= scc ; i ++ ) {
//printf("%d ",dp[i]);
maxx = Max(maxx ,dp[i] ) ;
} //puts("");
printf("%d
",maxx) ;
//fclose(fp) ;
return 0;
}
后来想了想，我的那个入度还能够利用一下，因此改了一下
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 50;
const int maxm = 1e5 + 50;
struct edge {
int nxt ,to ;
}ss[maxm * 10 ];
stack<int>sta ;
int head[maxn] ,dfn[maxn] ,low[maxn] ,w[maxn] ;
int cnt ,Index ,scc ,n ,m ,flag[maxn] ;
int sum[maxn] ,in[maxn] ,dp[maxn] ;
bool vis[maxn] ;
void init() {
memset(head ,-1 ,sizeof(head));
memset(vis ,false ,sizeof(vis));
}
inline int Min(int a,int b) { return a > b ? b : a ; }
inline int Max(int a,int b) { return a > b ? a : b ; }
void add_edge (int u ,int v ){
ss[++cnt].to = v;
ss[cnt].nxt = head[u] ;
head[u] = cnt ;
}
void tarjan(int x) {
dfn[x] = low[x] = ++Index ;
vis[x] = true ; sta.push(x) ;
for (int i = head[x] ; ~i ; i = ss[i].nxt ) {
if ( !dfn[ss[i].to] ) {
tarjan(ss[i].to);
low[x] = Min(low[x] ,low[ss[i].to]) ;
} else if ( vis[ss[i].to] ) {
low[x] = Min(low[x] ,dfn[ss[i].to]) ;
}
}
if ( low[x] == dfn[x] ) {
scc ++;
int v;
do {
v = sta.top() ; sta.pop();
flag[v] = scc ;
} while ( x != v ) ;
}
}
void toposort() {
queue<int >que ;
for (int i = 1 ; i <= scc ; i ++ ) {
if( !in[i] ) {
que.push(i);
dp[i] = sum[i] ;
}
}
while ( !que.empty() ) {
int top = que.front() ; que.pop();
for (int i = 1 ; i <= n ; i ++ ) {
if ( flag[i] == top ) {
for (int j = head[i] ; ~j ; j = ss[j].nxt ) {
if ( flag[i] != flag[ss[j].to] ) {
in[flag[ss[j].to]] -- ;///这一句
if ( !in[flag[ss[j].to]] )///这一句
que.push(flag[ss[j].to]) ;///这一句
dp[flag[ss[j].to]] = Max(dp[flag[ss[j].to]] ,dp[flag[i]] + sum[flag[ss[j].to]]) ;
}
}
}
}
}
}
int main() {
// FILE *fp;
// fp = fopen("in.txt" ,"r") ;
init() ; int u ,v ;
//fscanf(fp, "%d %d" ,&n ,&m ) ;
scanf("%d %d",&n ,&m ) ;
for (int i = 1 ; i <= n ; i ++ ) {
//fscanf(fp ,"%d" ,&w[i] );
scanf("%d",&w[i]);
}
for (int i = 1 ; i <= m ; i ++ ) {
//fscanf(fp ,"%d %d",&u ,&v ) ;
scanf("%d %d" ,&u ,&v ) ;
add_edge(u ,v ) ;
}
for (int i = 1 ; i <= n ; i ++ ) {
if ( !vis[i] ) {
tarjan(i);
}
}
for (int i = 1 ; i <= n ; i ++ ) {
if ( !flag[i] ) flag[i] = ++ scc ;
}
// for (int i = 1 ; i <= n ; i ++ ) {
// printf("%d ",flag[i]) ;
// } puts("");
for (int i = 1 ; i <= n ; i ++ ) {
for (int j = head[i] ; ~j ; j = ss[j].nxt ) {
if ( flag[i] != flag[ss[j].to] ) {
in[flag[ss[j].to]] ++;
}
}
}
for (int i = 1 ; i <= n ; i ++ ) {
sum[flag[i]] += w[i];
}
// for (int i = 1 ; i <= scc ; i ++ ) {
// printf("%d ",sum[i]) ;
// } puts("");
toposort() ;
int maxx = -0x3f3f3f3f ;
for (int i = 1 ; i <= scc ; i ++ ) {
//printf("%d ",dp[i]);
maxx = Max(maxx ,dp[i] ) ;
} //puts("");
printf("%d
",maxx) ;
return 0;
}
然后就卡在里这里，后面不知道了怎么改，在网上找了一个答案，发现跟我的思路差不多，但是我的就是不对，后来通过这两组数据的缩点对比我发现我的tarjan写错了，最后也没有想到解决方法，就万恶的改了一下自己缩点的模板，最后代码是这样的
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 50 ;
struct edge {
int nxt ,u ,v ;
}ss[maxn * 10] ,s[maxn * 10];
int head[maxn] ,dfn[maxn] ,low[maxn] ,pos ;
int n ,m ,cnt ,Index ,h[maxn] ,sta[maxn];
int flag[maxn] ,sum[maxn] ,cnt1 ,in[maxn] ,dp[maxn] ;
bool vis[maxn] ;
inline int Min(int a,int b) { return a > b ? b : a ; }
inline int Max(int a,int b) { return a > b ? a : b ; }
void init(){
cnt1 = pos = cnt = Index = 0;
memset(vis ,false ,sizeof(vis)) ;
memset(head ,-1 ,sizeof(head)) ;
memset(h ,-1 ,sizeof(h)) ;
}
void add_edge(int u,int v) {
ss[++cnt].u = u ;
ss[cnt].v = v;
ss[cnt].nxt = head[u] ;
head[u] = cnt ;
}
void tarjan(int x) {
dfn[x] = low[x] = ++Index ;
vis[x] = true ; sta[++pos] = x;
for (int i = head[x] ; ~i ; i = ss[i].nxt ) {
if ( !dfn[ss[i].v] ) {
tarjan(ss[i].v) ;
low[x] = Min(low[x] ,low[ss[i].v]);
} else if ( vis[ss[i].v] ) {
low[x] = Min(low[x] ,dfn[ss[i].v] ) ;
}
}
if ( low[x] == dfn[x] ) {
int y ;
while ((y = sta[pos--])) {
flag[y] = x;
vis[y] = false;
if ( x == y ) break;
sum[x] += sum[y];
}
}
}
void toposort() {
queue<int >que;
for (int i = 1 ; i <= n ; i ++ ) {
if ( flag[i] == i && !in[i] ) {
que.push(i);
dp[i] = sum[i] ;
}
}
while( !que.empty() ) {
int top = que.front() ; que.pop() ;
for (int i = h[top] ; ~i ; i = s[i].nxt ) {
dp[s[i].v] = Max(dp[s[i].v] ,dp[top] + sum[s[i].v]) ;
in[s[i].v] --;
if ( !in[s[i].v] ) que.push(s[i].v) ;
}
}
}
int main() {
init() ; int u, v ;
scanf("%d %d",&n ,&m ) ;
for (int i = 1 ; i <= n ; i ++ ) {
scanf("%d",&sum[i]);
}
for ( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&u ,&v ) ;
add_edge(u ,v ) ;
}
for (int i = 1 ; i <= n ; i ++ ) {
if ( !dfn[i]) tarjan(i);
}
for (int i = 1 ; i <= m ; i ++ ) {
int x = flag[ss[i].u] ,y = flag[ss[i].v] ;
if ( x != y ) {
s[++cnt1].u = x ;
s[cnt1].v = y ;
s[cnt1].nxt = h[x] ;
h[x] = cnt1;
in[y] ++;
}
}
toposort() ;
int maxx = -0x3f3f3f3f ;
for (int i = 1 ; i <= n ; i ++ ) {
if ( dp[i] > maxx ) maxx = dp[i] ;
}
printf("%d
",maxx );
return 0;
}