题意:有男孩和女孩，男孩之间全部认识，女孩之间全部认识，一部分男孩和女孩认识，现在希望选出一些孩子，这些孩子都相互认识。
方法:正的做不好做，观察他的补图，补图之间无关系的边就是原图有关系的。补图中的独立集不正是相互都没有连边么，反过来说，它们在原图中不正是两两都有连边么。
最小割：
#include<stdio.h> #include<string.h> #include<queue> #define INF 99999999 using namespace std; const int maxn = 450; struct node { int to; int v; int flag; int next; }edge[210*210]; int pre[maxn],index,vis[maxn],S,T,map[maxn][maxn]; void add(int x,int y,int z) { edge[index].to=y; edge[index].v=z; edge[index].flag=index+1; edge[index].next=pre[x]; pre[x]=index++; edge[index].to=x; edge[index].v=0; edge[index].flag=index-1; edge[index].next=pre[y]; pre[y]=index++; } int dfs(int u,int low) { int i,used=0; if(u==T) return low; for(i=pre[u];i!=-1&&used<low;i=edge[i].next) { if(vis[edge[i].to]==vis[u]+1&&edge[i].v) { int a=dfs(edge[i].to,min(low-used,edge[i].v)); edge[i].v-=a; edge[edge[i].flag].v+=a; used+=a; } } if(!used) vis[u]=-1; return used; } int BFS() { int i; queue<int>q; memset(vis,-1,sizeof(vis)); vis[0]=1; q.push(0); while(!q.empty()) { int t=q.front(); q.pop(); for(i=pre[t];i!=-1;i=edge[i].next) { if(vis[edge[i].to]<0&&edge[i].v) { vis[edge[i].to]=vis[t]+1; q.push(edge[i].to); } } } if(vis[T]>0) return 1; return 0; } int main() { int i,j,n,m,k,ft=0; while(~scanf("%d%d%d",&n,&m,&k)) { if(!n&&!m&&!k) break; memset(map,0,sizeof(map)); memset(pre,-1,sizeof(pre)); index=1; S=0,T=n+m+1; for(i=1;i<=n;i++) { add(0,i,1); for(j=1;j<=n;j++) { if(i==j)continue; map[i][j]=1; } } for(i=1;i<=m;i++) { add(i+n,T,1); for(j=1;j<=m;j++) { if(i==j)continue; map[i+n][j+n]=1; } } for(i=0;i<k;i++) { int x,y; scanf("%d%d",&x,&y); map[x][y+n]=1; } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(!map[i][j+n]) add(i,j+n,INF); } } int ans=0; while(BFS()) { while(1) { int a=dfs(0,INF); if(!a)break; ans+=a; } //printf("1"); } printf("Case %d: %d ",++ft,n+m-ans); } }
二分匹配:
#include<stdio.h> #include<string.h> #include<queue> #define INF 99999999 using namespace std; const int maxn = 450; int match[maxn],vis[maxn],map[maxn][maxn]; int dfs(int u,int m) { int i,j; for(i=1;i<=m;i++) { if(!vis[i]&&!map[u][i]) { vis[i]=1; if(match[i]==-1||dfs(match[i],m)) { match[i]=u; return 1; } } } return 0; } int main() { int i,j,n,m,k,ft=0; while(~scanf("%d%d%d",&n,&m,&k)) { if(!n&&!m&&!k) break; memset(match,-1,sizeof(match)); memset(map,0,sizeof(map)); for(i=0;i<k;i++) { int x,y; scanf("%d%d",&x,&y); map[x][y]=1; } int ans=0; for(i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i,m)) ans++; } printf("Case %d: %d ",++ft,n+m-ans); } }