Description

現在電視臺有一種節目叫做超級英雄,大概的流程就是每位選手到臺上回答主持人的幾個問題,然后根據回答問題的多少獲得不同數目的獎品或獎金。主持人問題準備了若干道題目，只有當選手正確回答一道題后，才能進入下一題，否則就被淘汰。為了增加節目的趣味性并適當降低難度，主持人總提供給選手幾個“錦囊妙計”，比如求助現場觀眾，或者去掉若干個錯誤答案（選擇題）等等。 這里，我們把規則稍微改變一下。假設主持人總共有m道題，選手有n種不同的“錦囊妙計”。主持人規定，每道題都可以從兩種“錦囊妙計”中選擇一種，而每種“錦囊妙計”只能用一次。我們又假設一道題使用了它允許的錦囊妙計后，就一定能正確回答，順利進入下一題。現在我來到了節目現場，可是我實在是太笨了，以至于一道題也不會做，每道題只好借助使用“錦囊妙計”來通過。如果我事先就知道了每道題能夠使用哪兩種“錦囊妙計”，那么你能告訴我怎樣選擇才能通過最多的題數嗎？

Input

輸入文件的一行是兩個正整數n和m(0 < n <1001,0 < m < 1001)表示總共有n中“錦囊妙計”，編號為0~n-1，總共有m個問題。以下的m行，每行兩個數，分別表示第m個問題可以使用的“錦囊妙計”的編號。注意，每種編號的“錦囊妙計”只能使用一次，同一個問題的兩個“錦囊妙計”可能一樣。

Output

第一行為最多能通過的題數p

Sample Input

Sample Output

思路：

直接用問題去匹配錦囊即可，最大匹配即最多解決問題個數。

注意問題關鍵點，在于當且僅當我們做完第i個題的時候，才能去做第i+1個題。

所以我們在枚舉題去匹配錦囊的時候，如果沒有辦法得到一個正確的匹配的時候，break掉即可。

Ac代碼：

#include<stdio.h>#include<string.h>#include<vector>using namespace std;int match[1005];int vis[1005];vector<int >mp[1005];int find(int u){    for(int i=0;i<mp[u].size();i++)    {        int v=mp[u][i];        if(vis[v]==0)        {            vis[v]=1;            if(match[v]==-1||find(match[v]))            {                match[v]=u;                return 1;            }        }    }    return 0;}int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        memset(match,-1,sizeof(match));        for(int i=0;i<m;i++)mp[i].clear();        for(int i=0;i<m;i++)        {            int x,y;            scanf("%d%d",&x,&y);            mp[i].push_back(x);            mp[i].push_back(y);        }        int output=0;        for(int i=0;i<m;i++)        {            memset(vis,0,sizeof(vis));            if(find(i)==1)output++;            else break;        }        PRintf("%d/n",output);    }}