Отримання знань

дистанційна підтримка освіти школярів


Штепсель для UNIX
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;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)