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

为什么会wrong answer求助

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];
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator