題目鏈接：點擊查看

題目大意：杰瑞和湯姆在玩游戲，游戲規則是：湯姆會拿來N個容器，每個容器內一開始就會包含1~N個小球，現在輪到杰瑞操作了，杰瑞可以選擇往每個容器里加入0個或者任意k的倍數個小球，問杰瑞能否讓最后有一個容器中有一個小球，有一個容器中有兩個小球，依次類推，讓每個容器中的小球個數都是遞增上升的，直到N結束

題目分析：剛看完這個題目之后以為上升的序列必須是連續的，判斷交上去直接WA了一發，后來意識到這個序列也不一定連續，通過操作可以讓一個1 1 1 1的序列變為1 3 2 4，這個序列也是滿足題意的，所以這就變成了一個二分圖最大匹配的問題，我們可以一開始讓容器編號對于最后結果建邊，也可以讓最后結果對于容器編號建邊，建好邊后跑一遍匈牙利并且記錄一下最大匹配量就可以判斷能否達到結果了，這里我用的是答案對于容器建邊，其實都一樣，看自己的個人愛好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int a[N];int n,k;bool maze[N][N];int match[N];bool vis[N];bool dfs(int x) {for(int i=1;i<=n;i++)//枚舉容器編號{if(maze[x][i]&&!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d%d",&n,&k);memset(maze,false,sizeof(maze));memset(match,0,sizeof(match));for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1;i<=n;i++)//枚舉每個容器{for(int j=a[i];j<=n;j++)//枚舉每個可能到達的答案 {int temp=j-a[i];if(temp%k)continue;maze[j][i]=true;//maze[可到達答案的值][容器編號]}}int ans=0;for(int i=1;i<=n;i++)//枚舉答案{memset(vis,false,sizeof(vis));if(dfs(i))ans++;}if(ans==n)//若所有容器和答案都匹配，則杰瑞勝利，否則湯姆勝利printf("Jerry\n");elseprintf("Tom\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 5090 Game with Pearls(二分图最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。