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.