TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

58.5% (24/41)

Tags

Description

Original Description

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

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

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

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

Original Input Format

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

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

  • 1N100
  • 1M500
  • 1ai,biN
  • 保證圖是 連通 並且 簡單 (不存在重邊、自環)的

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(n3) 的縮花演算法太累了,不如好好的 唬爛 一波,寫個隨機演算法,正確的機率又高、程式碼又短,怎麼看都是一個好選擇。

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

請你幫幫殿壬吧。

Sample Code

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

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

Input Format

Output Format

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0 1

Testdata and Limits

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