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

C++

Код:
#include <iostream>
#include <string>

using namespace std;

int numReceps, numPlugs, numAdapts, globalMax;

string names[400];           
int nnames;

bool receps[100];

struct plug {
   int val;
   bool list[400];            
} plugs[100];

struct adapt {
        int recep, plug;
} adapts[100];

int matchPlug[100], matchRecep[100];
bool canUse[100];

int findName(string name)
{
        for(int i=0; i<nnames; i++)
        if (name == names[i])
        return i;
   names[nnames++] = name;
   return nnames-1;
}

void setList(int i)
{
        plugs[i].list[plugs[i].val] = true;
   bool flag;
   do {
        flag = false;
      for(int j=0; j<numAdapts; j++) {
        if (plugs[i].list[adapts[j].recep] && !plugs[i].list[adapts[j].plug]) {
                flag = true;
            plugs[i].list[adapts[j].plug] = true;
         }
      }
   } while (flag);
}

bool findAugPath(int node)
{
        for(int j=0; j<numReceps; j++) {
        if (plugs[node].list[j] && canUse[j]) {
        if (matchRecep[j] == -1) {
                matchPlug[node] = j;
            matchRecep[j] = node;
            return true;
         }
         else {
                int save = matchRecep[j];
            matchRecep[j] = node;
            matchPlug[save] = -1;
            matchPlug[node] = j;
            canUse[j] = false;
            if (findAugPath(save))
                return true;
            canUse[j] = true;
            matchPlug[node] = -1;
            matchPlug[save] = j;
            matchRecep[j] = save;
         }
      }
   }
   return false;
}

int main()
{
        string name;

   cin >> numReceps;
   for(int i=0; i<numReceps; i++) {
        cin >> names[i];
      receps[i] = false;
   }
   nnames = numReceps;

   cin >> numPlugs;
   for(int i=0; i<numPlugs; i++) {
      cin >> name >> name;
      plugs[i].val=findName(name);
      for(int j=0; j<100; j++)
                plugs[i].list[j] = false;
   }

   cin >> numAdapts;
   for(int i=0; i<numAdapts; i++) {
        cin >> name;
      adapts[i].recep = findName(name);
      cin >> name;
      adapts[i].plug = findName(name);
   }

   for(int i=0; i<numPlugs; i++)
        setList(i);
        for(int i=0; i<100; i++) {
        matchPlug[i] = matchRecep[i] = -1;
   }

   int i=0;
   while(i < numPlugs) {
        for(int j=0; j<numReceps; j++)
        canUse[j] = true;
        if (matchPlug[i] == -1 && findAugPath(i)) {
        i = 0;
      }
      else
        i++;
   }

   int min = 0;
   for(int i=0; i<numPlugs; i++)
        if (matchPlug[i] == -1) min++;
   cout << min << endl;
}

Pascal

Код:
var n,m,k,tot:longint;
a:array[0..301]of string[30];
b:array[0..101]of string[30];
c:array[0..101]of longint;
kk:array[0..301,0..301]of boolean;
map:array[0..101,0..301]of boolean;
mark:array[0..301]of boolean;
from:array[0..301]of longint;

procedure init;
var
i,j,t,t1,t2:longint;
s,s1,s2:string;
begin
fillchar(kk,sizeof(kk),false);
fillchar(map,sizeof(map),false);

readln(n);
for i:=1 to n do
    begin
      readln(s);
      a[i]:=s;
    end;

readln(m);
for i:=1 to m do
    begin
      readln(s);
      t:=pos(' ',s);
      delete(s,1,t);
      b[i]:=s;
    end;

readln(k);
tot:=n;
for i:=1 to k do
    begin
      readln(s);
      t:=pos(' ',s);
      s1:=copy(s,1,t-1);
      s2:=copy(s,t+1,length(s)-t);
      t1:=0;
      t2:=0;
      for j:=1 to tot do
        if s1=a[j] then
          begin
            t1:=j;
            break;
          end;

      for j:=1 to tot do
        if s2=a[j] then
          begin
            t2:=j;
            break;
          end;

      if(t1<>0)and(t2<>0)then
        kk[t2,t1]:=true;
      if (t1=0)and(t2<>0)then
        begin
          inc(tot);
          a[tot]:=s1;
          kk[t2,tot]:=true;
        end;
      if (t1<>0)and(t2=0)then
        begin
          inc(tot);
          a[tot]:=s2;
          kk[tot,t1]:=true;
        end;
      if (t1=0)and(t2=0)then
        begin
          kk[tot+2,tot+1]:=true;
          a[tot+1]:=s1;
          a[tot+2]:=s2;
          inc(tot,2);
        end;
    end;
end;

procedure pre;
var
i,j,h:longint;
begin
for h:=1 to tot do
    for i:=1 to tot do
      for j:=1 to tot do
        if kk[i,h] and kk[h,j] then
          kk[i,j]:=true;

fillchar(c,sizeof(c),0);
for i:=1 to m do
    for j:=1 to tot do
      if b[i]=a[j] then
        begin
          c[i]:=j;
          break;
        end;

for i:=1 to m do
    begin
      for j:=1 to n do
        begin
          if b[i]=a[j] then
            map[i,j]:=true;

          if kk[j,c[i]]then
            map[i,j]:=true;
        end;
    end;
end;

function change(x:longint):boolean;
var
i:longint;
begin
for i:=1 to n do
    if map[x,i] and(not mark[i])then
      begin
        mark[i]:=true;
        if (from[i]=0) or change(from[i])then
          begin
            from[i]:=x;
            exit(true);
          end;
      end;
exit(false);
end;

procedure work;
var
i,j,ans:longint;
begin
ans:=0;
for i:=1 to m do
    begin
      fillchar(mark,sizeof(mark),false);
      if change(i)then inc(ans);
    end;

writeln(m-ans);
end;

begin
init;
pre;
work;
end.