Uva 11324 The Largest Clique【强连通 DAG动规 spfa】

白书上的例题

做一遍tarjan后，缩点，每一个scc节点的权为它的结点数，做一次DAG上的动规，求出路径上的最大点权和，就可以了

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<stack>

 #include<vector>

 using namespace std;

 const int maxn = ;

 int n,m;

 int first[maxn];

 int sc[maxn],scn[maxn],low[maxn],pre[maxn];

 int scnt,ecnt,dfs_clock;

 int dp[maxn];

 int first1[maxn];

 int ecnt1;

 struct Edge{

     int v,next;

 }e[maxn*];

 Edge e1[maxn*];

 stack<int> S;

 void init(){

     ecnt = ecnt1 = ;

     memset(first,-,sizeof(first));

     memset(first1,-,sizeof(first1));

     memset(dp,,sizeof(dp));

 }

 void addedges(int u,int v){

     e[ecnt].v = v;

     e[ecnt].next = first[u];

     first[u] = ecnt++;

 }

 void addedges1(int u,int v){

     e1[ecnt1].v = v;

     e1[ecnt1].next = first1[u];

     first1[u] = ecnt1++;

 }

 void dfs(int u){

     low[u] = pre[u] = ++dfs_clock;

     S.push(u);

     for(int i = first[u];~i;i = e[i].next){

         int v = e[i].v;

         if(!pre[v]){

             dfs(v);

             low[u] = min(low[u],low[v]);

         }

         else if(!sc[v]) low[u] = min(low[u],pre[v]);

     }

     if(pre[u] == low[u]){

         scnt++;

         for(;;){

             int x = S.top();S.pop();

             sc[x] = scnt;

             scn[scnt]++;

             if(x == u) break;

         }

     }

 }

 void find_scc(){

     while(!S.empty()) S.pop();

     scnt = dfs_clock = ;

     memset(low,,sizeof(low));memset(pre,,sizeof(pre));

     memset(sc,,sizeof(sc));memset(scn,,sizeof(scn));

     for(int i = ;i <= n;i++) if(!pre[i]) dfs(i);

 }

 int solve(int p){

     if(dp[p]) return dp[p];

     for(int i = first1[p];~i;i = e1[i].next){

         int v = e1[i].v;

         dp[p] = max(dp[p],solve(v));

     }

     return dp[p] = dp[p] + scn[p];

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         init();

         scanf("%d %d",&n,&m);

         for(int i = ;i < m;i++ ){

             int u,v;

             scanf("%d %d",&u,&v);

             addedges(u,v);

         }

         find_scc();

         for(int u = ;u <= n;u++){

             for(int i = first[u];~i;i = e[i].next){

                 int v = e[i].v;

                 if(sc[u] != sc[v]) addedges1(sc[u],sc[v]);

             }

         }

         int ans = ;

         for(int i = ;i <= scnt;i++) ans = max(ans,solve(i));

         printf("%d\n",ans);

     }

     return ;

 }

还有另一种做法是，建立一个超级源点，与入度为0的scc节点连接，做一次spfa,求出路径上的最大点权和

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<stack>

 #include<vector>

 #include<queue>

 using namespace std;

 const int maxn = ;

 const int INF = ;

 int n,m;

 int first[maxn];

 int sc[maxn],scn[maxn],low[maxn],pre[maxn];

 int scnt,ecnt,dfs_clock;

 int dp[maxn];

 int du[maxn];

 int dis[maxn];

 int inq[maxn];

 int first1[maxn];

 int ecnt1;

 struct Edge{

     int v,next;

 }e[maxn*];

 Edge e1[maxn*];

 stack<int> S;

 vector<int> g[maxn];

 int val[maxn];

 void init(){

     ecnt = ecnt1 = ;

     memset(first,-,sizeof(first));

     memset(val,,sizeof(val));

     memset(du,,sizeof(du));

 }

 void addedges(int u,int v){

     e[ecnt].v = v;

     e[ecnt].next = first[u];

     first[u] = ecnt++;

 }

 void dfs(int u){

     low[u] = pre[u] = ++dfs_clock;

     S.push(u);

     for(int i = first[u];~i;i = e[i].next){

         int v = e[i].v;

         if(!pre[v]){

             dfs(v);

             low[u] = min(low[u],low[v]);

         }

         else if(!sc[v]) low[u] = min(low[u],pre[v]);

     }

     if(pre[u] == low[u]){

         scnt++;

         for(;;){

             int x = S.top();S.pop();

             sc[x] = scnt;

             val[scnt]++;

             if(x == u) break;

         }

     }

 }

 void find_scc(){

     while(!S.empty()) S.pop();

     scnt = dfs_clock = ;

     memset(low,,sizeof(low));memset(pre,,sizeof(pre));

     memset(sc,,sizeof(sc));memset(scn,,sizeof(scn));

     for(int i = ;i <= n;i++) if(!pre[i]) dfs(i);

 }

 int spfa(){

     memset(inq, , sizeof(inq));

     queue<int>q;

     g[].clear();

     q.push();

     dis[] = ; val[] = ;

     for(int i = ; i <= scnt; i++){if(du[i] == )g[].push_back(i); dis[i] = -INF;}

     int ans = ;

     while(!q.empty()){

         int u = q.front(); q.pop(); inq[u] = ;

         for(int i = ; i < g[u].size(); i++){

             int v = g[u][i];

             if(dis[v] < dis[u] + val[v]){

                 dis[v] = dis[u] + val[v];

                 ans = max(ans, dis[v]);

                 if(inq[v] == )inq[v] = , q.push(v);

             }

         }

     }

     return ans;

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         init();

         scanf("%d %d",&n,&m);

         for(int i = ;i < m;i++ ){

             int u,v;

             scanf("%d %d",&u,&v);

             addedges(u,v);

         }

         find_scc();

         for(int i = ;i <= scnt;i++) g[i].clear();

         for(int u = ;u <= n;u++){

             for(int i = first[u];~i;i = e[i].next){

                 int v = e[i].v;

                 if(sc[u] != sc[v]) g[sc[u]].push_back(sc[v]),du[sc[v]]++;

             }

         }

         printf("%d\n",spfa());

     }

     return ;

 }