P7368 [USACO05NOV]Asteroids G

题面

贝茜想在 \(N\times N\) 的网格中驾驶她的宇宙飞船。网格中有 \(K\) 个小行星。要使驾驶过程愉快，就必须把这些小行星全部消除。

贝茜有一个武器，可以以一个单位代价消除一行或一列的全部小行星。贝茜想问你，要把所有小行星都消除的最小代价是多少。

对于 \(100\%\) 的数据，\(1 \leq N \leq 500\)，\(1 \leq K \leq N \times N\)。

思路

见到“最小代价”想到最小点覆盖。这道题就是最小点覆盖。竟然可以消除一行或者一列，那么对行建点 \(L(i)\),对列建 \(C(i)\)，然后连边 \((L(i),C(i))\)，不难发现这是一个二分图，直接匈牙利即可。

时间复杂度 \(O(n^2)\)。

代码

#include <iostream>

#include <vector>

using namespace std;

int n,m,t;

int mch[1005],vist[1005];

vector<int> g[1005];

bool dfs(int u,int tag){

    if(vist[u]==tag) return false;

    vist[u]=tag;

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

        int v=g[u][i];

        if((mch[v]==0)||dfs(mch[v],tag)){

            mch[v]=u;

            return true;

        }

    }

    return false;

}

int main(){

    cin>>n>>m;

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

		int u,v;

		cin>>u>>v;

		g[u].push_back(v+n);

	}

    int ans=0;

    for(int i=1;i<=2*n;i++){

        if(dfs(i,i)) ans++;

    }

    cout<<ans<<endl;

    return 0;

}

AC Record

巴特西

P7368 [USACO05NOV]Asteroids G

题面

思路

代码

最新文章

热门文章