| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么会wrong answer求助#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];
vector < int > adj[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);
adj[i].push_back(i+N+D+F+1);
cn[i][i+N+D+F+1]=1;
for (int j = 0 ; j != fs ; ++j)
{
int a;
scanf("%d",&a);
adj[a+N].push_back(i);
adj[i].push_back(a+N);
cn[a+N][i]=oo;
}
for (int j = 0 ; j != ds ; ++j)
{
int a;
scanf("%d",&a);
adj[i+N+D+F+1].push_back(a+N+F);
adj[a+N+F].push_back(i+N+D+F+1);
cn[i+N+D+F+1][a+N+F]=oo;
}
}
for (int i = N+1; i <=F+N;++i)
{
adj[stp].push_back(i);
adj[i].push_back(stp);
cn[stp][i]=1;
}
for (int i = F+N+1; i <=F+N+D;++i)
{
adj[i].push_back(enp);
adj[enp].push_back(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)
{
int y =adj[h][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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator