Part 1.图论

1.分层图最短路

P3119 [USACO15JAN] Grass Cownoisseur G

主要是需要缩点，分层图最短路就比较板了。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
//要先缩点！ 
int n,m,h[N],e[N],ne[N],idx =1,deg[N],f[N];
int dfn[N],low[N],tmp,q[N],indx,scc[N],tot,num[N],top;
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++tmp;
    q[++top] = u;
    for(int i=h[u],v;i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }else if(!scc[j]){
            low[u] = min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u]){
        ++tot;
        do{
            ++num[scc[q[top]] = tot];
        }while(q[top--]!=u);
    }
}
vector<int>g[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x+n);
        add(x+n,y+n);
    }
    tarjan(1);
    for(int i=1;i<=n*2;i++){
        if(dfn[i]){
            for(int k=h[i];k;k=ne[k]){
                int j=e[k];
                if(scc[i]!=scc[j]){
                    g[scc[i]].push_back(scc[j]),++deg[scc[j]];
                }
            }
        }
    }
    int l=0,r=0;
    for(int i=1;i<=tot;i++){
        if(!deg[i]) q[r++] = i;
        f[i]=-0x3f3f3f3f;
    }
    while(l < r){
        int u= q[l++];
        if(u==scc[1]) f[u]=0;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(!--deg[v]) q[r++] = v;
            f[v] = max(f[v],f[u]+num[v]);
        }
    }
    cout<<f[scc[n+1]];
    return 0;
}