BZOJ 1064: [Noi2008]假面舞會

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?1655??Solved:?798
[Submit][Status][Discuss]

Description

一年一度的假面舞會又開始了，棟棟也興致勃勃的參加了今年的舞會。今年的面具都是主辦方特別定制的。每個參加舞會的人都可以在入場時選擇一 個自己喜歡的面具。每個面具都有一個編號，主辦方會把此編號告訴拿該面具的人。為了使舞會更有神秘感，主辦方把面具分為k (k≥3)類，并使用特殊的技術將每個面具的編號標在了面具上，只有戴第i 類面具的人才能看到戴第i+1 類面具的人的編號，戴第k 類面具的人能看到戴第1 類面具的人的編號。 參加舞會的人并不知道有多少類面具，但是棟棟對此卻特別好奇，他想自己算出有多少類面具，于是他開始在人群中收集信息。 棟棟收集的信息都是戴第幾號面具的人看到了第幾號面具的編號。如戴第2號面具的人看到了第5 號面具的編號。棟棟自己也會看到一些編號，他也會根據自己的面具編號把信息補充進去。由于并不是每個人都能記住自己所看到的全部編號，因此，棟棟收集的信 息不能保證其完整性。現在請你計算，按照棟棟目前得到的信息，至多和至少有多少類面具。由于主辦方已經聲明了k≥3，所以你必須將這條信息也考慮進去。

Input

第一行包含兩個整數n, m，用一個空格分隔，n 表示主辦方總共準備了多少個面具，m 表示棟棟收集了多少條信息。接下來m 行，每行為兩個用空格分開的整數a, b，表示戴第a 號面具的人看到了第b 號面具的編號。相同的數對a, b 在輸入文件中可能出現多次。

Output

包含兩個數，第一個數為最大可能的面具類數，第二個數為最小可能的面具類數。如果無法將所有的面具分為至少3 類，使得這些信息都滿足，則認為棟棟收集的信息有錯誤，輸出兩個-1。

Sample Input

【輸入樣例一】

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

【輸入樣例二】

3 3
1 2
2 1
2 3

Sample Output

【輸出樣例一】
4 4

【輸出樣例二】
-1 -1

HINT

100%的數據，滿足n ≤ 100000, m ≤ 1000000。

網上的代碼+我的注解：

1 /* 2 1.當圖中有環時，k必定是環長度的約數，那么答案就是全部環的最大公約數和最小的大于3的公約數 3 （而且可以看出這個最大公約數一定是這個大于3的最小公約數的倍數， 4 證明：假設真正的結果是m，因為最大公約數一定是n*m(n>=1),大于三的最小公約數一定是m的約數， 5 所以這個最大公約數一定是這個大于3的最小公約數的倍數。可以用這個方法從最大值找到最小值）， 6 若最大公約數小于3則無解； 7 2.當圖中沒有環時，最小值毫無疑問就是3了，k最大就是所有聯通塊最長鏈 8 （假設每個聯通塊的最長鏈都可以接到一起，不能在一個聯通塊里找兩條鏈，因為他們是有限制關系的，不能接起來）的和。 9 3技巧：這里面有個技巧，因為如果有兩個面具能看見同一個或一個能看見兩個，那這兩個的一定屬于同一類，而且也有可能出現這樣的聯通塊：1->2->3->4->5且6->7->5這樣就變得不好處理了。可以把有向邊換成無向邊正向的話類數+1，反向的話類數-1。這樣一來如果找到已經表過號的點就是找到了環，環的長度就是abs(將要編的號-已有編號)。而最長鏈就是一個聯通塊內最大編號-最小編號（因為有可能出現負數或0）。 10 實現時，所有邊建長度為1的正向邊和長度為-1的反向邊，會容易處理很多(這樣可以將所有點都標記成到某點距離為多少，可以方便計算環的長度)。 11 12 時間復雜度分析： 13 標號的時間復雜度為O（n+m），枚舉的時間復雜度是O（n）,找公約數的時間為O（log(n)），所以總時間復雜度為O（nlog(n)+m）. 14 */ 15 #include <iostream> 16 #include <cstdio> 17 #include <cstring> 18 #include <algorithm> 19 #include <cstdlib> 20 #include <cmath> 21 #define N 200000 22 #define M 4000000 23 24 using namespace std; 25 26 int head[N],next[M],to[M],len[M]; 27 bool vis[N],bh[M]; 28 int d[N]; 29 int n,m,cnt,ans,tmax,tmin,an; 30 31 inline void add(int u,int v,int w) 32 { 33 to[cnt]=v; len[cnt]=w; next[cnt]=head[u]; head[u]=cnt++; 34 } 35 36 inline void read() 37 { 38 memset(head,-1,sizeof head); cnt=0; 39 scanf("%d%d",&n,&m); 40 for(int i=1,a,b;i<=m;i++) 41 { 42 scanf("%d%d",&a,&b); 43 add(a,b,1); add(b,a,-1); 44 } 45 } 46 47 inline int gcd(int x,int y)/*ans的初值可以設為0，gcd(0,100)=100,只要把0放在第一位*/ 48 { 49 int ys; 50 while(y) 51 { 52 ys=x%y; 53 x=y; y=ys; 54 } 55 return x; 56 } 57 58 inline void dfs(int u) 59 { 60 vis[u]=true; 61 for(int i=head[u];~i;i=next[i]) 62 { 63 if(vis[to[i]])/*找到了環*/ 64 {/*計算環的長度并對每個環的長度求最大公約數：abs(d[u]+len[i]-d[to[i]])，這個式子很好理解d[u]+len[i]-d[to[i]]，因為標記有可能是負值，所以要取絕對值*/ 65 ans=gcd(ans,abs(d[u]+len[i]-d[to[i]])); 66 } 67 else 68 { 69 d[to[i]]=d[u]+len[i]; 70 dfs(to[i]); 71 } 72 } 73 } 74 75 inline void tree(int u) 76 {/*思路：將一個聯通塊找到第一個點標記為0，再用這個點找其他的點（不走重邊），用所有點的編號的中的max-min+1，就是這個聯通塊中的結點數目*/ 77 vis[u]=true; 78 tmax=max(tmax,d[u]); 79 tmin=min(tmin,d[u]); 80 for(int i=head[u];~i;i=next[i]) 81 if(!vis[to[i]]) 82 { 83 bh[i]=bh[i^1]=true; 84 d[to[i]]=d[u]+len[i]; 85 tree(to[i]); 86 } 87 } 88 89 inline void go() 90 { 91 for(int i=1;i<=n;i++) 92 if(!vis[i]) dfs(i);/*整張圖有可能是森林*/ 93 if(ans)/*如果圖中有環的話，那么ans就不是0*/ 94 { 95 for(an=3;an<ans&&ans%an;an++);/*再用ans尋找大于3的（可能等于ans），且能整除ans的，也就是環的最小公約數，是最小*/ 96 } 97 else/*沒有環的情況*/ 98 { 99 memset(vis,0,sizeof vis); 100 for(int i=1;i<=n;i++) 101 if(!vis[i])/*最大是每個聯通塊中的最長鏈的長度和，沒找到一個！vis[i]，就是一個聯通塊*/ 102 { 103 tmax=tmin=d[i]=0; 104 tree(i); 105 ans+=tmax-tmin+1; 106 } 107 an=3;/*最小就是3了*/ 108 } 109 if(ans<3) ans=an=-1;/*注意要把這個ans小于3，放在最后面，因為可能在沒有環的情況下，把各個聯通塊的最長路徑加在一起也超不過3，比如那種極端的網狀圖，最長路徑就有可能是1了，所以要把這個ans<3放在外面。*/ 110 /*我一開始就是僅僅把ans<3放到了有環的判斷中，結果錯了一個點*/ 111 printf("%d %d\n",ans,an); 112 } 113 114 int main() 115 { 116 read();go(); 117 return 0; 118 }

