【poj1274】 The Perfect Stall

http://poj.org/problem?id=1274 (题目链接)

题意

  懒得写了

Solution

  二分图匹配裸题。注意清空数组。

代码

// poj3020
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi 3.1415926535898
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=500;
struct edge {int next,to;}e[maxn<<2];
int head[maxn],p[maxn],vis[maxn],cnt,n,m; void insert(int u,int v) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
bool find(int x) {
for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) {
vis[e[i].to]=1;
if (p[e[i].to]==0 || find(p[e[i].to])) {
p[e[i].to]=x;
return 1;
}
}
return 0;
}
int main() {
while (scanf("%d%d",&n,&m)!=EOF) {
for (int i=1;i<=n;i++) p[i]=head[i]=0;
cnt=0;
for (int i=1;i<=n;i++) {
int x;scanf("%d",&x);
for (int j=1;j<=x;j++) {
int t;scanf("%d",&t);
insert(i,t);
}
}
int ans=0;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) vis[j]=0;
if (find(i)) ans++;
}
printf("%d\n",ans);
}
return 0;
}

  

上一篇:JAVA编程思想读书笔记(四)--对象的克隆


下一篇:Asp.Net 验证控件