题解 P3119 【[USACO15JAN]草鉴定Grass Cownoisseur】

· · 题解

缩点变DAG，分层图+spfa跑一遍即可出解

正文:

  1. 缩点：可以当做跑spfa的优化吧,虽然必要性还是很大：变DAG后保证第二层图，不再重复第一层图经过点

  2. 分层图：

     1. 将原图写做2个（n为点的个数）
 2. First图：u-->v
    Second图：u+n-->v+n
    Fir->Sec图：v-->u+n(这样就将第一、二层图联系起来了，由于DAG，在Sec图时不会重复加Fir图经过点的点权)

 PS：Sec图同样有点权

  3. spfa:它死了 注意起点变为缩点后1的所在点

Code:

#include<bits/stdc++.h>//分层图 
using namespace std;
const int maxn=2e5+5;
int low[maxn],dfn[maxn],x[maxn],y[maxn],head[maxn<<1],sz[maxn],col[maxn],dis[maxn<<1],n,m,dfs_clock,size,tot;
bool vis[maxn<<1];
struct node{
    int u,v,nxt;
}e[maxn<<1];

int read(){
    int x=0;char a=getchar();
    while(!isdigit(a)) a=getchar();
    while(isdigit(a)) {x=x*10+a-'0';a=getchar();}
    return x;
}

void add(int u,int v){
    e[++size].u=u;
    e[size].v=v;
    e[size].nxt=head[u];
    head[u]=size;
}

stack<int>s;
void tarjan(int u){
    s.push(u);
    dfn[u]=low[u]=++dfs_clock;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!col[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++tot;int k;
        do{
            k=s.top();s.pop();
            col[k]=tot;
            sz[tot]++;//缩点内原点数量，即：点权
        }while(k!=u);
    }
}

queue<int>q;
void spfa(){
    q.push(col[1]);//起点
    for(int i=1;i<=2*tot;++i) dis[i]=0;
    dis[col[1]]=0;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=sz[u];//由于取了1号点，在回到col[1]+tot点时，不再去；所以：每次加上u的点权
            if(dis[v]<dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]) vis[v],q.push(v);
            }
        }
    }
}

void clear(){
    size=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
}

void readda(){
    for(int i=1;i<=m;++i){
        int u=col[x[i]],v=col[y[i]];//新图
        if(u!=v){
            add(u,v);
            add(u+tot,v+tot);
            add(v,u+tot);
        }
    }
    for(int i=1;i<=tot;++i) sz[i+tot]=sz[i];//Sec图也有点权
}

int main(){
    n=read();m=read();
    for(int i=1,a,b;i<=m;++i){
        x[i]=read();y[i]=read();
        add(x[i],y[i]);
    }
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);//缩完点后，tot成为新的总点数
    clear();
    readda();
    spfa();
    printf("%d",dis[col[1]+tot]);//在Sec图上回到1
    return 0;
}

rp++