我的代碼：

1 #define N 100010 2 #define M 1000100 3 #include<iostream> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #include<cstdio> 8 int n,m,ans=0,an,head[N],t=-1,d[N]; 9 bool vis[N]={0},bianflag[M<<1]; 10 struct Edge{ 11 int v,w,last; 12 }edge[M<<1]; 13 int read1() 14 { 15 int ret=0,ff=1; 16 char s=getchar(); 17 while(s<'0'||s>'9') 18 { 19 if(s=='-') ff=-1; 20 s=getchar(); 21 } 22 while(s>='0'&&s<='9') 23 { 24 ret=ret*10+s-'0'; 25 s=getchar(); 26 } 27 return ret*ff; 28 } 29 void add_edge(int u,int v,int w) 30 { 31 ++t; 32 edge[t].v=v; 33 edge[t].w=w; 34 edge[t].last=head[u]; 35 head[u]=t; 36 } 37 void input() 38 { 39 n=read1();m=read1(); 40 int a,b; 41 memset(head,-1,sizeof(head)); 42 for(int i=1;i<=m;++i) 43 { 44 scanf("%d%d",&a,&b); 45 add_edge(a,b,1); 46 add_edge(b,a,-1); 47 } 48 } 49 int gcd(int a,int b) 50 { 51 if(!b) return a; 52 return gcd(b,a%b); 53 } 54 void dfs1(int k) 55 { 56 vis[k]=true; 57 for(int l=head[k];l!=-1;l=edge[l].last) 58 { 59 if(vis[edge[l].v]) 60 { 61 ans=gcd(ans,abs(d[k]+edge[l].w-d[edge[l].v])); 62 } 63 else { 64 d[edge[l].v]=d[k]+edge[l].w; 65 dfs1(edge[l].v); 66 } 67 } 68 } 69 void dfs2(int k,int &maxx,int &minn) 70 { 71 vis[k]=true; 72 maxx=max(maxx,d[k]); 73 minn=min(minn,d[k]); 74 for(int l=head[k];l!=-1;l=edge[l].last) 75 { 76 if(bianflag[l]) continue; 77 bianflag[l]=true; 78 bianflag[l^1]=true; 79 d[edge[l].v]=d[k]+edge[l].w; 80 dfs2(edge[l].v,maxx,minn); 81 } 82 } 83 int main() 84 { 85 input(); 86 for(int i=1;i<=n;++i) 87 { 88 if(!vis[i]) dfs1(i); 89 } 90 if(ans) 91 { 92 for(an=3;an<ans&&ans%an;++an); 93 94 } 95 else 96 { 97 an=3; 98 memset(vis,false,sizeof(vis)); 99 for(int i=1;i<=n;++i) 100 { 101 if(!vis[i]) 102 { 103 int maxx,minn; 104 maxx=minn=d[i]=0; 105 dfs2(i,maxx,minn); 106 ans+=maxx-minn+1; 107 //cout<<maxx<<" "<<minn<<" "<<ans<<endl; 108 } 109 } 110 } 111 if(ans<3) 112 { 113 ans=-1;an=-1; 114 } 115 printf("%d %d",ans,an); 116 return 0; 117 } 118

?

轉載于:https://www.cnblogs.com/c1299401227/p/5861351.html

總結

以上是生活随笔為你收集整理的图论 公约数 找环和链 BZOJ [NOI2008 假面舞会]的全部內容，希望文章能夠幫你解決所遇到的問題。

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