二部图问题:每个任务的两种模式对应一条边,那么最大的匹配数就是最多的任务不用改变模式的任务数。
相当于求最小点覆盖,而最小点覆盖= 最大匹配数
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define MAXN 110 int uN,vN; int map[MAXN][MAXN]; int link[MAXN]; bool used[MAXN]; bool dfs(int u) { int v; for(v=0; v<vN; v++) if(map[u][v]&&!used[v]) { used[v]=1; if(link[v]==-1||dfs(link[v])) { link[v]=u; return 1; } } return 0; } int bfs() { int res=0; int u; memset(link,-1,sizeof(link)); for(u=0; u<uN; u++) { memset(used,0,sizeof(used)); if(dfs(u)) res++; } return res; } int main() { int k; int i,u,v; while(scanf("%d",&uN),uN) { scanf("%d%d",&vN,&k); memset(map,0,sizeof(map)); while(k--) { scanf("%d%d%d",&i,&u,&v); if(u>0&&v>0)map[u][v]=1; } printf("%d\n",bfs()); } return 0; }