二分匹配（KM算法）

给出一个完全二分图每条边有一个权值要求求出权值和最大的完美匹配

代码：

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int c1,c2,w[1002][1002],lx[102],ly[102],s[102],t[102],link[102];

void update()
{
    int i,j;
    int a=1<<30;
    for(i=0;i<c1;i++)
    {
        if(s[i])
        {
            for(j=0;j<c1;j++)
            {
                if(!t[j])
                {
                    a=min(a,lx[i]+ly[j]-w[i][j]);
                }
            }
        }
    }
    for(i=0;i<c1;i++)
    {
        if(s[i]) lx[i]-=a;
        if(t[i]) ly[i]+=a;
    }
}

int dfs(int x)
{
    s[x]=1;
    for(int i=0;i<c1;i++)
        if(!t[i]&&lx[x]+ly[i]==w[x][i])
        {
            t[i]=1;
            if(link[i]==-1||dfs(link[i]))
            {
                link[i]=x;
                return 1;
            }
        }
        return 0;
}

void km()
{
    int i,j;
    for(i=0;i<c1;i++)
    {
        ly[i]=0; lx[i]=w[i][0];
        for(j=1;j<c1;j++)
            lx[i]=max(lx[i],w[i][j]);
    }
    memset(link,-1,sizeof(link));
    for(i=0;i<c1;i++)
        while(1)
        {
            memset(s,0,sizeof(s));
            memset(t,0,sizeof(t));
            if(dfs(i))
                break;
            else update();
        }
}
//主函数中直接调用   KM（）；

poj 2195 going home http://poj.org/problem?id=2195

【题意+思路】：给定一个N*M的地图，地图上有若干个man和house，且man与house的数量一致。man每移动一格需花费$1（即单位费用=单位距离），一间house只能入住一个man。现在要求所有的man都入住house，求最小费用。这里求得是最小费用只要把图里的权值变成负数求出最大的权值和取负就可以i了

  1 #include<iostream>
  2 #include<string.h>
  3 #include<stdio.h>
  4 
  5 using namespace std;
  6 struct node{int x;int y;} man[102],house[102];
  7 char ss[102][102];
  8 int c1,c2,w[1002][1002],lx[102],ly[102],s[102],t[102],link[102];
  9 
 10 int max(int a,int b)
 11 {
 12     return a>b?a:b;
 13 }
 14 
 15 int min(int a,int b)
 16 {
 17     return a<b?a:b;
 18 }
 19 
 20 int abs(int a)
 21 {
 22     return a>0?a:a*(-1);
 23 }
 24 
 25 void build()
 26 {
 27     for(int i=0;i<c1;i++)
 28         for(int j=0;j<c2;j++)
 29         {
 30             int q;
 31             q=abs(man[i].x-house[j].x)+abs(man[i].y-house[j].y);
 32             w[i][j]-=q;
 33         }
 34 }
 35 
 36 int dfs(int x)
 37 {
 38     s[x]=1;
 39     for(int i=0;i<c1;i++)
 40     if(!t[i]&&lx[x]+ly[i]==w[x][i])
 41     {
 42         t[i]=1;
 43         if(link[i]==-1||dfs(link[i]))
 44         {
 45             link[i]=x;
 46             return 1;
 47         }
 48     }
 49     return 0;
 50 }
 51 
 52 
 53 void update()
 54 {
 55     int i,j;
 56     int a=1<<30;
 57     for(i=0;i<c1;i++)
 58     {
 59         if(s[i])
 60         {
 61             for(j=0;j<c1;j++)
 62             {
 63                 if(!t[j])
 64                 {
 65                     a=min(a,lx[i]+ly[j]-w[i][j]);
 66                 }
 67             }
 68         }
 69     }
 70     for(i=0;i<c1;i++)
 71     {
 72         if(s[i]) lx[i]-=a;
 73         if(t[i]) ly[i]+=a;
 74     }
 75 }
 76 
 77 
 78 void km()
 79 {
 80     int i,j;
 81     for(i=0;i<c1;i++)
 82     {
 83         ly[i]=0; lx[i]=w[i][0];
 84         for(j=1;j<c1;j++)
 85            lx[i]=max(lx[i],w[i][j]);
 86     }
 87     memset(link,-1,sizeof(link));
 88     for(i=0;i<c1;i++)
 89         while(1)
 90         {
 91             memset(s,0,sizeof(s));
 92             memset(t,0,sizeof(t));
 93             if(dfs(i))
 94                 break;
 95             else update();
 96         }
 97 }
 98 
 99 
