NOI 2008 假面舞會 party

這道題難在對圖的深入分析。如果一個人能夠看見兩個不同的人，那麼這兩個人所戴的面具種類一定相同，同樣，如果一個人能被兩個人看見，這兩個人所戴的面具種類也一定相同。把每個人當作圖中的一個頂點，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。

相關日誌