FAFU-1198 小三大作战 多重匹配

本文主要是介绍FAFU-1198 小三大作战 多重匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.fafu.edu.cn/problem.php?id=1198

#include "stdio.h"
#include "string.h"
const int maxn = 105;
int map[maxn][maxn],cap[maxn],data[maxn][maxn],flow[maxn];;
int n,m;
bool vis[maxn];
bool dfs(int x)
{for( int i=1; i<=m; i++ )  //遍历每个GG{if( map[i][x] && !vis[i] )  //iGG想保养xMM {vis[i] = true;if( cap[i] > flow[i] )  //流量小于容量 {data[i][++flow[i]] = x;  //记录return true;}else                    //如果iGG保养满了 就遍历iGG已保养的MM是否还能被其他GG保养{for( int j=1; j<=flow[i]; j++ )  //遍历iGG已保养的MM{if( dfs( data[i][j] ) )   //{data[i][j] = x;return true;}}}}}return false;
}int fun()
{memset(flow,0,sizeof(flow)); //记录每个GG保养了几个MMint ans = 0;for( int i=1; i<=n; i++ )   //遍历每个MM{memset(vis,0,sizeof(vis));if( dfs(i) )ans++;}return ans;
}int main()
{int i,j;while( scanf("%d%d",&n,&m)==2 ){for( i=1; i<=m; i++ ){scanf("%d",&cap[i]);}for( i=1;i<=m;i++ ){for( j=1;j<=n;j++ )scanf("%d",&map[i][j]);}printf("%d\n",fun());}
}

这篇关于FAFU-1198 小三大作战 多重匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---