题解 P3387 【【模板】缩点】

封癫 · 2017-08-04 17:09:29 · 题解

Tarjan缩点啊

我的方法是缩完点之后，把每个点的颜色当成编号，重新建一个新图。然后在新图上跑DFS

可以有DP、拓扑排序等等妙不可言的做法

具体解释为什么缩点什么的在这里

代码如下

#include<cstdio>
#include<cctype>
#include<cstdlib>

inline long long read(){
   long long num=0,f=1;
   char ch=getchar();
   while(!isdigit(ch)){
       if(ch=='-')f=-1;
       ch=getchar();
   }
   while(isdigit(ch)){
       num=num\*10+ch-'0';
       ch=getchar();
   }
   return num\*f;
}

struct Edge{
   int next,to;
};
struct Pic{
   Edge edge[200000];
   int head[100000],num;
   inline void add(int from,int to){
       edge[++num]=(Edge){head[from],to};
       head[from]=num;
   }
}Old,New;
int ans;
int     f[150000];
int   val[150000];
int   que[150000];
int   dfn[150000];
int   low[150000];
int   col[150000];
bool  vis[150000];
int stack[150000];
int ID,top,cnt;
void tarjan(int x){
   dfn[x]=low[x]=++ID;
   vis[x]=1;
   stack[++top]=x;
   for(int i=Old.head[x];i;i=Old.edge[i].next){
       int to=Old.edge[i].to;
       if(!dfn[to]){
           tarjan(to);
           low[x]=low[x]<low[to]?low[x]:low[to];
       }
       else if(vis[to])    low[x]=low[x]<dfn[to]?low[x]:dfn[to];
   }
   if(low[x]==dfn[x]){
       vis[x]=0;
       col[x]=++cnt;
       val[cnt]+=que[x];
       while(stack[top]!=x){
          col[stack[top--]]=cnt;
          val[cnt]+=que[stack[top+1]];
          vis[stack[top+1]]=0;
      }
      top--;
      }
}

int dfs(int x){
   if(f[x])return f[x];
   f[x]=val[x];
   int maxx=0;
   for(int i=New.head[x];i;i=New.edge[i].next){
       int to=New.edge[i].to;
       if(!f[to])dfs(to);
       maxx=maxx>f[to]?maxx:f[to];
   }
   f[x]+=maxx;
   return f[x];
}

int main(){
   int n=read(),m=read();
   for(int i=1;i<=n;++i)que[i]=read();
   int from,to;
   for(int i=1;i<=m;++i){
       from=read();to=read();
       Old.add(from,to);
   }
   for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
   for(int i=1;i<=n;++i){
       for(int j=Old.head[i];j;j=Old.edge[j].next)    if(col[i]!=col[Old.edge[j].to])    New.add(col[i],col[Old.edge[j].to]);
   }
   for(int i=1;i<=cnt;++i)
       if(!f[i]){
           dfs(i);
           ans=ans>f[i]?ans:f[i];
       }
   printf("%d",ans);
}