1093: [ZJOI2007]最大半連通子圖

Description

　　一個有向圖G=(V,E)稱為半連通的(Semi-Connected)，如果滿足：?u,v∈V，滿足u→v或v→u，即對于圖中任意兩點u，v,存在一條u到v的有向路徑或者從v到u的有向路徑。若G'=(V',E')滿足V'?V，E'是E中所有跟V'有關的邊，則稱G'是G的一個導出子圖。若G'是G的導出子圖，且G'半連通，則稱G'為G的半連通子圖。若G'是G所有半連通子圖中包含節點數最多的，則稱G'是G的最大半連通子圖。給定一個有向圖G，請求出G的最大半連通子圖擁有的節點數K，以及不同的最大半連通子圖的數目C。由于C可能比較大，僅要求輸出C對X的余數。

Input

　　第一行包含兩個整數N，M，X。N，M分別表示圖G的點數與邊數，X的意義如上文所述接下來M行，每行兩個正整
數a, b，表示一條有向邊(a, b)。圖中的每個點將編號為1,2,3…N，保證輸入中同一個(a,b)不會出現兩次。N ≤1
00000, M ≤1000000；對于100%的數據， X ≤10^8

Output

　　應包含兩行，第一行包含一個整數K。第二行包含整數C Mod X.

Sample Input

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

Sample Output

3
3

---

　　這是一道水題無疑。但是，所謂的半連通確實很能混淆視聽。既然題目只針對所謂的“最大半連通子圖”，那就依它來吧。 　　很明顯強連通滿足半聯通的條件。然后再想，不在同一個強連通分量中，怎樣才能做到所謂的“半連通”？ 　　可能你已經明白了。實在是太簡單不過了。找DAG（人稱“大哥”）上的一條鏈足矣。 　　而“最大半連通子圖擁有的節點數”，即是找縮點后DAG圖中擁有最多節點的鏈。注意，此處并不是找最長鏈。 　　另外，計數？簡單。按拓撲序更新即是了。 　　但是，但是，但是！ 　　我第一次交上去WA了。因為，圖中有重邊。DP更新方案數時很有可能重復計數。 　　代碼如下： 1 /************************************************************** 2 Problem: 1093 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:1360 ms 7 Memory:23928 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 template<class T>inline void readin(T &res) { 15 static char ch;T flag=1; 16 while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1; 17 res=ch-48;while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag; 18 } 19 20 const int N = 100100; 21 const int M = 1001000; 22 struct Edge {int v,upre;}; 23 struct CON { 24 Edge e[M];int head[N], ne; 25 void clear(int p) {ne=p;memset(head,p,sizeof(head));} 26 inline void adde(int u,int v) {e[++ne]=(Edge){v,head[u]};head[u]=ne;} 27 }g,ng; 28 29 int n, m, MOD, u, v; 30 int dfn[N], low[N], idy, stack[N], top, col[N], tcol; 31 int siz[N], f[N], t[N], in[N], vis[N]; 32 bool ins[N]; 33 void tarjan(int u) { 34 dfn[u]=low[u]=++idy; 35 stack[++top]=u;ins[u]=1; 36 for( int i = g.head[u]; i; i = g.e[i].upre ) { 37 int v=g.e[i].v; 38 if(!dfn[v]) tarjan(v), low[u]=std::min(low[u],low[v]); 39 else if(ins[v]) low[u]=std::min(low[u],dfn[v]); 40 } 41 if(low[u]==dfn[u]) { 42 ++tcol; 43 while(stack[top+1]!=u) { 44 col[stack[top]]=tcol; 45 siz[tcol]++; 46 ins[stack[top--]]=0; 47 } 48 } 49 } 50 inline void add(int &a,int b) {a=a+b>MOD?a+b-MOD:a+b;} 51 int main() { 52 readin(n);readin(m);readin(MOD); 53 g.clear(0);ng.clear(0); 54 for( int i = 1; i <= m; i++ ) { 55 readin(u);readin(v); 56 g.adde(u,v); 57 } 58 for( int i = 1; i <= n; i++ ) if(!dfn[i]) tarjan(i); 59 for( int u = 1; u <= n; u++ ) for( int i = g.head[u]; i; i=g.e[i].upre ) { 60 int v=g.e[i].v; 61 if(col[u]!=col[v]) ng.adde(col[u],col[v]), in[col[v]]++; 62 } 63 top=0; 64 for( int i = 1; i <= tcol; i++ ) if(!in[i]) stack[++top]=i, f[i]=siz[i], t[i]=1; 65 while(top) { 66 int u=stack[top];top--; 67 for( int i = ng.head[u]; i; i = ng.e[i].upre ) { 68 int v=ng.e[i].v; 69 in[v]--; 70 if(!in[v]) stack[++top]=v; 71 if(vis[v]==u) continue; 72 if(f[u]+siz[v]>f[v]) f[v]=f[u]+siz[v], t[v]=t[u]; 73 else if(f[u]+siz[v]==f[v]) add(t[v],t[u]); 74 vis[v]=u; 75 } 76 } 77 int num=0, ans=0; 78 for( int i = 1; i <= tcol; i++ ) num=std::max(num,f[i]); 79 printf("%d\n",num); 80 for( int i = 1; i <= tcol; i++ ) if(f[i]==num) add(ans,t[i]); 81 printf("%d\n",ans); 82 return 0; 83 } 84 tarjan縮點+拓撲排序簡單DP

轉載于:https://www.cnblogs.com/Doggu/p/bzoj1093.html

總結

以上是生活随笔為你收集整理的BZOJ 1093 [ZJOI2007]最大半连通子图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。