bipartite matching

看到一个讲得很好的：二分图的最大匹配，完美匹配，匈牙利算法

还有一个特别详细的：matching

uva,10080

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn=110;
int n,m,s,v;
int pos;


struct Point
{
    double x,y;
    void read()
    {
        scanf("%lf%lf",&x,&y);
    }
}p[maxn],q[maxn];

double dist(Point a,Point b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

struct Edge
{
    int from,to;
    Edge(){}
    Edge(int a,int b):from(a),to(b){}
}E[maxn*maxn];

vector<Edge> edges;  //记录边
vector<int> G[maxn];  //记录从i出发的遍的编号
int matching[maxn+5];
bool check[maxn+5];
typedef vector<int>::iterator iterator_t;


bool dfs(int u)
{
    for(iterator_t it=G[u].begin();it!=G[u].end();it++)
    {
        int v=edges[*it].to;
        if(!check[v])
        {
            check[v]=true;
            if(matching[v]==-1 || dfs(matching[v]))
            {
                matching[v]=u;   //显示v与u匹配
                return true;   //加上matching[u]=v是错的,因为matching[u]
//是在u之前与u匹配的点，命为w，这样覆盖了w，下次经过u，w这一条匹配
//边的时候就会出错。
//!!!!!!!注意当二分匹配的两部分点的编号不一样的时候是对的。
//也可以分拆问题，一个区间段是一个类型，然后匹配；
            }
        }
    }
    return false;
}

int hungarian()
{
    int ans=0;
    memset(matching,-1,sizeof(matching));
    for(int u=0;u<n;++u)
    {//if(matching[u]==-1)是错的，因为增广路径是可以经过已经匹配的点
 
            memset(check,false,sizeof(check));
            if(dfs(u))
                ++ans;
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&s,&v))
    {
        for(int i=0;i<n;i++)
        {
            G[i].clear();
            p[i].read();
        }
        
        for(int i=0;i<m;i++)
        {
            q[i].read();
        }
        edges.clear();
        pos=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(dist(p[i],q[j])<=s*v)
                {
                    G[i].push_back(pos);
                    E[pos]=Edge(i,j);
                    edges.push_back(E[pos]);
                    pos++;
                }
            }
        }
        printf("%d
",n-hungarian());
    }
    return 0;
}
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 const int maxn=110;
10 int n,m,s,v;
11 int pos;
12 
13 
14 struct Point
15 {
16     double x,y;
17     void read()
18     {
19         scanf("%lf%lf",&x,&y);
20     }
21 }p[maxn],q[maxn];
22 
23 double dist(Point a,Point b)
24 {
25     double dx=a.x-b.x;
26     double dy=a.y-b.y;
27     return sqrt(dx*dx+dy*dy);
28 }
29 
30 vector<int> G[maxn];
31 int matching[maxn+5];
32 bool check[maxn+5];
33 typedef vector<int>::iterator iterator_t;
34 
35 
36 bool dfs(int u)
37 {
38     for(int i=0;i<G[u].size();i++)
39     {
40         int v=G[u][i];
41         if(!check[v])
42         {
43             check[v]=true;
44             if(matching[v]==-1 || dfs(matching[v]))
45             {
46                 matching[v]=u;
47                 return true;
48             }
49         }
50     }
51     return false;
52 }
53 
54 int hungarian()
55 {
56     int ans=0;
57     memset(matching,-1,sizeof(matching));
58     for(int u=0;u<n;++u)
59     {
60             memset(check,false,sizeof(check));
61             if(dfs(u))
62                 ++ans;
63     }
64     return ans;
65 }
66 
67 int main()
68 {
69     while(~scanf("%d%d%d%d",&n,&m,&s,&v))
70     {
71         for(int i=0;i<n;i++)
72         {
73             G[i].clear();
74             p[i].read();
75         }
76         
77         for(int i=0;i<m;i++)
78         {
79             q[i].read();
80         }
81         for(int i=0;i<n;i++)
82         {
83             for(int j=0;j<m;j++)
84             {
85                 if(dist(p[i],q[j])<=s*v)
86                 {
87                     G[i].push_back(j);
88                 }
89             }
90         }
91         printf("%d
",n-hungarian());
92     }
93     return 0;
94 }
更简单的临接表重写了

uva,10092

记录一个从用匈牙利算法到各种改进到觉得不需要匈牙利算法又到决定不用是不对的代码。。注意是错的！！！！

因为我这个代码没有一个求增广路径的过程，

例如

1 2 7
2 4 2 
3 1 1 
4 1 1 
5 2 1 2 
6 1 1 
7 2 1 2 
8 1 1 
9 1 1

如果按照顺序匹配，第五行的2是不能被匹配的，所以结果为0，但是根据最大匹配的原则，这个点是可以被匹配的。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <vector>
  6 
  7 using namespace std;
  8 const int maxn=1100;
  9 
 10 int nk,np;
 11 
 12 vector<int> G[maxn];
 13 vector<int> S[25];
 14 int map[maxn];
 15 int cnt;
 16 int flag;
 17 
 18 
 19 bool dfs(int u)
 20 {
 21     for(int i=0;i<G[u].size();i++)
 22     {
 23         int v=G[u][i];
 24         if(!map[v])
 25             continue;
 26         S[v].push_back(u);
 27         map[v]--;
 28         return true;
 29     }
 30     return false;
 31 }
 32 
 33 void hungarian()
 34 {
 35     for(int i=1;i<=np;i++)
 36     {
 37         if(dfs(i))
 38         {
 39             cnt--;
 40         }
 41         if(!cnt)
 42         {
 43             for(int i=1;i<=nk;i++)
 44             {
 45                 if(map[i])
 46                 {
 47                     flag=1;
 48                     return;
 49                 }
 50             }
 51             return;
 52         }
 53     }
 54 }
 55 
 56 int main()
 57 {
 58     int n,m;
 59     while(scanf("%d%d",&nk,&np) && nk+np)
 60     {
 61         cnt=0;
 62         memset(map,0,sizeof(map));
 63         for(int i=1;i<=nk;i++)
 64         {
 65             S[i].clear();
 66             scanf("%d",&n);
 67             map[i]=n;
 68             cnt+=n;
 69         }
 70         for(int i=1;i<=np;i++)
 71             G[i].clear();
 72         for(int i=1;i<=np;i++)
 73         {
 74             scanf("%d",&n);
 75             for(int j=0;j<n;j++)
 76             {
 77                 scanf("%d",&m);
 78                 G[i].push_back(m);
 79             }
 80         }
 81         flag=0;
 82         hungarian();
 83         if(flag || cnt)
 84             printf("0
");
 85         else
 86         {
 87             printf("1
");
 88             for(int i=1;i<=nk;i++)
 89             {
 90                 for(int j=0;j<S[i].size();j++)
 91                 {
 92                     if(!j)
 93                         printf("%d",S[i][j]);
 94                     else
 95                         printf(" %d",S[i][j]);
 96                 }
 97                 printf("
");
 98             }
 99         }
100     }
101     return 0;
102 }
View Code

然后让我们用正确的思路去理解它：二分匹配的问题是针对能分成两个部分，然后这两个部分各自之间是没有边的，只有相互之间有边。

然而这个问题给出来是题目的种类部分是有引向自己的边。所以二分匹配不成立，不能用最大匹配算法。

So:::::::我们为什么不想：把一个种类含有几个的分拆为只含有一个的能够被同一问题所匹配。

这样子就能够使用最大匹配算法；；；；；good idea。shit.

why are't me notion it?

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 const int maxn=1005;
 10 
 11 int g[maxn][maxn],proSetNum[maxn];
 12 int matching[maxn];
 13 int proMatch[maxn];
 14 bool check[maxn];
 15 int proSizeNum,proNum,proSizeSum;
 16 int pos[maxn];
 17 
 18 void Initial()
 19 {
 20     memset(g,0,sizeof(g));
 21     pos[1]=1;
 22     for(int i=2;i<=proSizeNum;i++)
 23         pos[i]=pos[i-1]+proSetNum[i-1];
 24 }
 25 
 26 bool dfs(int u)
 27 {
 28     for(int i=1;i<=proSizeSum;i++)
 29     {
 30         if(g[u][i] && !check[i])
 31         {
 32             check[i]=true;
 33             if(matching[i]==-1 || dfs(matching[i]))
 34             {
 35                 matching[i]=u;
 36                 proMatch[u]=i;
 37                 return true;
 38             }
 39         }
 40     }
 41     return false;
 42 }
 43 
 44 void hungarian()
 45 {
 46     for(int i=1;i<=proNum;i++)
 47         proMatch[i]=-1;
 48     for(int i=1;i<=proSizeSum;i++)
 49         matching[i]=-1;
 50     int maxMatch=0;
 51     
 52     for(int i=1;i<=proNum;i++)
 53     {
 54         if(proMatch[i]==-1)
 55         {
 56             memset(check,false,sizeof(check));
 57             if(dfs(i))
 58             {
 59                 maxMatch++;
 60             }
 61         }
 62     }
 63     
 64     if(maxMatch==proSizeSum)
 65     {
 66         printf("1
");
 67         for(int i=1;i<=proSizeNum;i++)
 68         {
 69             for(int j=0;j<proSetNum[i];j++)
 70             {
 71                 if(!j)
 72                     printf("%d",matching[pos[i]+j]);
 73                 else
 74                     printf(" %d",matching[pos[i]+j]);
 75             }
 76             printf("
");
 77         }
 78     }
 79     else
 80         printf("0
");
 81 }
 82 
 83 int main()
 84 {
 85     int m,n;
 86     while(scanf("%d%d",&proSizeNum,&proNum) && proSizeNum+proNum)
 87     {
 88         proSizeSum=0;
 89         for(int i=1;i<=proSizeNum;i++)
 90         {
 91             scanf("%d",&proSetNum[i]);
 92             proSizeSum+=proSetNum[i];
 93         }
 94         Initial();
 95         for(int i=1;i<=proNum;i++)
 96         {
 97             scanf("%d",&n);
 98             for(int j=0;j<n;j++)
 99             {
100                 scanf("%d",&m);
101                 for(int k=0;k<proSetNum[m];k++)
102                     g[i][pos[m]+k]=m;
103             }
104         }
105         hungarian();
106     }
107     return 0;
108 }
用临接矩阵ac了，不过挺慢的

uva,670

主人和够从一个点出发，狗的速度<=2*主人的速度,每经过一个点问在下一个点之前，狗去一个有趣的地方，且最多去一个，

然后主人与狗在下一个点碰面，问最多有趣的点，

简化为边与点的匹配，当符合狗跑的距离<=2*主人的距离就加入二分匹配的一边，然后求最大匹配跑一跑

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <algorithm>
  6 #include <cmath>
  7 #define eps 1e-6
  8 using namespace std;
  9 const int maxn=105;
 10 
 11 int matching[maxn];
 12 bool check[maxn];
 13 int G[maxn][maxn];
 14 int proMatch[maxn];
 15 int N,M;
 16 int pos;
 17 int cnt;
 18 
 19 struct Point
 20 {
 21     int x,y;
 22     void read()
 23     {
 24         scanf("%d%d",&x,&y);
 25     }
 26 }p[maxn],q[maxn];
 27 
 28 
 29 double dist(Point a,Point b)
 30 {
 31     int dx=a.x-b.x;
 32     int dy=a.y-b.y;
 33     return sqrt(dx*dx+dy*dy);
 34 }
 35 
 36 struct Edge
 37 {
 38     int from,to;
 39     double dis;
 40     Edge(){}
 41     Edge(int a,int b)
 42     {
 43         this->from=a;
 44         this->to=b;
 45         dis=dist(p[a],p[b]);
 46     }
 47 }E[maxn*maxn];
 48 
 49 
 50 bool dfs(int u)
 51 {
 52     for(int j=1;j<=M;j++)
 53     {
 54         if(G[u][j] && !check[j])
 55         {
 56             check[j]=true;
 57             if(matching[j]==-1 || dfs(matching[j]))
 58             {
 59                 proMatch[u]=j;
 60                 matching[j]=u;
 61                 return true;
 62             }
 63         }
 64     }
 65     return false;
 66 }
 67 
 68 
 69 void hungarian()
 70 {
 71     for(int i=0;i<=M;i++) //i<=M注意可能会漏点
 72         matching[i]=-1;
 73     for(int i=0;i<=N;i++)
 74         proMatch[i]=-1;
 75     cnt=N;
 76     for(int i=0;i<pos;i++)
 77     {
 78         if(proMatch[i]==-1)
 79         {
 80             memset(check,false,sizeof(check));
 81             if(dfs(i))
 82             {
 83                 cnt++;
 84             }
 85         }
 86     }
 87     
 88 }
 89 
 90 int main()
 91 {
 92     int L;
 93     scanf("%d",&L);
 94     while(L--)
 95     {
 96         scanf("%d%d",&N,&M);
 97         for(int i=0;i<N;i++)
 98         {
 99             p[i].read();
100         }
101         
102         pos=0;
103         for(int i=1;i<N;i++)
104         {
105             E[pos++]=Edge(i-1,i);  //相邻两个点
106         }
107         memset(G,0,sizeof(G));
108         for(int j=1;j<=M;j++)
109         {
110             q[j].read();
111         }
112         
113         for(int i=0;i<pos;i++)
114         {
115             for(int j=1;j<=M;j++)
116             {
117                 if(dist(p[E[i].from],q[j])+dist(p[E[i].to],q[j])<=2*E[i].dis)
118                     G[i][j]=1;
119             }
120         }
121         
122         hungarian();
123         printf("%d
",cnt);
124         for(int i=0;i<pos;i++)
125         {
126             int v=proMatch[i];
127             if(v>0)  //注意要v>0  不能直接if(v)
128             {
129                 if(!i)
130                     printf("%d %d %d %d %d %d",p[E[i].from].x,p[E[i].from].y,q[v].x,q[v].y,p[E[i].to].x,p[E[i].to].y);
131                 else
132                     printf(" %d %d %d %d",q[v].x,q[v].y,p[E[i].to].x,p[E[i].to].y);
133             }
134             else
135             {
136                 if(!i)
137                     printf("%d %d %d %d",p[E[i].from].x,p[E[i].from].y,p[E[i].to].x,p[E[i].to].y);
138                 else
139                     printf(" %d %d",p[E[i].to].x,p[E[i].to].y);
140             }
141         }
142         printf("
");
143         if(L)
144             printf("
");
145     }
146     return 0;
147 }
View Code

 uva,11045

和第二道题差不多，要简单。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <map>
 7 
 8 
 9 using namespace std;
10 const int maxn=40;
11 
12 int g[maxn][maxn];
13 int matching[maxn];
14 bool check[maxn];
15 int proSizeNum,proSizeSum,proSetNum[maxn],proNum;
16 int pos[maxn];
17 map<string,int> mp;
18 
19 void Initial()
20 {
21     memset(g,0,sizeof(g));
22     pos[1]=1;
23     int l=proSizeNum/6;
24     for(int i=2;i<=6;i++)
25         pos[i]=pos[i-1]+l;  //将第i中衣服k件拆成k件第i种衣服。
26 }
27 
28 bool dfs(int u)
29 {
30     for(int i=1;i<=proSizeNum;i++)
31     {
32         if(!check[i] && g[u][i])
33         {
34             check[i]=true;
35             if(matching[i]==-1 ||  dfs(matching[i]))
36             {
37                 matching[i]=u;
38                 return true;
39             }
40         }
41     }
42     return false;
43 }
44 
45 void hungarian()
46 {
47     for(int i=1;i<=proSizeNum;i++)
48         matching[i]=-1;
49     
50     int maxMatch=0;
51     for(int i=0;i<proNum;i++)
52     {
53         memset(check,false,sizeof(check));
54         if(dfs(i))
55             maxMatch++;
56     }
57     
58     if(maxMatch==proNum)
59         printf("YES
");
60     else
61         printf("NO
");
62 }
63 
64 int main()
65 {
66     int t;
67     scanf("%d",&t);
68     int m,n;
69     string s1,s2;
70     while(t--)
71     {
72         mp.clear();
73         mp["XXL"]=1;  //剪枝
74         mp["XL"]=2;  
75         mp["L"]=3;
76         mp["M"]=4;
77         mp["S"]=5;
78         mp["XS"]=6;
79         scanf("%d%d",&proSizeNum,&proNum);
80         Initial();
81         int tmp=proSizeNum/6;
82         int cnt1=0;
83         for(int i=0;i<proNum;i++)
84         {
85             cin>>s1>>s2;
86             m=mp[s1];n=mp[s2];
87             for(int i=0;i<tmp;i++)
88             {
89                 g[cnt1][pos[m]+i]=m;
90                 g[cnt1][pos[n]+i]=n;
91             }
92             cnt1++;
93         }
94         hungarian();
95     }
96     return 0;
97 }
View Code
活在现实，做在梦里。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/do-it-best/p/5423907.html