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; }