Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Posted by HHHBBB at 2014-07-26 19:22:58 on Problem 3281
```#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

#define maxn 1005
#define oo 999999999

int ans,N,F,D,cn[maxn][maxn],stp,enp,fa[maxn];
bool vis[maxn];
queue < int > q;

void in();
void work();
void out();
bool bfs();

int main()
{

// freopen("poj3281.in","r",stdin);
// freopen("poj3281.out","w",stdout);

in();
work();
out();

return 0;
}

void in()
{
scanf("%d%d%d",&N,&F,&D);
stp=0;enp=N+F+D+1;
for (int i = 1 ; i <= N ; ++i)
{
int fs,ds;
scanf("%d%d",&fs,&ds);
cn[i][i+N+D+F+1]=1;
for (int j = 0 ; j != fs ; ++j)
{
int a;
scanf("%d",&a);
cn[a+N][i]=oo;
}
for (int j = 0 ; j != ds ; ++j)
{
int a;
scanf("%d",&a);
cn[i+N+D+F+1][a+N+F]=oo;
}
}
for (int  i = N+1; i <=F+N;++i)
{
cn[stp][i]=1;
}
for (int  i = F+N+1; i <=F+N+D;++i)
{
cn[i][enp]=1;
}
}

void work()
{
while (bfs() == true)
{
int minf=oo;
for (int u = enp ; fa[u] != -1 ; u=fa[u])
minf=min(minf,cn[ fa[u] ][u]);
for (int u = enp ; fa[u] != -1 ; u=fa[u])
{
cn[ fa[u] ][u]-=minf;
cn[u][ fa[u] ]+=minf;
}
ans+=minf;
}
}

void out()
{
printf("%d\n",ans);
}

bool bfs()
{
while ( !q.empty() ) q.pop();
memset(vis,false,sizeof(vis));
q.push(stp);
vis[stp]=true;
fa[stp]=-1;
for ( ;!q.empty() ;q.pop() )
{
int h =q.front();
for (int i = 0 ; i != adj[h].size() ; ++i)
{
if (vis [y] || cn[h][y]==0 ) continue;
vis[y]=true;
q.push(y);
fa[y]=h;
if ( y == enp)
return true;
}
}
return false;
}
```

Followed by: