Информатика и математика

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Информатика и математика » Байт решений задач с acm.pku » acm.pku 1236 Network of Schools


acm.pku 1236 Network of Schools

Сообщений 1 страница 2 из 2

1

http://acm.pku.edu.cn/JudgeOnline/problem?id=1236

Задача Межшкольная сеть

   Некоторые школы связаны компьютерной сетью. Между школами заключены соглашения: каждая школа имеет список школ-получателей, которым она рассылает программное обеспечение всякий раз, получив новое программное обеспечение (извне сети или из другой школы). При этом, если школа В есть в списке получателей школы А, то школа А может и не быть в списке получателей школы В.

   Требуется написать программу, определяющую минимальное количество школ, которым надо передать по экземпляру нового программного обеспечения, чтобы распространить его по всем школам сети в соотвествии с соглашением (подзадача А).

   Кроме того, надо обеспечить возможность рассылки нового программного обеспечения из любой школы по всем остальным школам. Для этого можно расширять списки получателей некоторых школ, добавляя в них новые школы. Требуется найти минимальное суммарное количество расширений списков, при которых программное обеспечение из любой школы достигло бы всех остальных школ (подзадача В). Одно расширение означает добавление одной новой школы-получателя  в список получателей одной из школ.

   Технические условия.  Входные данные: Первая строка содержит целое число N - количество школ в сети (2 <= N <= 100). Школы нумеруются первыми N положительными целыми числами. Каждая из следующих N строк задает список получателей. Строка i+1 содержит номера получателей i-й школы. Каждый такой список заканчивается нулем. Пустой список содержит только нуль.

   Выходные данные: Ваша программа должна вывести две строки. Первая строка должна содержать одно положительное целое число - решение подзадачи А. Вторая строка должна содержать решение подзадачи В.

   Пример входных данных:

5
2 4 3 0
4 5 0
0
0
1 0

   Пример выходных данных:

1
2

   Обсуждение задачи

   Для решения задачи требуется знание фундаментального математического понятия "отношение" и, соответственно, понятия "замкнутость отношения". Кратко рассмотрим их.

   Бинарным отношение R двух множеств А и В называют подмножество прямого произведения А и В. Прямое (декартовое) произведение двух множеств А и В есть множество упорядоченных пар, в котором первый элемент каждой пары принадлежит А, а второй принадлежит В. Если А = В, то говорят, что R есть отношение на множестве А.

   Отношение R обладает обычно рядом свойств. Так, оно обладает свойством транзитивности, если для любых элементов a, b, c, принадлежащих А, из a R b и b R c следует, что a R c. Словами это проговаривается так: если a и b находятся в отношении R и b и c находятся в отношении R, то пара a и c также находятся в отношении R.

   Неформально говоря, замкнутость отношения относительно некоторого свойства означает, что многократное его применение не выводит нас за определенные границы. Задачу же нахождения по транзитивному отношению R отношения R*, обладающего свойством замкнутости, называют задачей замыкания, а отношение R* - транзитивным замыканием R.

   Для более детального ознакомления с решением, базирующимся на данном подходе, рекомендуем всем желающим обратиться к книге Кирюхин В.М., Окулов С.М. "Методика решения задач по информатике. Международные олимпиады", - М.: БИНОМ. Лаборатория знаний, 2007. - 600 с.: ил., где этот подход применительно к этой задаче детально разобран на стр. 148-154.

   Мы же приведем 2 других решения, одно из которых базируется на алгоритме Флойда-Уоршелла, а второе на понятии доминирующих множеств, с которыми рекомендуем разобраться самостоятельно.

Код:
var a,b,floyd,ad:array[1..100,1..100]of byte;
    fdi,fde,di,de:array[1..100]of byte;
    i,x,y,nr,min,nrcomp,nrext,j,k,l,m,n,nrctc:longint;
    luate:set of byte;
    bb:boolean;
    ctc:array[1..100]of set of byte;
    ss:string;

procedure dofloyd;
var i,j,k:byte;
begin
  for k:=1 to n do
      for i:=1 to n do
          for j:=1 to n do
              if floyd[i,k]+floyd[k,j]=2 then floyd[i,j]:=1;
  for i:=1 to n do
      for j:=1 to n do
          if a[i,j]=1 then
             begin
               inc(fdi[j]);
               inc(fde[i]);
             end;
