首页 > > 程序设计 > C/C++ >

P3387 【模板】缩点

2018-06-17 22:02:53来源：未知阅读 ()

题目背景

缩点+DP

题目描述

给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入输出格式

输入格式：

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

输出格式：

共一行，最大的点权之和。

输入输出样例

输入样例#1：

输出样例#1：

说明

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 }