首页 > 代码库 > UVALive 5962 Strongly Connected Chemicals --最大独立集
UVALive 5962 Strongly Connected Chemicals --最大独立集
题意：给n个阳离子和m个阴离子，并给出相互的吸引关系，求一个最大的点集，使其中的每个阴阳离子相互吸引。
解法：枚举每条边，使该条边存在，然后建立反图，求一个最大匹配，此时的点数减去最大匹配与ans求一个最大值即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <stack>using namespace std;#define N 207int G[N][N],G2[N][N];int match[N];int vis[N];char ss[N][N];int n,m;int Search_Path(int s){ for(int v=0;v<m;v++) { if(G[s][v] == 0) continue; if(!vis[v]) { vis[v] = 1; if(match[v] == -1 || Search_Path(match[v])) { match[v] = s; return 1; } } } return 0;}int Max_match(){ memset(match,-1,sizeof(match)); int cnt = 0; for(int i=0;i<n;i++) { memset(vis,0,sizeof(vis)); if(Search_Path(i)) cnt++; } return cnt;}int main(){ int t,cs = 1,i,j,k,h; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) { scanf("%s",ss[i]); for(j=0;j<m;j++) G[i][j] = ss[i][j] - ‘0‘; } int ans = 0; for(i=0;i<n;i++) //枚举边 { for(j=0;j<m;j++) { if(G[i][j]) { int cntn = 0; int cntm = 0; for(k=0;k<n;k++) if(G[k][j]) cntn++; for(h=0;h<m;h++) if(G[i][h]) cntm++; for(k=0;k<n;k++) { for(h=0;h<m;h++) { if(G[k][j]&&G[i][h]) G2[k][h] = 1-G[k][h]; else G2[k][h] = 0; } } ans = max(ans,cntn+cntm-Max_match()); } } } printf("Case %d: %d\n",cs++,ans); } return 0;}
UVALive 5962 Strongly Connected Chemicals --最大独立集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。