hdu1269 迷宫城堡 http://acm.hdu.edu.cn/showproblem.php?pid=1269

 1 #include<cstdio> 2 #include<cstring> 3 #include<stack> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 class Tarjan{///有向图强连通分量缩点 7     static const int ME=100010;///边的个数 8     static const int MV=10010;///点的个数 9     int Index,Bcnt,num[MV],belong[MV],dfn[MV],low[MV];10     bool instack[MV];11     stack<int> s;12     void tarjan(int u) {13         dfn[u]=low[u]=++Index;14         instack[u]=true;15         s.push(u);16         int v;17         for(int i=g.head[u]; ~i; i=g.e[i].next) {18             v=g.e[i].v;19             if(!dfn[v]) {20                 tarjan(v);21                 low[u]=min(low[u],low[v]);22             } else if(instack[v]) {23                 low[u]=min(low[u],dfn[v]);24             }25         }26         if(dfn[u]==low[u]) {27             Bcnt++;28             do {29                 v=s.top();30                 s.pop();31                 instack[v]=false;32                 belong[v]=Bcnt;33                 num[Bcnt]++;34             } while(u!=v);35         }36     }37     struct G {38         struct E {39             int u,v,next;40         } e[ME];41         int le,head[MV];42         void init() {43             le=0;44             mt(head,-1);45         }46         void add(int u,int v) {47             e[le].u=u;48             e[le].v=v;49             e[le].next=head[u];50             head[u]=le++;51         }52     } g;53 public:54     void init() {55         g.init();56         Index=Bcnt=0;57         mt(num,0);58         mt(dfn,0);59         mt(low,0);60         mt(instack,0);61         while(!s.empty()) s.pop();62     }63     void add(int u,int v) {64         g.add(u,v);65     }66     void solve(int n) {///传入点数，点下标1开始67         for(int i=1; i<=n; i++) {68             if(!dfn[i]) {69                 tarjan(i);70             }71         }72     }73     int getbcnt() {///强连通分量的个数74         return Bcnt;75     }76     int getbelong(int id) {///属于哪个分量，分量下标1开始77         return belong[id];78     }79     int getnum(int id) {///某个分量的点的个数80         return num[id];81     }82 }tarjan;83 int main(){84     int n,m,x,y;85     while(~scanf("%d%d",&n,&m),n+m){86         tarjan.init();87         while(m--){88             scanf("%d%d",&x,&y);89             tarjan.add(x,y);90         }91         tarjan.solve(n);92         if(tarjan.getbcnt()==1) puts("Yes");93         else puts("No");94     }95     return 0;96 }

  1 #include<cstdio>  2 #include<cstring>  3 #include<stack>  4 #define mt(a,b) memset(a,b,sizeof(a))  5 using namespace std;  6 class Tarjan{///有向图强连通分量缩点  7     static const int ME=300010;///边的个数  8     static const int MV=100010;///点的个数  9     int Index,Bcnt,num[MV],belong[MV],dfn[MV],low[MV]; 10     bool instack[MV]; 11     stack<int> s; 12     void tarjan(int u) { 13         dfn[u]=low[u]=++Index; 14         instack[u]=true; 15         s.push(u); 16         int v; 17         for(int i=g.head[u]; ~i; i=g.e[i].next) { 18             v=g.e[i].v; 19             if(!dfn[v]) { 20                 tarjan(v); 21                 low[u]=min(low[u],low[v]); 22             } else if(instack[v]) { 23                 low[u]=min(low[u],dfn[v]); 24             } 25         } 26         if(dfn[u]==low[u]) { 27             Bcnt++; 28             do { 29                 v=s.top(); 30                 s.pop(); 31                 instack[v]=false; 32                 belong[v]=Bcnt; 33                 num[Bcnt]++; 34             } while(u!=v); 35         } 36     } 37 public: 38     struct G { 39         struct E { 40             int u,v,next; 41         } e[ME]; 42         int le,head[MV]; 43         void init() { 44             le=0; 45             mt(head,-1); 46         } 47         void add(int u,int v) { 48             e[le].u=u; 49             e[le].v=v; 50             e[le].next=head[u]; 51             head[u]=le++; 52         } 53     } g; 54 public: 55     void init() { 56         g.init(); 57         Index=Bcnt=0; 58         mt(num,0); 59         mt(dfn,0); 60         mt(low,0); 61         mt(instack,0); 62         while(!s.empty()) s.pop(); 63     } 64     void add(int u,int v) { 65         g.add(u,v); 66     } 67     void solve(int n) {///传入点数，点下标1开始 68         for(int i=1; i<=n; i++) { 69             if(!dfn[i]) { 70                 tarjan(i); 71             } 72         } 73     } 74     int getbcnt() {///强连通分量的个数 75         return Bcnt; 76     } 77     int getbelong(int id) {///属于哪个分量，分量下标1开始 78         return belong[id]; 79     } 80     int getnum(int id) {///某个分量的点的个数 81         return num[id]; 82     } 83 }tarjan; 84 static const int ME=300010;///边的个数 85 static const int MV=100010;///点的个数 86 struct G { 87     struct E { 88         int u,v,next; 89     } e[ME]; 90     int le,head[MV]; 91     void init() { 92         le=0; 93         mt(head,-1); 94     } 95     void add(int u,int v) { 96         e[le].u=u; 97         e[le].v=v; 98         e[le].next=head[u]; 99         head[u]=le++;100     }101 } gx;102 int dp[MV];103 int dfs(int u){104     if(dp[u]!=-1) return dp[u];105     int tmp=tarjan.getnum(u);106     dp[u]=tmp;107     for(int i=gx.head[u];~i;i=gx.e[i].next){108         int v=gx.e[i].v;109         dp[u]=max(dp[u],tmp+dfs(v));110     }111     return dp[u];112 }113 int main(){114     int n,m,u,v;115     while(~scanf("%d%d",&n,&m)){116         tarjan.init();117         for(int i=0;i<m;i++){118             scanf("%d%d",&u,&v);119             tarjan.add(u,v);120         }121         tarjan.solve(n);122         gx.init();123         for(int i=0;i<tarjan.g.le;i++){124             u=tarjan.g.e[i].u;125             v=tarjan.g.e[i].v;126             u=tarjan.getbelong(u);127             v=tarjan.getbelong(v);128             if(u!=v){129                 gx.add(u,v);130             }131         }132         mt(dp,-1);133         int ans=0;134         for(int i=1;i<=tarjan.getbcnt();i++){135             ans=max(ans,dfs(i));136         }137         printf("%d\n",ans);138     }139     return 0;140 }

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<stack>  5 #define mt(a,b) memset(a,b,sizeof(a))  6 using namespace std;  7 const int M=100010;  8 const int mod=1000000007;  9 typedef __int64 LL; 10 class Tarjan{///有向图强连通分量缩点 11     static const int ME=M*3;///边的个数 12     static const int MV=M;///点的个数 13     int Index,Bcnt,num[MV],belong[MV],dfn[MV],low[MV]; 14     bool instack[MV]; 15     stack<int> s; 16     void tarjan(int u) { 17         dfn[u]=low[u]=++Index; 18         instack[u]=true; 19         s.push(u); 20         int v; 21         for(int i=g.head[u]; ~i; i=g.e[i].next) { 22             v=g.e[i].v; 23             if(!dfn[v]) { 24                 tarjan(v); 25                 low[u]=min(low[u],low[v]); 26             } else if(instack[v]) { 27                 low[u]=min(low[u],dfn[v]); 28             } 29         } 30         if(dfn[u]==low[u]) { 31             Bcnt++; 32             do { 33                 v=s.top(); 34                 s.pop(); 35                 instack[v]=false; 36                 belong[v]=Bcnt; 37                 num[Bcnt]++; 38             } while(u!=v); 39         } 40     } 41     struct G { 42         struct E { 43             int u,v,next; 44         } e[ME]; 45         int le,head[MV]; 46         void init() { 47             le=0; 48             mt(head,-1); 49         } 50         void add(int u,int v) { 51             e[le].u=u; 52             e[le].v=v; 53             e[le].next=head[u]; 54             head[u]=le++; 55         } 56     } g; 57 public: 58     void init() { 59         g.init(); 60         Index=Bcnt=0; 61         mt(num,0); 62         mt(dfn,0); 63         mt(low,0); 64         mt(instack,0); 65         while(!s.empty()) s.pop(); 66     } 67     void add(int u,int v) { 68         g.add(u,v); 69     } 70     void solve(int n) {///传入点数，点下标1开始 71         for(int i=1; i<=n; i++) { 72             if(!dfn[i]) { 73                 tarjan(i); 74             } 75         } 76     } 77     int getbcnt() {///强连通分量的个数 78         return Bcnt; 79     } 80     int getbelong(int id) {///属于哪个分量，分量下标1开始 81         return belong[id]; 82     } 83     int getnum(int id) {///某个分量的点的个数 84         return num[id]; 85     } 86 }gx; 87 int val[M]; 88 struct G{ 89     int val,id; 90 }g[M]; 91 bool cmp(G a,G b){ 92     if(a.id==b.id) return a.val<b.val; 93     return a.id<b.id; 94 } 95 int main(){ 96     int n,m,x,y; 97     while(~scanf("%d",&n)){ 98         gx.init(); 99         for(int i=1;i<=n;i++){100             scanf("%d",&val[i]);101         }102         scanf("%d",&m);103         while(m--){104             scanf("%d%d",&x,&y);105             gx.add(x,y);106         }107         gx.solve(n);108 109         LL sum=0;110         LL ans=1;111         for(int i=1;i<=n;i++){112             g[i].val=val[i];113             g[i].id=gx.getbelong(i);114         }115         sort(g+1,g+1+n,cmp);116         g[0].id=-1;117         for(int i=1;i<=n;i++){118             if(g[i].id!=g[i-1].id){119                 sum+=(LL)g[i].val;120                 int num=0;121                 for(int j=i;j<=n;j++){122                     if(g[i].id==g[j].id&&g[i].val==g[j].val){123                         num++;124                     }125                     else{126                         i=j-1;127                         break;128                     }129                 }130                 ans*=num;131                 ans%=mod;132             }133         }134         printf("%I64d %I64d\n",sum,ans);135     }136     return 0;137 }