P3387 【模板】縮點

題目背景

縮點+DP

題目描述

給定一個n個點m條邊有向圖，每個點有一個權值，求一條路徑，使路徑經過的點權值之和最大。你只需要求出這個權值和。

允許多次經過一條邊或者一個點，但是，重覆經過的點，權值只計算一次。

輸入輸出格式

輸入格式：

第一行，n,m

第二行，n個整數，依次代表點權

第三至m+2行，每行兩個整數u,v，表示u->v有一條有向邊

輸出格式：

共一行，最大的點權之和。

輸入輸出樣例

2 2
1 1
1 2
2 1

2

說明

n<=10^4,m<=10^5,|點權|<=1000 演算法：Tarjan縮點+DAGdp

為什麼要DP。。

跑完tarjan跑爆搜不就好了麽。

還有這題貌似要開兩個鄰接表存。

不然會產生衝突(當然也有可能是我太弱了2333)

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<stack>
  6 using namespace std;
  7 const int MAXN=800100;
  8 const int mod=998244353;
  9 inline void read(int &n)
 10 {
 11     char c='+';bool flag=0;n=0;
 12     while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
 13     while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();
 14 }
 15 struct node
 16 {
 17     int u,v,nxt;
 18     void cler()
 19     {u=v=nxt=0;}
 20 }edge[MAXN];
 21 int head[MAXN];
 22 int num=1;
 23 inline void add_edge(int x,int y)
 24 {
 25     edge[num].u=x;
 26     edge[num].v=y;
 27     edge[num].nxt=head[x];
 28     head[x]=num++;
 29 }
 30 struct node2
 31 {
 32     int u,v,nxt;
 33     void cler()
 34     {u=v=nxt=0;}
 35 }edge2[MAXN];
 36 int head2[MAXN];
 37 int num2=1;
 38 inline void add_edge2(int x,int y)
 39 {
 40     edge2[num2].u=x;
 41     edge2[num2].v=y;
 42     edge2[num2].nxt=head2[x];
 43     head2[x]=num2++;
 44 }
 45 int n,m;
 46 int dfn[MAXN];//時間順序
 47 int low[MAXN];
 48 stack<int>s;
 49 int tot=0;//總結點 
 50 int vis[MAXN];
 51 int color[MAXN];
 52 int colornum=0;
 53 int date[MAXN];// 每一個聯通分量里的權值
 54 int a[MAXN]; 
 55 int out;// 最終答案 
 56 int ans;// 當前答案 
 57 int dfs(int now)
 58 {
 59     if(vis[now])    return vis[now];
 60     vis[now]=date[now];
 61     int nowmax=0;
 62     for(int i=head2[now];i!=-1;i=edge2[i].nxt)
 63     {
 64         if(!vis[edge2[i].v])        dfs(edge2[i].v);
 65         nowmax=max(nowmax,vis[edge2[i].v]);
 66     }
 67     vis[now]+=nowmax;
 68     return vis[now];        
 69 }
 70 inline void tarjan(int now)
 71 {
 72     dfn[now]=low[now]=++tot;
 73     vis[now]=1;
 74     s.push(now);
 75     for(int i=head[now];i!=-1;i=edge[i].nxt)
 76     {
 77         if(!dfn[edge[i].v])    tarjan(edge[i].v),    low[now]=min(low[now],low[edge[i].v]);
 78         else if(vis[edge[i].v])    low[now]=min(low[now],dfn[edge[i].v]);
 79     }
 80     if(dfn[now]==low[now])
 81     {
 82         colornum++;
 83         int h;
 84         do
 85         {
 86             h=s.top();
 87             if(!color[s.top()])    color[s.top()]=colornum,date[colornum]+= a[s.top()];
 88             vis[s.top()]=0;    s.pop();
 89         }while(now!=h);
 90     }
 91 }
 92 int main()
 93 {
 94     read(n);read(m);
 95     memset(head,-1,sizeof(head));
 96     memset(head2,-1,sizeof(head2));
 97     for(int i=1;i<=n;i++)    read(a[i]);
 98     for(int i=1;i<=m;i++)
 99     {
100         int x,y;read(x);read(y);
101         add_edge(x,y);
102     }
103     for(int i=1;i<=n;i++)
104         if(!dfn[i])    tarjan(i);
105     
106     for(int i=1;i<=n;i++)
107         for(int j=head[i];j!=-1;j=edge[j].nxt)
108             if(color[i]!=color[edge[j].v])    add_edge2(color[i],color[edge[j].v]);
109     memset(vis,0,sizeof(vis));
110     for(int i=1;i<=colornum;i++)
111     {
112         if(!vis[i])
113             dfs(i),ans=max(ans,vis[i]);
114     }    
115     printf("%d",ans);
116     return 0;
117 }