http://acm.pku.edu.cn/JudgeOnline/problem?id=1274二分最大匹配
最大流用 匈牙利 或者最大流（建圖 源點(diǎn)s連上所有的牛，所有的棚連上匯點(diǎn)t）
#include<iostream>
using namespace std;
#define MAXN 201
int uN, vN; // u,ｖ數(shù)目
bool g[MAXN][MAXN]; // g[i][j] 表示 xi與yj相連
int xM[MAXN], yM[MAXN]; // 輸出量
bool chk[MAXN]; // 輔助量 檢查某輪 y[v]是否被check
bool SearchPath( int u)
{
int v;
for (v = 0 ; v < vN; v ++ ){
if (g[u][v] && ! chk[v]){
chk[v] = true ;
if (yM[v] == - 1 || SearchPath(yM[v])){
yM[v] = u;
xM[u] = v;
return true ;
}
}
}
return false ;
}
int MaxMatch()
{
int u;
int ret = 0 ;
memset(xM, - 1 , sizeof (xM));
memset(yM, - 1 , sizeof (yM));
for (u = 0 ; u < uN; u ++ ){
if (xM[u] == - 1 ){
memset(chk, false , sizeof (chk));
if (SearchPath(u)) ret ++ ;
}
}
return ret;
}
int main()
{
while(scanf("%d%d",&uN,&vN)!=EOF) {
int i,j;
memset(g,0,sizeof(g));
for(i=0;i<uN;i++) {
int a,b;
scanf("%d",&a);
for(j=0;j<a;j++){
scanf("%d",&b);
g[i][b-1]=1;
}
}
printf("%d\n",MaxMatch());
}
return 0;
}
#include<iostream>
using namespace std;
#define MAXN 410
#define inf 2100000000
//傳入網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n,容量mat,源點(diǎn)source,匯點(diǎn)sink
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
else if (!pre[i]&&(j=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
for (j=i=0;i<n;j+=flow[source][i++]);
return j;
}
int mat[MAXN][MAXN],flow[MAXN][MAXN];
int main()
{
int n,m;
int s,t;
int k,a,b;
while(scanf("%d%d",&n,&m)!=EOF){
memset(mat,0,sizeof(mat));
memset(flow,0,sizeof(flow));
for(int i=1;i<=n;i++){
mat[0][i]=1;
}// s->1--n
for(int i = n+1;i <= n+m;i++){
mat[i][n+m+1]=1;
}//(n+1)--(n+m)->t
for(int i=1;i<=n;i++){
scanf("%d",&k);
for(int j=0;j<k;j++){
scanf("%d",&a);
mat[i][n+a]=1;
}
}
printf("%d\n",max_flow(n+m+2,mat,0,n+m+1,flow));
}
return 0;
}
posted on 2009-02-15 16:18
爬 閱讀(1156)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
pku