poi2012 festival

强连通分量+最长路

#include<cstdio>
#include<cstring>
const int maxi=100000000;
int ft[610][610];
bool f[100001],can[100001];
int head[100001],next[200001],d[100001];
int dfn[100001],low[100001],sta[100001],g[100001];
int top=0,s=0,sum=0,ss=0,n,m1,m2,ans=0;
struct re{
    int u,v,w;
} a[200001];
inline int min(int a,int b){return a<b? a:b;}
inline int max(int a,int b){return a>b? a:b;}
inline int abs(int x){return x>=0? x:-x;}
void done(int i){
    ++s;
    while (sta[top]!=i){
        g[sta[top]]=s;
        can[sta[top]]=false;
        top--;
    }
    g[i]=s;
    can[i]=false;
    top--;
}
void dfs(int i){
    dfn[i]=low[i]=++ss;
    sta[++top]=i;
    f[i]=false;
    for (int j=head[i];j;j=next[j]){
        int k=a[j].v;
        if (can[k]){
            if (f[k]) dfs(k);
            low[i]=min(low[i],min(low[k],dfn[k]));
        }
    }
    if (low[i]==dfn[i]) done(i);
}
void build(int u,int v,int w){
    a[++sum].u=u;
    a[sum].v=v;
    a[sum].w=w;
    next[sum]=head[u];
    head[u]=sum;
}
int main(){
    //freopen("fes11a.in","r",stdin);
    scanf("%d%d%d",&n,&m1,&m2);
    int u,v;
    for (int i=1;i<=m1;i++){
        scanf("%d%d",&u,&v);
        build(v,u,1);
        build(u,v,-1);
    }
    for (int i=1;i<=m2;i++){
        scanf("%d%d",&u,&v);
        build(v,u,0);
    }
    memset(f,true,sizeof(f));
    memset(can,true,sizeof(can));
    for (int i=1;i<=n;i++){
        if (f[i])dfs(i);
    }
    //for (int i=1;i<=n;i++) printf("g[%d]=%d\n",i,g[i]);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            ft[i][j]=-maxi;
        }
    }
    //printf("%d\n",ft[1][1]);
    for (int i=1;i<=n;i++) ft[i][i]=0;
    for (int i=1;i<=sum;i++){
        if (g[a[i].u]==g[a[i].v]){
            ft[a[i].u][a[i].v]=max(ft[a[i].u][a[i].v],a[i].w);
        }
    }
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            printf("f[%d][%d]=%d ",i,j,ft[i][j]);
        }
        printf("\n");
    }*/
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                //if (i==j) printf("i=%d j=%d k=%d f2=%d f3=%d\n",i,j,k,ft[i][k],ft[k][j]);
                ft[i][j]=max(ft[i][j],ft[i][k]+ft[k][j]);
            }
        }
    }
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            printf("f[%d][%d]=%d ",i,j,ft[i][j]);
        }
        printf("\n");
    }*/
    for (int i=1;i<=n;i++){
        if (ft[i][i]>0){
            printf("NIE\n");
            return 0;
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (g[i]==g[j]) d[g[i]]=max(d[g[i]],abs(ft[i][j]));
        }
    }
    for (int i=1;i<=s;i++){
        ans+=d[i]+1;
    }
    printf("%d\n",ans);
}