| My T-shirt suits me |
Our friend Victor participates as an instructor in an environmental volunteer
program. His boss asked Victor to distribute N T-shirts to M volunteers, one T-shirt each volunteer,
where N is multiple of six,
and N
M.
There are the same number of T-shirts of each one of the six available sizes:
XXL, XL, L, M , S, and XS. Victor has a little problem because only two sizes of
the T-shirts suit each volunteer.
You must write a program to decide if Victor can distribute T-shirts in
such a way that all volunteers get a T-shirt that suit them. If N 
M, there can be some remaining
T-shirts.
The first line of the input contains the number of test cases. For each test
case, there is a line with two numbers N and M. N is multiple of 6, 1
N36,
and indicates the number of T-shirts. Number M, 1M30,
indicates the number of volunteers, with NM. Subsequently, M lines are listed where each line contains,
separated by one space, the two sizes that suit each volunteer (XXL, XL, L, M ,
S, or XS).
For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.
3 18 6 L XL XL L XXL XL S XS M S M L 6 4 S XL L S L XL L XL 6 1 L M
YES NO YES
二分图匹配问题，将志愿者和就服匹配起来
直接套用匈牙利算法模板即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<vector> 6 #define MAX_V 80 7 8 using namespace std; 9 10 int V; 11 int n,m; 12 int match[MAX_V]; 13 bool used[MAX_V]; 14 vector<int> G[MAX_V]; 15 16 void add_edge(int u,int v) 17 { 18 G[u].push_back(v); 19 G[v].push_back(u); 20 } 21 22 bool dfs(int v) 23 { 24 used[v]=true; 25 26 for(int i=0;i<G[v].size();i++) 27 { 28 int u=G[v][i],w=match[u]; 29 if(w<0||(!used[w]&&dfs(w))) 30 { 31 match[v]=u; 32 match[u]=v; 33 return true; 34 } 35 } 36 37 return false; 38 } 39 40 int bipartite_matching() 41 { 42 int res=0; 43 44 memset(match,-1,sizeof(match)); 45 46 for(int v=1;v<=V;v++) 47 { 48 if(match[v]<0) 49 { 50 memset(used,false,sizeof(used)); 51 if(dfs(v)) 52 res++; 53 } 54 } 55 56 return res; 57 } 58 59 int main() 60 { 61 int kase; 62 63 scanf("%d",&kase); 64 65 while(kase--) 66 { 67 scanf("%d %d",&n,&m); 68 69 V=n+m; 70 for(int i=1;i<=V;i++) 71 G[i].clear(); 72 73 string s1,s2; 74 for(int i=1;i<=m;i++) 75 { 76 cin>>s1>>s2; 77 if(s1=="XXL"||s2=="XXL") 78 for(int j=1;j<=n/6;j++) 79 add_edge(j,n+i); 80 if(s1=="XL"||s2=="XL") 81 for(int j=n/6+1;j<=n/3;j++) 82 add_edge(j,n+i); 83 if(s1=="L"||s2=="L") 84 for(int j=n/3+1;j<=n/2;j++) 85 add_edge(j,n+i); 86 if(s1=="M"||s2=="M") 87 for(int j=n/2+1;j<=n*2/3;j++) 88 add_edge(j,n+i); 89 if(s1=="S"||s2=="S") 90 for(int j=n*2/3+1;j<=n*5/6;j++) 91 add_edge(j,n+i); 92 if(s1=="XS"||s2=="XS") 93 for(int j=n*5/6+1;j<=n;j++) 94 add_edge(j,n+i); 95 } 96 97 if(bipartite_matching()==m) 98 puts("YES"); 99 else 100 puts("NO"); 101 } 102 103 return 0; 104 }
原文：http://www.cnblogs.com/lzj-0218/p/3560576.html
