bzoj1093: [ZJOI2007]最大半连通子图

动态规划.

首先，如果一个强连通分量的一个点在子图里，这个强连通分量所有点都在子图。所以先用tarjan算法求出强连通分量，缩点，当成一个点来处理。然后进行俩次动态规划就行了，注意判重边。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
set<pair<int,int> > edge;
const int maxn = 100000 + 10;
const int maxm = 1000000 + 10;

int g[maxn],next[maxm],v[maxm],eid,in[maxn];
int _g[maxn],_next[maxm],_v[maxm],_eid;
int s[maxn],dfn[maxn],low[maxn],vid,sp=10;
int n,m,mod,res1,res2;
int color[maxn],size[maxn],cid;
int len[maxn],cnt[maxn];
bool vis[maxn];

void _addedge(int a,int b) {
    _v[_eid]=b; _next[_eid]=_g[a]; _g[a]=_eid++;
}

void addedge(int a,int b) {
    v[eid]=b; next[eid]=g[a]; g[a]=eid++; in[b]++;
}

void tarjan(int u) {
    dfn[u]=low[u]=++vid; //dfn表示访问时间，low为访问到的low[_v[i]]的最小值 
    s[++sp]=u;
    vis[u]=1;
    
    for(int i=_g[u];i+1;i=_next[i]) {
        if(dfn[_v[i]]==0) {
            tarjan(_v[i]);
            low[u]=min(low[u],low[_v[i]]);
        }
        else if(vis[_v[i]]==1) {
            low[u]=min(low[u],dfn[_v[i]]);
        }
    }
        
        if(dfn[u]==low[u]) {
            ++cid;
            do{
                color[s[sp]]=cid;
                size[cid]++;
                vis[s[sp]]=0;
            }while(s[sp--]!=u);
        }

}

void dp1(int u) {
    vis[u]=1;
    for(int i=g[u];~i;i=next[i]) {
        if(!vis[v[i]]) dp1(v[i]);
        len[u]=max(len[u],len[v[i]]);
    }
    len[u]+=size[u];
}

void dp2(int u) {
    vis[u]=1;
    for(int i=g[u];~i;i=next[i]) {
        if(!vis[v[i]]) dp2(v[i]);
        if(len[u]==size[u]+len[v[i]]) cnt[u]=(cnt[u]+cnt[v[i]])%mod;
    }
    if(g[u]==-1) cnt[u]=1;
    if(len[u]==res1) res2=(res2+cnt[u])%mod;
}

int main() {
  memset(g,-1,sizeof(g));
  memset(_g,-1,sizeof(_g));
  
  scanf("%d%d%d",&n,&m,&mod);
  for(int i=1,u,v;i<=m;i++) {
      scanf("%d%d",&u,&v);
      _addedge(u,v);
  }
  /*printf("
");
  for(int u=1;u<=n;u++) {
      printf("%d
",u);
      for(int j=_g[u];~j;j=_next[j]) printf("%d ",_v[j]);
      printf("
");
  }*/ 
  
  for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
      
  for(int u=1;u<=n;u++)
  for(int i=_g[u],U,V;~i;i=_next[i]) {
    U=color[u],V=color[_v[i]];
    if(U!=V && edge.find(make_pair(U,V))==edge.end()) {
      edge.insert(make_pair(U,V));
      addedge(U,V);
    }
  }
  memset(vis,0,sizeof(vis));
  for(int u=1;u<=n;u++) if(!in[u]) dp1(u),res1=max(res1,len[u]);
  memset(vis,0,sizeof(vis));
  for(int u=1;u<=n;u++) if(!in[u]) dp2(u);
  
  printf("%d
%d
",res1,res2);
  return 0;  
}