题意：就6种型号的衣服，然后给你n件衣服，n一定是6的倍数，也就是每种类型的衣服的件数是一样的，然后给m个人，每个人能穿两种型号的衣服，给你每个人穿衣的信息，然后判断是否每个人都能找到衣服穿
很显然是二分图最大匹配，但是这里有个小问题，就是一种衣服有多件，可能被多个人穿，和二分图匹配有点不同，在最大匹配中每个点是只会出现一次的，这个问题要解决不难就是把相同的衣服拆成多件不同的衣服处理，但是建图的时候就要注意多处理一下,建图完毕后就是纯粹的匈牙利算法
//问题一看就是二分图匹配，不过一个种衣服会有多件要怎么处理呢，就把多件相同类型的衣服当做不同衣服来处理 //衣服按照1到6编号，如果第i种衣服有重复的，那么重复的衣服就是i+6，如果再有重复的，就是i+6+6 //另外，一个员工能穿第i中衣服，不能单单建一条边到i，要建多条边同时指向i，i+6，i+6+6，…… //然后就是裸露的无向图匈牙利算法匹配 #include <cstdio> #include <cstring> #define N 70 int g[N][N]; //无向图邻接表 int mat[N],vis[N]; int n,m,nn; char shirt[7][4]={"","XXL","XL","L","M","S","XS"};void input() {memset(g,0,sizeof(g));scanf("%d%d",&n,&m);nn=n/6;for(int i=1; i<=m; i++){char s1[5],s2[5];int t1,t2;scanf("%s%s",s1,s2);for(int j=1; j<=6; j++)if(!strcmp(s1,shirt[j])){ t1=j; break;}for(int j=1; j<=6; j++)if(!strcmp(s2,shirt[j])){ t2=j; break;}//printf("%d %d\n",t1,t2);int u,v1,v2;u=n+i; //当前员工的标号，我们约定前面n号全部留给衣服v1=t1; //第一种型号的衣服v2=t2; //第二种型号的衣服for(int c=0; c<nn;c++) {int t;t=++g[u][0]; g[u][t]=v1+6*c; //建立边<u,v1+6*c>t=++g[v1+6*c][0];g[v1+6*c][t]=u; //建立边<v1+6*c,u>//第一件衣服的无向边建立完成t=++g[u][0];g[u][t]=v2+6*c; //建立边<u,v2+6*c>t=++g[v2+6*c][0];g[v2+6*c][t]=u; //建立边<v2+6*c,u>//第一件衣服的无向边建立完成 }} /*for(int i=1; i<=n+m; i++){printf("%d:",i);for(int j=1; j<=g[i][0]; j++)printf(" %d",g[i][j]);printf("\n");} */return ;}int find(int u) {for(int i=1; i<=g[u][0]; i++){int v=g[u][i];if(!vis[v]){vis[v]=1;if(!mat[v] || find(mat[v])){mat[v]=u;return 1;}}}return 0; } void max_match() {int ans=0;memset(mat,0,sizeof(mat));for(int i=1; i<=n+m; i++){memset(vis,0,sizeof(vis));ans+=find(i);}for(int i=1; i<=n+m; i++)printf("%d ",mat[i]);printf("\n");printf("ans=%d\n",ans);int flag=1;for(int i=n+1; i<=n+m; i++)if(!mat[i]){ flag=0; break;}if(flag)printf("YES\n");elseprintf("NO\n"); }int main() {int T;scanf("%d",&T);while(T--){input();max_match();}return 0; }
当然如果理解了匈牙利算法的增广路本质后，是可以转化为最大流来做的，其实就是算法导论里面说的，加一个源点，，源点发射n条边指向L集合的每一个顶点，然后加一个汇点，R集合的m个元素发射m条边全部指向汇点，原本L和R之间的边保持不变，就转化成最大流来解决了