本文主要是介绍UVa11045 My T-shirt suits me，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：共有n件衣服，m个人，n>=m，衣服有6种尺码，总数量是6的倍数，每种尺码衣服的数量相同。每个人能穿两种尺码的衣服，比如XL和XXL。问是否每个人都能穿上合身的衣服。
思路：二分图匹配。幸好学过离散数学，看到题目马上反应过来是二分图匹配，但是不知道算法。去看了一下书，说是可以转换为最大流，建立一个源，连接所有的衣服，衣服到人如果合适，连接起来，再把所有人连接到一个汇。其中每条边的权都是1，这样匹配问题直接转换成最大流，如果最大流等于人数，说明有解。太机智了！！！
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <ctype.h>
#define INF 1000000000
using namespace std;int G[70][70];int sizetoint(string str){if(str=="XS")return 1;if(str=="S")return 2;if(str=="M")return 3;if(str=="L")return 4;if(str=="XL")return 5;if(str=="XXL")return 6;return 0;
}int main(){int t;cin>>t;while(t--){memset(G,0,sizeof(G));int n,m;cin>>n>>m;int nn=n/6;string str1,str2;//建图 for(int i=1;i<=m;i++){cin>>str1>>str2;for(int j=1;j<=nn;j++){G[(sizetoint(str1)-1)*nn+j][n+i]=1;G[(sizetoint(str2)-1)*nn+j][n+i]=1;}}//源点到衣服 for(int i=1;i<=n;i++){G[0][i]=1;}//人到汇点 for(int i=n+1;i<=n+m;i++){G[i][n+m+1]=1;}//最大流问题增广路算法 int f[70][70];int a[70];int pre[70];int maxf=0;memset(f,0,sizeof(f));while(true){memset(a,0,sizeof(a));queue<int> que;a[0]=INF;que.push(0);while(!que.empty()){int cur=que.front();que.pop();for(int i=0;i<=m+n+1;i++){if(!a[i]&&(G[cur][i]-f[cur][i])){a[i]++;que.push(i);pre[i]=cur;}}}for(int i=n+m+1;i!=0;i=pre[i]){f[pre[i]][i]++;f[i][pre[i]]--;}if(!a[n+m+1])break;maxf++;}if(maxf==m){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}
下面是匈牙利算法：每一个人去找衣服，如果找到的衣服没人穿，那么他穿上。如果有人穿，DFS换衣服，结果让那个人穿上衣服，其他人该换的换。如果都不行，就是匹配失败了。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <ctype.h>
#define INF 1000000000
using namespace std;bool G[40][40];
int match[40];
bool chk[40];
int n,m;int sizetoint(string str){if(str=="XS")return 1;if(str=="S")return 2;if(str=="M")return 3;if(str=="L")return 4;if(str=="XL")return 5;if(str=="XXL")return 6;return 0;
}bool dfs(int u){for(int i=1;i<=n;i++){if(!chk[i]&&G[u][i]){chk[i]=true;int tmp=match[i];match[i]=u;if(tmp==-1||dfs(tmp)){return true;}match[i]=tmp;}}return false;
}int main(){int t;cin>>t;while(t--){memset(G,0,sizeof(G));for(int i=0;i<40;i++)match[i]=-1;cin>>n>>m;int nn=n/6;string str1,str2;//建图 for(int i=1;i<=m;i++){cin>>str1>>str2;for(int j=1;j<=nn;j++){G[i][(sizetoint(str1)-1)*nn+j]=1;G[i][(sizetoint(str2)-1)*nn+j]=1;}}int ans=0;for(int i=1;i<=m;i++){memset(chk,0,sizeof(chk));if(dfs(i))ans++;}if(ans==m){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}
这篇关于UVa11045 My T-shirt suits me的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
