TopCoder

Thumb output jddoia
$\huge 南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

52.6% (10/19)

Description

Original Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬兩歲又四個月大時的故事。

殿壬兩歲又四個月時,就致力於研究圖論(Graph Theory)中的「匹配問題」(Matching Problem):給你一張圖 $G = (V,E)$ ,請問這張圖的最大匹配的邊的數量是多少。

如果你不知道什麼是「匹配問題」的話,沒有關係,殿壬已經幫你查好維基百科了:對於一個給定的圖 $G=(V,E)$ ,這張圖的一個匹配 $M$ 是圖 $G$ 的一個子圖(由原來的圖的一部分頂點和一部分邊構成的圖),其中每兩條邊都不相鄰(沒有公共頂點)。在匹配圖中,一個頂點連出的邊數至多是一條。而一個匹配的大小,就是匹配圖 $M$ 裡面的邊的數量。

現在,殿壬遇到了一題匹配問題了:給你一張 $N$ 點(點從 $1$ 到 $N$ 編號) $M$ 邊(邊從 $1$ 到 $M$ 編號)的無向連通簡單圖(Simple Graph,不存在重邊、自環的圖),第 $i$ 條邊連結著點 $a_i$ 和點 $b_i$ ,請輸出最大匹配的邊的數量。

Original Input Format

輸入的第一行包含兩個正整數 $N, M$ ,代表圖的點數、邊數。

接下來的 $M$ 行,每行包含兩個正整數,第 $i$ 行的兩個正整數為 $a_i, b_i$ ,代表第 $i$ 條邊連接的邊。

  • $1 \le N \le 100$
  • $1 \le M \le 500$
  • $1 \le a_i, b_i \le N$
  • 保證圖是 連通 並且 簡單 (不存在重邊、自環)的

Original Output Format

請輸出一個數字,代表最大匹配的邊的數量。

Original Sample Input

Sample Input 1:
3 3
1 2
2 3
3 1

Sample Input 2:
4 3
1 2
2 3
3 4

Original Sample Output

Sample Output 1:
1

Sample Output 2:
2

Original Limits

  • Time Limit: 2 second
  • Memory Limit: 256 MB

Program To Be Hacked

#include <bits/stdc++.h>
using namespace std;

int n , m , u[106] , ans;
pair<int,int> x[506];

int main(){
    clock();
    cin >> n >> m;
    for(int i = 0 ;i < m; ++i) cin >> x[i].first >> x[i].second;
    for(int times = 0; times < 5000 * 5000; ++ times){
        random_shuffle(x , x + m);
        memset(u,0,sizeof(u));
        int cnt = 0;
        for(int i = 0 ;i < m; ++i) if(u[x[i].first] == 0 && u[x[i].second] == 0){
            u[x[i].first] = 1;
            u[x[i].second] = 1;
            cnt ++;
        }
        ans = max(ans , cnt);
        if(1.0 * clock() / CLOCKS_PER_SEC > 1.99) break;
    }
    cout << ans << endl;
    return 0;
}

Judge Method

精通「匹配問題」的殿壬,他發現:認真寫出一個 $O(n^ 3)$ 的縮花演算法太累了,不如好好的 唬爛 一波,寫個隨機演算法,正確的機率又高、程式碼又短,怎麼看都是一個好選擇。

你,身為殿壬的好朋友,決定要幫殿壬戒掉這個壞習慣,而讓他戒掉這個壞習慣的方法就是給他一筆會 Wrong Answer 的測試資料。

請你幫幫殿壬吧。

Sample Code

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。

#include <cstdio>
int main() {
    printf("3 3\n1 2\n2 3\n3 1\n");
}

Input Format

Output Format

Sample Input

Sample Output

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1