end;

procedure calcctc;
begin
  b:=a;
  floyd:=a;
  dofloyd;
  a:=floyd;
  for i:=1 to n do
      for j:=1 to n do
          if a[i,j]+a[j,i]=1 then
             begin
               a[i,j]:=0;
               a[j,i]:=0;
             end;
  nrctc:=0;
  luate:=[];
  for i:=1 to n do
      if not(i in luate) then
      begin
        inc(nrctc);
        ctc[nrctc]:=[i];
        for j:=1 to n do
            if a[i,j]=1 then
               ctc[nrctc]:=ctc[nrctc]+[j];
        luate:=luate+ctc[nrctc];
      end;
  a:=b;
  for i:=1 to nrctc do
      for j:=1 to nrctc do
          if i<>j then
             for k:=1 to n do
                 if k in ctc[i] then
                    for l:=1 to n do
                        if l in ctc[j] then
                           if a[k,l]=1 then
                              ad[i,j]:=1;
end;

begin
  readln(n);
  nrcomp:=0;
  for i:=1 to n do
      begin
        read(j);
        while j<>0 do
          begin
            a[i,j]:=1;
            inc(de[i]);
            inc(di[j]);
            read(j);
          end;
      end;
  fillchar(ad,sizeof(ad),0);
  calcctc;
  for i:=1 to nrctc do
      begin
        di[i]:=0;de[i]:=0;
        for j:=1 to nrctc do
            if ad[i,j]=1 then inc(de[i]);
        for j:=1 to nrctc do
            if ad[j,i]=1 then inc(di[i]);
      end;
  k:=0;l:=0;
  for i:=1 to nrctc do
      if (di[i]=0)and(de[i]<>0)then inc(k);
  for i:=1 to nrctc do
      if (de[i]=0)and(di[i]<>0)then inc(l);
  for i:=1 to nrctc do
      if de[i]+di[i]=0 then begin inc(k);inc(l);end;
  m:=k;
  if l>k then k:=l;
  if nrctc=1 then
  k:=0;
  writeln(m);
  writeln(k);
end.
Код:
Const MaxN=200;           { max number of schools }
Type
  GraphType=Array[1..MaxN,0..MaxN] Of 0..MaxN;
  VertexSet=Set Of 1..MaxN;
Var
  N :Word;            { the number of schools }
  G: GraphType;       { representation of the network with graph G; }
                      { G[p,0] is the number of edges outgoing from p }
                      { the outgoing edges from p: (p, G[p,i]) 1<=i<=G[p,0]) }
  Domin,              { dominator set }
  CoDomin: VertexSet; { codominator set }
  NoDomins,           { number of dominator elements   }
  NoCoDomins: 0..MaxN;{ number of codominator elements }
  AnswerB: 0..MaxN;   { solution of subtask B }
  p: 0..MaxN;

Procedure ReadInput;
{ Global output variables: N, G }
  Var i,p: Word;
  Begin
    ReadLn(N);

    For i:=1 To N Do
      G[i,0]:=0;
    For i:=1 To N Do Begin
      Read(p);
      While p<>0 Do Begin
        Inc(G[i,0]);
        G[i,G[i,0]]:=p;
        Read(p);
      End;
      ReadLn;
    End;

End { ReadInput };

Procedure ComputeDomin(Const G: GraphType; Var D: VertexSet);
{ Computes a minimal dominator set D of graph G }
{ Global input variables: N }
  Var
    Dominated, Reachable: Set of 1..MaxN;
    p: 1..MaxN;

  Procedure Search(p:Word);
    Var i: Word;
  Begin
    Exclude(D, p);
    Include(Dominated, p);
    For i:= 1 To G[p,0] Do
      If Not (G[p,i] in Reachable) Then Begin
        Include(Reachable,G[p,i]);
        Search(G[p,i]);
      End;
  End { Search };

  Begin { ComputeDomin }
    D:=[];
    Dominated:=[];
    For p:=1 To N Do
      If Not (p In Dominated) Then Begin
        Reachable:=[p];
        Search(p);
        Include(D, p);
      End;
  End { ComputeDomin };

