POJ 3401 Asteroids

POJ 3401 Asteroids

題目概述:

一個n*n(≦500)的座標上有k(≦10000)個點，請問最少能用幾條縱向或橫向的直線將所有點覆蓋。

思路:

二分圖最大匹配問題。

每個點只能被一條縱向直線或一條橫向直線覆蓋到。

將縱向直線 跟 橫向直線分成兩個集合，假設點為(x,y)，那就將縱向直線集合的x連到橫向集合的y。可以發現求出最小頂點覆蓋就是答案了，而最小頂點覆蓋在二分圖中答案恰好為最大匹配數。

AC code:

//By SCJ

#include<iostream>

#include<cstring>

#include<vector>

//#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

vector<int> G[505];

int n,m,match_y[505];

bool used[505];

bool dfs(int u)

{

   for(int i=0;i<G[u].size();++i)

   {

       int v=G[u][i];

       if(used[v]) continue;

       used[v]=1;

       if(match_y[v]==-1||dfs(match_y[v]))

       {

           match_y[v]=u;

           return true;

       }

   }

   return false;

}

int bipartite_match()

{

   memset(match_y,-1,sizeof(match_y));

   int ans=0;

   for(int v=1;v<=n;++v)

   {

       memset(used,0,sizeof(used));

       if(dfs(v)) ans++;

   }

   return ans;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   cin>>n>>m;

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

   {

       int x,y;cin>>x>>y;

       G[x].push_back(y);

   }

   cout<<bipartite_match()<<endl;

}