find_dulilingyuan1.m

10组图论编程

function [C,Line,C1,max_b]=Find_DuLiLIngYuan1(C)
% clear
% clc
% 
% 
% C=[ 4 8 7 15 12;
%     7 9 17 14 10 ;
%     6 9 12 8 7 ;
%     6 7 14 6 10 ;
%     6 9 12 10 6]


max_all=max(max(C))+3;
max_b=max_all+10;
% 1
[m,n]=size(C);
for i=1:m
    C(i,:)=C(i,:)-min(C(i,:));
end

for i=1:m
    C(:,i)=C(:,i)-min(C(:,i));
end
% C


% 2
% C1=C;
Line=0
% while Line==0
C1=C;
[m0,n0]=find(C1==0);
while ~isempty(m0)
for i=1:m
    [m1,n1]=find(C1(i,:)==0);
    [m11,n11]=size(m1);
    m_num(i,1)=n11;
    
    [m2,n2]=find(C1(:,i)==0);
    [m21,n21]=size(m2');
    n_num(1,i)=n21;
end
m_num;
n_num;
n_num(find(n_num==0))=m+1;
m_num(find(m_num==0))=m+1;

if min(m_num)<=min(n_num)
    [m0,n0]=find(m_num==min(m_num));
    ii=m0(1,1);
    [m0,n0]=find(C1(ii,:)==0);
    C1(ii,:)=max_all;
    C1(:,n0(1,1))=max_all;
    C1(ii,n0(1,1))=max_b;
    Line=Line+1;
else
    [m0,n0]=find(n_num==min(n_num));
    ii=n0(1,1);
    [m0,n0]=find(C1(:,ii)==0);
    C1(:,ii)=max_all;
    C1(m0(1,1),:)=max_all;
    C1(m0(1,1),ii)=max_b;
    Line=Line+1;    
end
% if Line==m
%     break
% else
   
[m0,n0]=find(C1==0);
end
% C1
% C
% clc
for i=1:m
    for j=1:m
        if C(i,j)>0&&C1(i,j)==max_all
            C1(i,j)=C(i,j);
        end
    end
end
% C
% C1
        

m_ok=zeros(m,1);
n_ok=zeros(1,m);

ee=1;
while ee
    ee=0;
    for i=1:m
        [m0,n0]=find(C1(i,:)==max_b);    
        if isempty(m0)&&m_ok(i,1)==0
            m_ok(i,1)=1;
            ee=1;
        end
    end
    
    for i=1:m
        if m_ok(i,1)==1
            for j=1:m
                if C1(i,j)==max_all&&n_ok(1,j)==0
                    n_ok(1,j)=1;
                    ee=1;
                end
            end
        end
    end
    for j=1:m
        if n_ok(1,j)==1
            for i=1:m
                if C1(i,j)==max_b&&m_ok(i,1)==0
                    m_ok(i,1)=1;
                    ee=1;
                end
            end
        end
    end
end
C2=C1;
m_ok;
n_ok;
for i=1:m
    if m_ok(i,1)==0
        C2(i,:)=max_all;        
    end
end
% C2
for j=1:m
    if n_ok(1,j)==1
        C2(:,j)=max_all;        
    end
end  


min_a=min(min(C2));

for i=1:m
    if m_ok(i,1)==1
        C(i,:)=C(i,:)-min_a;
    end
end
for i=1:m
    for j=1:m
        if C(i,j)<0
            C(:,j)=C(:,j)+min_a;
        end
    end
end
% C
end
% Line=0
% end