莱城高新区建设局网站,免费建设com网站,长泰县建设局网站,开发公司总经理管理方案题目地址#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid1054 简单二分匹配#xff0c;根据题意构造一个无向图。然后求最小点覆盖#xff0c;然后扫描mark数组将曾经匹配的点所匹配的边消去。 最小点覆盖 最大二分匹配 #includestdio.h
#includestrin…题目地址http://acm.hdu.edu.cn/showproblem.php?pid1054 简单二分匹配根据题意构造一个无向图。然后求最小点覆盖然后扫描mark数组将曾经匹配的点所匹配的边消去。 最小点覆盖 最大二分匹配 #includestdio.h
#includestring.h
#define maxn 1505
struct node
{int v;node *next;
}*head[maxn],edge[maxn*maxn],*p;
int n,vis[maxn],mark[maxn];
bool dfs(int v)
{for(node *p head[v]; p ; p p-next){if(vis[p-v])continue;vis[p-v] 1;if(mark[p-v] -1 || dfs(mark[p-v])){mark[p-v] v;return true;}}return false;
}
int main()
{int num,v,u,i,j;while(scanf(%d,n) ! EOF){memset(head,NULL,sizeof(head));p edge;for(i 0; i n; i){scanf(%d:(%d),u,num);for(j 0; j num; j){scanf(%d,v);p-v v;p-next head[u];head[u] p;p-v u;p-next head[v];head[v] p;}}memset(mark,-1,sizeof(mark));int ans 0;for(i 0; i n; i){memset(vis,0,sizeof(vis));if(dfs(i))ans;}//减去已有的边。。。for(i 0; i n; i){if(mark[i] ! -1){for(j i1; j n; j)if(mark[j] i){mark[j] -1;ans--;}}}printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/LUO257316/archive/2012/09/08/3220833.html
