NOI 2008 假面舞會 party
本文正體字版由OpenCC轉換
這道題難在對圖的深入分析。如果一個人能夠看見兩個不同的人，那麼這兩個人所戴的面具種類一定相同，同樣，如果一個人能被兩個人看見，這兩個人所戴 的面具種類也一定相同。把每個人當作圖中的一個頂點，a能看見b，則連接(a,b)一條有向邊。我們把能夠推斷出的帶相同面具的人成爲一個類。
顯然圖中可能會有多個連通分量，對於某個連通分量，如果把邊的方向去掉，該連通分量中存在一個無向環，則稱該連通分量爲環結構，否則成爲 樹結構。可以發現，一個環結構的連通分量，逐步把一個類的所有頂點收縮爲一個頂點，最終一定會剩下一個有向環，而一個樹結構的連通分量也會變成一個單向的 有向樹。一個環結構的連通分量，最終有向環上頂點個數，就是該連通分量的最大類數，而且，最大類數的所有約數也都可以滿足該連通分量的類數。而樹結構連通 分量，有向樹中的最長路徑，就是該連通分量的最大類數。
顯然環結構是關鍵的，如果同時存在樹結構和環結構的連通分量，樹結構可以忽略。如果存在兩個（或多個）環結構連通分量，它們類數的最大公約數可以就是滿足這兩個連通分量的最大類數，它們類數的最大公約數的大於等於3的最小公約數就是滿足這兩個連通分量的最小類數。
關鍵問題就是求一個環結構連通分量的等價環的長度。收縮等位頂點的方法不便於編寫，我們可以用一遍DFS的方法。對於一個連通分量，從一個 頂點開始DFS，有向邊可以雙向走，第一個頂點標號1。遇到正向的邊，標號加1，遇到反向的邊，標號減1。遇到已經訪問過的點，則說明找到了一個等價環， 長度爲該點應該被標的標號減去已有的標號的差的絕對值，標號不改變然後返回繼續DFS。這樣以O(N+M)的時間求出所有等價環長度，算出最大和最小公約 數即可。
/*
* Problem: NOI2008 party
* Author: Guo Jiabao
* Time: 2009.3.4 22:41
* State: Solved
* Memo: dfs找環和鏈 求公約數
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=100001,MAXM=1000001;
using namespace std;
struct edge
{
edge *next,*op;
int t,c;
bool nuked;
}ES[MAXM];
struct vertex
{
edge *f,*l;
int it,bl;
bool vis;
}V[MAXN];
int N,M,EC,Ccnt,Gans,Mans,D;
int C[MAXN],BMax[MAXN],BMin[MAXN];
inline edge * addedge(int a,int b,int c)
{
if (V[a].l)
V[a].l=V[a].l->next=&ES[++EC];
else
V[a].f=V[a].l=&ES[++EC];
ES[EC].t=b;
ES[EC].c=c;
ES[EC].nuked=false;
return &ES[EC];
}
void init()
{
int i,a,b;
freopen("party2008.in","r",stdin);
freopen("party2008.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
edge *e1=addedge(a,b,1);
edge *e2=addedge(b,a,-1);
e1->op=e2;
e2->op=e1;
}
Gans=0;
}
inline int ABS(int a) {return a<0?-a:a;}
void findcircle(int u,int it)
{
V[u].it=it;
V[u].vis=true;
for (edge *k=V[u].f;k;k=k->next)
{
if (k->nuked) continue;
k->nuked=k->op->nuked=true;
int v=k->t;
if (!V[v].vis)
findcircle(v,it+k->c);
else
{
if (it+k->c - V[v].it!=0)
C[++Ccnt]=ABS(it+k->c - V[v].it);
}
}
}
inline int gcd(int a,int b)
{
int c;
while (b)
{
c=a%b;
a=b;
b=c;
}
return a;
}
void findpart(int u)
{
V[u].bl=D;
for (edge *k=V[u].f;k;k=k->next)
{
int v=k->t;
if (V[v].bl==0)
findpart(v);
}
}
void part() //求連通分量
{
int i;
D=0;
for (i=1;i<=N;i++)
V[i].bl=0;
for (i=1;i<=N;i++)
{
if (V[i].bl==0)
{
++D;
findpart(i);
BMin[D]=0x7FFFFFFF;
BMax[D]=-0x7FFFFFFF;
}
}
}
void furthest(int u,int it)
{
V[u].it=it;
V[u].vis=true;
for (edge *k=V[u].f;k;k=k->next)
{
if (k->nuked) continue;
k->nuked=k->op->nuked=true;
int v=k->t;
furthest(v,it+k->c);
}
}
void link()
{
int i;
for (i=1;i<=N;i++)
{
V[i].vis=false;
for (edge *k=V[i].f;k;k=k->next)
k->nuked=k->op->nuked=false;
}
for (i=1;i<=N;i++)
{
if (!V[i].vis)
furthest(i,1);
if (V[i].it>BMax[ V[i].bl ])
BMax[ V[i].bl ]=V[i].it;
if (V[i].it<BMin[ V[i].bl ])
BMin[ V[i].bl ]=V[i].it;
}
Gans=0;
for (i=1;i<=D;i++)
Gans+=BMax[i]-BMin[i]+1;
if (Gans < 3)
Gans=Mans=-1;
else
Mans=3;
}
void solve()
{
int i,GCD,LCD,MIN;
for (i=1;i<=N;i++)
if (!V[i].vis)
findcircle(i,1);
MIN=GCD=C[1];
for (i=2;i<=Ccnt;i++)
{
GCD=gcd(GCD,C[i]);
if (C[i] < MIN)
MIN = C[i];
}
for (LCD=3;LCD<=MIN;LCD++)
{
for (i=1;i<=Ccnt;i++)
if (C[i] % LCD !=0)
break;
if (i>Ccnt)
break;
}
if (Ccnt==0) //無環
{
part();
link();
}
else if (GCD>=3)
{
Gans=GCD;
Mans=LCD;
}
else
Gans=Mans=-1;
}
int main()
{
init();
solve();
printf("%d %dn",Gans,Mans);
return 0;
}
<h2><span class="mw-headline">假面舞會 </span></h2>
【問題描述】
一年一度的假面舞會又開始了，棟棟也興致勃勃的參加了今年的舞會。今年的面具都是主辦方特別定製的。每個參加舞會的人都可以在入場時選擇一 個自己喜歡的面具。每個面具都有一個編號，主辦方會把此編號告訴拿該面具的人。爲了使舞會更有神祕感，主辦方把面具分爲k (k≥3)類，並使用特殊的技術將每個面具的編號標在了面具上，只有戴第i 類面具的人才能看到戴第i+1 類面具的人的編號，戴第k 類面具的人能看到戴第1 類面具的人的編號。 參加舞會的人並不知道有多少類面具，但是棟棟對此卻特別好奇，他想自己算出有多少類面具，於是他開始在人羣中收集信息。
棟棟收集的信息都是戴第幾號面具的人看到了第幾號面具的編號。如戴第2號面具的人看到了第5 號面具的編號。棟棟自己也會看到一些編號，他也會根據自己的面具編號把信息補充進去。由於並不是每個人都能記住自己所看到的全部編號，因此，棟棟收集的信 息不能保證其完整性。現在請你計算，按照棟棟目前得到的信息，至多和至少有多少類面具。由於主辦方已經聲明瞭k≥3，所以你必須將這條信息也考慮進去。
【輸入格式】
輸入文件party.in 第一行包含兩個整數n, m，用一個空格分隔，n 表示主辦方總共準備了多少個面具，m 表示棟棟收集了多少條信息。
接下來m 行，每行爲兩個用空格分開的整數a, b，表示戴第a 號面具的人看到了第b 號面具的編號。相同的數對a, b 在輸入文件中可能出現多次。
【輸出格式】
輸出文件party.out 包含兩個數，第一個數爲最大可能的面具類數，第二個數爲最小可能的面具類數。如果無法將所有的面具分爲至少3 類，使得這些信息都滿足，則認爲棟棟收集的信息有錯誤，輸出兩個-1。
【輸入樣例一】
<pre>6 5
1 2
2 3
3 4
4 1
3 5</pre>
【輸出樣例一】
<pre>4 4</pre>
【輸入樣例二】
<pre>3 3
1 2
2 1
2 3</pre>
【輸出樣例二】
<pre>-1 -1</pre>
【數據規模和約定】
- 50%的數據，滿足n ≤ 300, m ≤ 1000；
- 100%的數據，滿足n ≤ 100000, m ≤ 1000000。
上次修改時間 2017-02-03