Procedure ComputeCoDomin(Const G: GraphType; Var CD: VertexSet);
{ Computes a minimal codominator set D of graph G }
{ Global input variables: N }
  Var
    GT: GraphType;           { transposed graph of G }
    p,q: 1..MaxN; i:Word;

  Begin { ComputeCoDomin }
    For p:=1 To N Do
      GT[p,0]:=0;
    For p:=1 To N Do         { compute the transpose of the graph G in GT }
      For i:=1 To G[p,0] Do Begin
        q:=G[p,i];
        Inc(GT[q,0]); GT[q,GT[q,0]]:=p;
      End;
  ComputeDomin(GT, CD)        { computes CD, the dominator set of GT }
  End;{ ComputeCoDomin }

Begin { Program }
  ReadInput;
  ComputeDomin(G,Domin);
  ComputeCoDomin(G,CoDomin);

  NoDomins:=0;
  For p:=1 To N Do     { count the number of elements in the set Domin }
    If p In Domin Then Inc(NoDomins);

  NoCoDomins:=0;
  For p:=1 To N Do     { count the number of elements in the set CoDomin }
    If p In CoDomin Then Inc(NoCoDomins);

  If (Domin=[1]) And (CoDomin=[1])  { strongly connected }
    Then AnswerB:=0
    Else If NoDomins > NoCoDomins
      Then AnswerB:=NoDomins
      Else AnswerB:=NoCoDomins;

  WriteLn(NoDomins);
  Writeln(AnswerB);
End.

Ну и конечно же, решение на С++. Очень интересный и полезный алгоритм. Также рекомендуем разобраться самостоятельно.

Код:
#include <iostream>
using namespace std;

const int N=101;
int gMap[N][N],nMap[N][N]; 
int mapNo[N];  
int connC;  
int inC[N],outC[N];  
bool vst[N];  
int n;  
int stack[N*N],sn;  

void DFS1(int x)  
{
    vst[x]=true;
    for(int i=1;i<=n;++i)
    {
        if(gMap[x][i] && ! vst[i])
        DFS1(i);
    }
    stack[++sn]=x;
}

void DFS2(int x,int mark)  
{
    vst[x]=true;
    mapNo[x]=mark;
    for(int i=1;i<=n;++i)
    {
        if(gMap[i][x] && ! vst[i])
        DFS2(i,mark);
    }
}

void Korasaju()
{
    int i,j;
    for(i=1;i<=n;++i)
    {
        if(! vst[i])
        DFS1(i);
    }
    memset(vst,false,sizeof(vst));
    for(i=sn;i>=1;--i)  
    {
        if(! vst[stack[i]])
        DFS2(stack[i],++connC);
    }
    for(i=1;i<=n;++i)  
    {
        for(j=1;j<=n;++j)
        {
            if(gMap[i][j] && mapNo[i]!=mapNo[j])
            nMap[mapNo[i]][mapNo[j]]=true;
        }
    }
}                  

bool Read()
{
    if(scanf("%d",&n)==EOF || n==-1)
    return false;
for(int i=1,t;i<=n;++i)
{
     while(scanf("%d",&t),t)
     gMap[i][t]=true;
    }
    return true;
}

void Solve()
{
    Korasaju();
    memset(inC,0,sizeof(inC));
    memset(outC,0,sizeof(outC));
    int i,j;
    for(i=1;i<=connC;++i)
    {
        for(j=1;j<=connC;++j)
        {
            if(nMap[i][j])
                ++outC[i],++inC[j];
        }
    }
    int zeroIn=0,zeroOut=0;
    for(i=1;i<=connC;++i)
    {
        if(inC[i]==0)
        ++zeroIn;
    if(outC[i]==0)
       ++zeroOut;
}      
printf("%d\n",zeroIn);
if(connC==1)
   puts("0");
else
      printf("%d\n",zeroIn>zeroOut ? zeroIn : zeroOut);
}

int main()
{
    while(Read())
    Solve();
    return 0;
}

0

2

Помогите пожалуйста!! Как этот код будет выглядеть на С#?

0


Вы здесь » Информатика и математика » Байт решений задач с acm.pku » acm.pku 1236 Network of Schools