殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬兩歲又四個月大時的故事。
殿壬兩歲又四個月時,就致力於研究圖論(Graph Theory)中的「匹配問題」(Matching Problem):給你一張圖
如果你不知道什麼是「匹配問題」的話,沒有關係,殿壬已經幫你查好維基百科了:對於一個給定的圖
現在,殿壬遇到了一題匹配問題了:給你一張
輸入的第一行包含兩個正整數
接下來的
請輸出一個數字,代表最大匹配的邊的數量。
Sample Input 1:
3 3
1 2
2 3
3 1
Sample Input 2:
4 3
1 2
2 3
3 4
Sample Output 1:
1
Sample Output 2:
2
#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; }
精通「匹配問題」的殿壬,他發現:認真寫出一個
你,身為殿壬的好朋友,決定要幫殿壬戒掉這個壞習慣,而讓他戒掉這個壞習慣的方法就是給他一筆會 Wrong Answer
的測試資料。
請你幫幫殿壬吧。
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。
#include <cstdio> int main() { printf("3 3\n1 2\n2 3\n3 1\n"); }
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 1 |