CSU-1531 Jewelry Exhibition —— 二分图匹配（最小覆盖点）

题目链接：https://vjudge.net/problem/CSU-1531

Input

Output

Sample Input

2

1 5 3

0.2 1.5

0.3 4.8

0.4 3.5

4 4 8

0.7 0.5

1.7 0.5

2.8 1.5

3.7 0.5

2.2 3.6

2.7 2.7

1.2 2.2

1.2 2.7

Sample Output

1

3

题解：

一开始想用DP做，后来发现不行，因为新加入的点会破坏前面的结果，且不知道前面的状态如何，所以不能用动态规划的思想去解题。

1.用最少的边去覆盖掉所有的点，顾名思义，可以用二分图的最小覆盖点去做，只是这题的“点”为二分图的边，这题的"边"为二分图的点。

2.把题目的点的x、y坐标看做二分图的点，把题目的点当做二分图的边，其两端是x、y坐标，这样就转化成了用最少的点去覆盖掉所有的边。

代码一（矩阵）：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 #define eps 0.0000001

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = +;

 int G[maxn][maxn];

 int vis[maxn], match[maxn];

 int n,m,k;

 int find(int u)

 {

     for(int i = ; i<m; i++)

     {

         if(G[u][i] && !vis[i] )

         {

             vis[i] = ;

             if(match[i]==- || find(match[i]))

             {

                 match[i] = u;

                 return ;

             }

         }

     }

     return ;

 }

 void solve()

 {

     double x,y;

     scanf("%d%d%d",&n,&m,&k);

     ms(G,);

     for(int i = ; i<k; i++)

     {

         scanf("%lf%lf",&x,&y);

         G[(int)x][(int)y] = ;

     }

     int ans = ;

     ms(match,-);

     for(int i = ; i<n; i++)

     {

         ms(vis,);

         if(find(i))

             ans++;

     }

     printf("%d\n",ans);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--){

         solve();

     }

     return ;

 }

代码二（vector）：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 #define eps 0.0000001

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = +;

 vector<int> G[maxn];

 int vis[maxn], match[maxn];

 int n,m,k;

 int find(int u)

 {

     int Size = G[u].size();

     for(int i = ; i<Size; i++)

     {

         int v = G[u][i];

         if(!vis[v] )

         {

             vis[v] = ;

             if(match[v]==- || find(match[v]))

             {

                 match[v] = u;

                 return ;

             }

         }

     }

     return ;

 }

 void solve()

 {

     double x,y;

     scanf("%d%d%d",&n,&m,&k);

     for(int i = ; i<n; i++)

         G[i].clear();

     for(int i = ; i<k; i++)

     {

         scanf("%lf%lf",&x,&y);

         G[(int)x].pb((int)y);

     }

     int ans = ;

     ms(match,-);

     for(int i = ; i<n; i++)

     {

         ms(vis,);

         if(find(i))

             ans++;

     }

     printf("%d\n",ans);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--){

         solve();

     }

     return ;

 }

巴特西

CSU-1531 Jewelry Exhibition —— 二分图匹配（最小覆盖点）

最新文章

热门文章