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

Re:为什么会错呢?搞不懂,哪位大侠帮着看看!谢谢!

Posted by lyf_2009 at 2011-06-16 18:57:58 on Problem 1904
In Reply To:为什么会错呢?搞不懂,哪位大侠帮着看看!谢谢! Posted by:lyf_2009 at 2011-06-16 18:56:59
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;


const int M = 4010;
bool vis[M];
int idx;
int Stop;
int n;
vector<int> table[M], marriage[2010];
bool isInStack[M];
int low[M];
int dfn[M];
int stack[M];

#define  min(a, b) ((a)<(b)?(a):(b))

void tarjan(int u)
{
   if (vis[u])
       return;
   vis[u] = true;
   stack[Stop++] = u;
   isInStack[u] = true;
   low[u] = dfn[u] = idx++;
   int i, v;
   int size = table[u].size();
   for (i = 0; i < size; i++)
   {
	   v = table[u][i];
      if (!vis[v])
      {
          tarjan(v);
          low[u] = min(low[u], low[v]);
      }
      else if (isInStack[v])
          low[u] = min(low[u], dfn[v]);
   }
   if (dfn[u] == low[u])
   {
       vector<int> son, girl;
       int person;
       do
       {
          person = stack[--Stop];
          isInStack[person] = false;
          if (person <= n)
             son.push_back(person);
          else
             girl.push_back(person);
       }while (u != person);
       int i, j, k;
       for (i = 0; i < son.size(); i++)
       {
          k = son[i];
          for (j = 0 ; j < girl.size(); j++)
          {
              marriage[k].push_back(girl[j]);
          }
       }
   }
}

void initialize()
{
    idx = 0;
    Stop = 0;
    memset(vis, 0, sizeof(vis));
    memset(isInStack, 0, sizeof(isInStack));
}


int main()
{
   int i, j, girl, num;
   scanf("%d", &n);
   initialize();
   for (i = 1; i <= n; i++)
   {
      scanf("%d", &num);
      for (j = 0; j < num; j++)
      {
         scanf("%d", &girl);
         table[i].push_back(girl+n);
      }
   }
   for (i = 1; i <= n; i++)
   {
      scanf("%d", &girl);
      table[girl + n].push_back(i);
   }
   for (i = 1; i <= 2*n; i++)
     tarjan(i);
   for (i = 1; i <= n; i++)
   {
      sort(marriage[i].begin(), marriage[i].end());
      int size = marriage[i].size();
      printf("%d", size);
      for (j = 0; j < size; j++)
         printf(" %d", marriage[i][j]-n);
      printf("\n");
   }
   return 0;
}

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