Кирсанов М.Н. Графы в Maple Физматлит 2007
| > | #Программа 29 c.136 |
Задача о назначениях
| > | restart: n:=4: |
| > | N:=1..n: |
| > | with(LinearAlgebra): |
| > | A:=Matrix([[1,7,1,3],[1,6,4,6],[17,1,5,1],[1,6,10,4]]): |
| > | A0:=A: |
| > | A1:=Matrix(n): |
Из каждой строки вычитаем min
| > | for i to n do |
| > | m:=min(op(convert(Row(A,i),list))); |
| > | R[i]:=convert(map(`-`,Row(A,i),m),list);od: |
| > | A:=Matrix([seq(R[i],i=N)]): |
Из каждого столбца вычитаем min
| > | for i to n do |
| > | m:=min(op(convert(Column(A,i),list))); |
| > | C[i]:=convert(map(`-`,Column(A,i),m),list);od: |
| > | A:=Transpose(Matrix([seq(C[i],i=N)])): |
| > | n1:=1: |
| > | while n1<>n do # Пока паросочетание не совершенное |
| > | for i to n do # Матрица A1 двудольного графа |
| > | for j to n do |
| > | if A[i,j]=0 then A1[i,j]:=1 else A1[i,j]:=0:fi; |
| > | od: |
| > | od: |
Считывание подпрограммы BipartCard из файла bipart.m
| > | read "C:\\bipart.m"; |
| > | B:=Matrix(n): |
| > | BipartCard(A1): # Максимальное паросочестание |
| > | n1:=nops(op(B)[3]):# Число 1 в матрице B |
| > | C:=A1-B: # Матрица графа с дугами от X к Y |
| > | XM:={}:YM:={}: |
| > | for i to n do # Множества вершин, не входящих в паросочетание |
| > | if not 1 in convert(Row(B,i),list) then XM:=XM union {i} fi; |
| > | if not 1 in convert(Column(B,i),list) then YM:=YM union {i} fi; |
| > | od: |
| > | Xs:=XM: Ys:={}:# Множества вершин, достижимых из XM |
| > | L12:=1; |
| > | while L12<>0 do# Пока не установится процесс |
| > | L1:=nops(Xs): |
| > | for k in Xs do |
| > | for j to n do |
| > | for i to n do |
| > | if C[k,i]=1 then |
| > | Ys:=Ys union {i}; |
| > | if B[j,i]=1 then Xs:=Xs union {j};fi; |
| > | fi; |
| > | od; |
| > | od; |
| > | od; |
| > | L12:=L1-nops(Xs): |
| > | od: |
| > | Y0:={$N} minus Ys: |
| > | sbm:=SubMatrix(A,[op(Xs)],[op(Y0)]):# Подматрица из строк Xs и столбцов Y0 |
| > | m:=min(op(convert(sbm,set))); |
| > | for i to n do |
| > | for j to n do |
| > | if i in Xs then A[i,j]:=A[i,j]-m;fi; |
| > | if j in Ys then A[i,j]:=A[i,j]+m;fi; |
| > | od; |
| > | od; |
| > | od: |
| > | MinSum=add(add(B[i,j]*A0[i,j],i=N),j=N); |