CodeChef - GRAPHCT Graph Counting+

題目連結

A 題意分析：n條直線将地圖切成多個塊，起點終點都在塊上，問從起點到終點，最少要走多少步？（有公共邊的塊認為是相鄰的塊）

解題思路：猜想：A、B兩點間的線段與多少條直線相交，就是我們需要走的步數。即：步數 = 與線段相交的直線條數（直接搜題解的朋友，建議看到這裡就自己去實作一方，或者自己去證明下）

#include<bits/stdc++.h>
using namespace std;
const double eps = ;
int main()
{
    double x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;
    int ans = ;
    int n;
    cin>>n;
    for(int i=;i<n;i++)
    {
        double a,b,c;
        cin>>a>>b>>c;
        if((a*x1+b*y1+c)*(a*x2+b*y2+c)<)
            ++ans;
    }
    cout<<ans<<endl;
    return ;
}
           

G：首先為一些定義：

假設G =（V，E）是一個包含邊u =（u，v）且u≠v的無向圖。設f是映射V \ {u，v}中每個頂點到自身的函數，否則，将其映射到一個新的頂點w。e的收縮産生了一個新的圖G’=（V’，E’），其中V’=（V \ {u，v}）∪{w}，E’= E \ {e} x∈V，x’= f（x）∈V’入射到邊e’∈E’當且僅當相應的邊e∈E入射到x中的x。

一個無向圖H被稱為圖G的一個次微分，如果H同構于一個圖，可以通過G的一個子圖上零個或多個邊收縮來獲得。

如果任何兩個頂點之間存在路徑，則連接配接圖。雙連接配接圖即使在移除任何一個頂點和所有的邊緣之後仍保持連接配接。

一個簡單的圖是在任何一對頂點之間沒有多于一個邊的圖，也沒有從頂點到它自身的邊。

您需要計算有多少個具有n個頂點和m個邊的簡單雙連通圖，使得它們不具有長度為5的周期作為次要。如果存在具有在第一圖中相鄰的标簽i和j的頂點而不是在第二圖中存在兩個圖，則認為兩個圖是不同的。

輸入：

第一行包含測試用例T.每個下一行包含兩個整數n和m。

輸出：

輸出T行，一個對應于每個測試用例。對于測試用例，請輸出問題中所述的圖表數量。輸出答案模1000000007。

樣本輸入：

5

1 0

3 2

3 3

4 4

5 10

采樣輸出：

1

1

3

限制條件：

1 <= T <= 2000

1 <= n <= 100

0 <= m <= 10000

可以證明，如果G有一個長度大于等于5的周期，則G有一個長度為5的周期。是以我們希望計算沒有長度≥5的周期的雙連通圖。

現在，我們首先證明任何具有n> = 5頂點的雙連通圖具有至少為4的長度的周期。考慮沒有連接配接的任何節點u和v。由于u和v之間存在至少兩條不相交的路徑（每一個長度> = 2），是以我們可以将它們組合起來形成一個長度大于等于4的周期。是以，唯一的可能性是對于所有u，v都有一個邊之間。但是在這種情況下，圖是一個團，并且具有長度≥4的周期。是以，具有> = 5個頂點的所有雙連通分量都具有周期。

現在我們可以使用兩個連通圖的一個耳朵分解。結果基本上說，我們可以從G中的任何循環開始，并通過向G添加最大路徑（耳朵）來逐漸形成圖形。是以，我們從具有4個節點的循環開始（一個确實存在，就像我們上面看到的那樣）。現在分析幾個例子，發現增加耳朵到G的唯一方法是在1對角線之間，每個耳朵的長度應該是2，在其他情況下，我們得到一個長度大于等于5的周期。是以，G看起來像這樣：有兩個節點u和v，它們之間有n-2條長度為2的不相交路徑。如果需要，我們可以選擇在u和v之間添加直接邊緣。是以，G中邊的總數是2 （n-2）或2 （n-2）+1。我們可以用ncr（n，2）方法選擇u和v。這給了我們以下結果：

如果n = 1，則輸出1（如果m = 0），否則輸出0

如果n = 2，則輸出1（如果m = 1），否則輸出0

如果n = 3，則輸出1（如果m = 3），否則輸出0

如果n = 4，則輸出3（如果m = 4）。如果m = 6輸出1，否則如果m = 5輸出6.否則輸出0

對于n> = 5，如果m = 2 （n-2）或m = 2 （n-2）+1，則輸出n *（n-1）/ 2。否則輸出0。

#include<bits/stdc++.h>
using namespace std;
const double eps = ;
int main()
{
     int t,n,m;
        cin>>t;
        while(t--)
        {
            cin>>n>>m;
            int ans = ;
            if(n==)
            {

                if(m==)
                {
                    ans = ;
                }
            }
            else if(n==)
            {
                if(m==)
                {
                    ans = ;
                }
            }
            else if(n==)
            {
                if(m==)
                {
                    ans = ;
                }
            }
            else if(n==)
            {
                if(m==)ans = ;
                if(m==)ans = ;
                if(m==)ans = ;
            }
            else if(m==*(n-))
            {
                ans=n*(n-)/;
            }
            else if(m==(*(n-)+))
            {
                ans=n*(n-)/;
            }
            cout<<ans<<endl;
        }
    return ;
}
           

It can be shown that G has a cycle of length 5 as a minor iff G has a cycle of length >= 5 in it. So we wish to count biconnected graphs having no cycle of length >= 5.

We start by working out a few special cases for n <= 4. Now, first we show that any biconnected graph having n >= 5 vertices has a cycle of length atleast 4. Consider any nodes u and v which are not connected. Since there are atleast 2 disjoint paths between u and v (each of length >= 2), we can combine them to form a cycle of length >= 4. Hence, the only possibility is that for all u,v there is an edge between then. But in that case, the graph is a clique and has a cycle of length >= 4. Thus, all biconnected components having >= 5 vertices have a cycle.

Now we can use an ear decomposition of two connected graphs. The result basically says that we can start off with any cycle in G, and form the graph progressively by adding maximal paths (ears) to G. So we start off with a cycle having 4 nodes (one surely exists, as we have seen above). Now analysing a few cases reveals that the only way to add ears to G are between 1 diagonal, and each ear should have length exactly 2. In all other cases, we get a cycle of length >= 5. Thus, G looks like this : there are two nodes u and v, with n - 2 disjoint paths of length 2 between them. We can optionally add a direct edge between u and v if needed. Thus, the total number of edges in G are either 2 * (n-2) or 2 * (n-2) + 1. We can choose u and v in ncr(n,2) ways. This gives us the following result :

if n = 1, output 1 if m = 0, else 0

if n = 2, output 1 if m = 1, else 0

if n = 3, output 1 if m = 3, else 0

if n = 4, output 3 if m = 4. If m = 6 output 1, else if m = 5 output 6. else output 0

for n >= 5, output n * (n-1)/2 if m = 2 * (n-2) or m = 2 * (n-2) + 1. else output 0.