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.