|
|
Posted on 2010-10-02 22:25 成幸毅 阅读(137) 评论(0) 编辑 收藏 引用
求最大匹配，不解释。
 #include <iostream>
#include <queue>
using namespace std;
const int MAXN = 500;
const int INF = 0x7fffffff;
int n,m;
int p,s,t;
int u;
int c[MAXN][MAXN],num[MAXN],pre[MAXN],d[MAXN];
  void ini_d(int s,int t)  {
memset(d,1,sizeof(d));
memset(num,0,sizeof(num));
queue<int> Q;
Q.push(t);
d[t] = 0;
int k ;
num[0] = 1;
  while(!Q.empty()) {
k = Q.front();Q.pop();
for(int i = 0; i <= t; i++) {
if(c[i][k] > 0 && d[i] > t) {
d[i] = d[k] + 1;
Q.push(i);
num[d[i]]++;
 }
}
}
 }
int findAlowArc(int i) {
int j;
for(j = 0; j <= t; j++) {
if(c[i][j] > 0 && d[i] == d[j] + 1)
return j;
}
return -1;
}
int reLable(int i) {
int j;
int mm = INF;
for(j = 0; j <= t; j++) {
if(c[i][j] > 0) mm = min(mm,d[j]+1);
}
return mm == INF?t+1:mm;
}
int maxFlow(int s,int t) {
ini_d(s,t);
memset(pre,-1,sizeof(pre));
int flow = 0,i = s,j;
int delta;
while(d[s] <= t) {
j = findAlowArc(i);
if(j >= 0) {
pre[j] = i;
i = j;
if(i == t) {
delta = INF;
for(i = t; i != s; i = pre[i]) delta = min(delta,c[pre[i]][i]);
for(i = t; i != s; i = pre[i])
c[pre[i]][i] -= delta, c[i][pre[i]] += delta;
flow += delta;
}
}
else {
int x = reLable(i);
num[x]++;
num[d[i]]--;
if(num[d[i]] == 0) return flow;
d[i] = x;
if(i != s) i = pre[i];
}
}
return flow;
}
int main() {
while(EOF != scanf("%d%d",&n,&m)) {
s = 0,t = n + m + 1;
memset(c,0,sizeof(c));
for(int i = 1; i <= n; i++) {
scanf("%d",&p);
for(int j = 0; j < p; j++) {
scanf("%d",&u);
c[i][u+n] = 1;
c[s][i] = 1;
c[u+n][t] = 1;
}
}
int ans = maxFlow(s,t);
printf("%d\n",ans);
}
// system("pause");
return 0;
}
|