100 
101 int main()
102 {
103     int i,j,n,m;
104     while(scanf("%d%d",&n,&m))
105     {
106         if(n==0&&m==0)
107             break;
108         //getchar();
109         for(i=0;i<n;i++)
110             scanf("%s",ss[i]);
111          c1=c2=0;
112         for(i=0;i<n;i++)
113             for(j=0;j<m;j++)
114             {
115                 if(ss[i][j]=='m')
116                 { 
117                     man[c1].x=i;   man[c1++].y=j;
118                 }
119                 if(ss[i][j]=='H')
120                 {
121                     house[c2].x=i; house[c2++].y=j;
122                 }
123             }
124             memset(w,0,sizeof(w));
125             build();
126             
127 
128             km();
129             
130             int ans=0;
131             for(i=0;i<c1;i++)
132                 ans+=w[link[i]][i];
133             printf("%d
",ans*(-1));
134     }
135     return 0;
136 }

View Code

hdu 3722 Card Game http://acm.hdu.edu.cn/showproblem.php?pid=3722

【题意】；给出n个字符串,其中任意两个字符串(包括同一字符串)可以进行互相拼接起来,例如s1="abcd"……>s2="dcab",表示将s1拼接在s2后面,所得的值就是将s1反转得"dcba",该字符串与s2同有的前缀为"dc",所以值就是2.现在求解在n个字符串给定的情况下,将这些字符串拼接起来所得到的最大值. 建好了图就是个km模板题了

  1 #include<iostream>
  2 #include<string.h>
  3 #include<stdio.h>
  4 using namespace std;
  5 struct node{int x;int y;} man[102],house[102];
  6 char ss[102][102];
  7 int c1,c2,w[1002][1002],lx[102],ly[102],s[102],t[102],link[102];
  8 
  9 int max(int a,int b)
 10 {
 11     return a>b?a:b;
 12 }
 13 
 14 int min(int a,int b)
 15 {
 16     return a<b?a:b;
 17 }
 18 
 19 int abs(int a)
 20 {
 21     return a>0?a:a*(-1);
 22 }
 23 
 24 void build()
 25 {
 26     for(int i=0;i<c1;i++)
 27         for(int j=0;j<c2;j++)
 28         {
 29             int q;
 30             q=abs(man[i].x-house[j].x)+abs(man[i].y-house[j].y);
 31             w[i][j]-=q;
 32         }
 33 }
 34 
 35 int dfs(int x)
 36 {
 37     s[x]=1;
 38     for(int i=0;i<c1;i++)
 39         if(!t[i]&&lx[x]+ly[i]==w[x][i])
 40         {
 41             t[i]=1;
 42             if(link[i]==-1||dfs(link[i]))
 43             {
 44                 link[i]=x;
 45                 return 1;
 46             }
 47         }
 48         return 0;
 49 }
 50 
 51 
 52 void update()
 53 {
 54     int i,j;
 55     int a=1<<30;
 56     for(i=0;i<c1;i++)
 57     {
 58         if(s[i])
 59         {
 60             for(j=0;j<c1;j++)
 61             {
 62                 if(!t[j])
 63                 {
 64                     a=min(a,lx[i]+ly[j]-w[i][j]);
 65                 }
 66             }
 67         }
 68     }
 69     for(i=0;i<c1;i++)
 70     {
 71         if(s[i]) lx[i]-=a;
 72         if(t[i]) ly[i]+=a;
 73     }
 74 }
 75 
 76 void km()
 77 {
 78     int i,j;
 79     for(i=0;i<c1;i++)
 80     {
 81         ly[i]=0; lx[i]=w[i][0];
 82         for(j=1;j<c1;j++)
 83             lx[i]=max(lx[i],w[i][j]);
 84     }
 85     memset(link,-1,sizeof(link));
 86     for(i=0;i<c1;i++)
 87         while(1)
 88         {
 89             memset(s,0,sizeof(s));
 90             memset(t,0,sizeof(t));
 91             if(dfs(i))
 92                 break;
 93             else update();
 94         }
 95 }
 96 
 97 int main()
 98 {
 99     int i,j,n,m;
100     while(scanf("%d%d",&n,&m))
101     {
102         if(n==0&&m==0)
103             break;
104         for(i=0;i<n;i++)
105             scanf("%s",ss[i]);
106         c1=c2=0;
107         for(i=0;i<n;i++)
108             for(j=0;j<m;j++)
109             {
110                 if(ss[i][j]=='m')
111                 { 
112                     man[c1].x=i;   man[c1++].y=j;
113                 }
114                 if(ss[i][j]=='H')
115                 {
116                     house[c2].x=i; house[c2++].y=j;
117                 }
118             }
119             memset(w,0,sizeof(w));
120             build();
121             km();            
122             int ans=0;
123             for(i=0;i<c1;i++)
124                 ans+=w[link[i]][i];
125             printf("%d
",ans*(-1));
126     }
127     return 0;
128 }

View Code

二分匹配 （KM算法）

二分匹配（KM算法）