Main » 2013 October 11 » [模拟赛NOIP2010]合成
9:24 AM [模拟赛NOIP2010]合成 |
想了半天，越看越像二分图ps:就是二分图，傻了#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 100010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int pre[N],last[N],e[N],size[N],n,len=0,V[N],d[N]; void add(int x,int y) { pre[++len]=last[x]; last[x]=len;e[len]=y; size[x]++; } int DFS(int x) { int pos=last[x],i; FOR(i,1,size[x]) { int y=e[pos]; if (!V[y]) { V[y]=1; if (d[y]==-1||DFS(d[y])) {d[y]=x;return 1;} } pos=pre[pos]; } return 0; } int main() { scanf("%d",&n); int i,j; FOR(i,1,n) { int u,v,Len; scanf("%d",&u); scanf("%d",&Len); FOR(j,1,Len) { scanf("%d",&v); add(u,v);add(v,u); } } memset(d,0xff,sizeof(d)); int ans=0; FOR(i,1,n) { memset(V,0,sizeof(V)); if (DFS(i)) ans++; } ans/=2; printf("%d\n",ans); } |
|
|
| Total comments: 0 | |