題目鏈接

---

?

題意：二分多重匹配的裸題，與匈牙利算法不同的之前的男女匹配不同，這個題目的題意是每一個人可以選擇多種型號的衣服，并且每一種衣服可以很多人穿，但是每件衣服有數量限制，問最多有多少匹配數。

• 我們用girl[i][x],表示第i種衣服的第x件的歸宿，也就是哪個人穿的

• cnt[i]表示第i種衣服已經用的次數

• num[i]表示第i種衣服的總數量

核心代碼:

bool find(int u)
{for(int i=m[u].first;i<=m[u].second;i++)//就是這個u男孩喜歡的衣服范圍{if(!used[i])//如果這件衣服沒有詢問過{used[i]=1;if(cnt[i]<num[i])//如果現在該種衣服沒用完{girl[i][cnt[i]++]=u;//那么就直接把第cnt[i]件衣服給u，同時該衣服用的數量+1return true;}//那用完了怎么辦，思想還是一樣的，就從它已經有的匹配中重新找別的匹配看得行不for(int j=0;j<num[i];j++)if(find(girl[i][j]))//如果之前那個穿第i種第j件衣服的男孩也有別的可以穿的衣服{girl[i][j]=u;//就把這個第i種第j件衣服給男孩ureturn true;}}}return false;//找不到就返回false
}
int hungry()
{int ans=0;memset(cnt,0,sizeof(cnt));//每種衣服已經用的初始化為0for(int i=1;i<=n;i++){memset(used,0,sizeof(used));//每一次的詢問標記if(find(i)) ans++;}return ans;
}

完整代碼貼上：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
const int dir[4][2]= {0,-1,-1,0,0,1,1,0};
typedef long long ll;
const ll inFF=9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=21;
int girl[maxn][maxn],cnt[maxn],num[maxn],used[maxn];
int n;
map<int,pr>m;
bool find(int u)
{for(int i=m[u].first;i<=m[u].second;i++){if(!used[i]){used[i]=1;if(cnt[i]<num[i]){girl[i][cnt[i]++]=u;return true;}for(int j=0;j<num[i];j++)if(find(girl[i][j])){girl[i][j]=u;return true;}}}return false;
}
int hungry()
{int ans=0;memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;i++){memset(used,0,sizeof(used));if(find(i)) ans++;}return ans;
}
int main()
{string r;map<char,int> mp;mp['S']=1,mp['M']=2,mp['L']=3,mp['X']=4,mp['T']=5;char ch1,ch2;while(cin>>r,r!="ENDOFINPUT"){scanf("%d",&n);m.clear();for(int i=1;i<=n;i++){getchar();scanf("%c%c",&ch1,&ch2);m[i]=pii(mp[ch1],mp[ch2]);}for(int i=1;i<=5;i++)scanf("%d",&num[i]);cin>>r;if(hungry()==n) puts("T-shirts rock!");else puts("I'd rather not wear a shirt anyway...");}return 0;
}

?

總結

以上是生活随笔為你收集整理的POJ - 2584 T-Shirt Gumbo 二分多重匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

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