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
2 1
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 ![[HDU] 3549 Flow Problem [最大流][Dinic][讀取優化][圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)