当前位置:编程学习 > C/C++ >>

Uva11419 I AM SAM 我是山姆 二分匹配

这是白书上给出的题目,我去做了下,题意跟poj3041很像,给一个矩阵,再给出障碍物,一个子弹可以清除一整行或者一整列的障碍物,问最少 需要打几枪,同时把开枪的位置给输出来,
 
 
 
分析:求打几枪 很简单,先做一下poj3041就知道了, 最少打几枪 反过来想 其实就是问 最多有几个点 不在同一个行也不在同一列上,至于开枪的位置,可以开两个数组,这里是行与列进行匹配,所以 行 在左集合  列右集合,各自开一个数组 marry[],marry[i]=x,择表示i与x进行匹配,求最大匹配数完成后,再从没有匹配的点开始拓展,因为求最少开几枪其实就是求最大匹配数,最大匹配数就是最多有几个点不在同一行也不在同一列,那么剩下的点就是没有匹配过,那就从他们开始拓展开来,第一次没有参与匹配的点 在哪一行最多 或者在哪一列最多 那么肯定开枪位置就在这一行 或者这一列,这里的左右集合表现的很明显,因为记录 路径的缘故
 
 
 
 
#include<iostream>  
#include<cstdio>  
#include<list>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<stack>  
#include<map>  
#include<vector>  
#include<cmath>  
#include<memory.h>  
#include<set>  
  
#define ll long long  
#define LL __int64  
#define eps 1e-8  
const ll INF=9999999999999;  
  
using namespace std;  
  
#define M 400000100  
  
#define inf 0xfffffff  
  
//vector<pair<int,int> > G;  
//typedef pair<int,int> P;  
//vector<pair<int,int>> ::iterator iter;  
//  
//map<ll,int>mp;  
//map<ll,int>::iterator p;  
  
vector<int>G[1212];  
  
char tempmp[1212];  
int mp[1212][1212];  
int lmarry[1212],rmarry[1212];  
bool visl[1212],visr[1212];  
  
int dis[2][4]={0,-1,0,1,1,0,-1,0};  
  
int n,m,k;  
  
void clear()  
{  
    memset(lmarry,-1,sizeof(lmarry));  
    memset(rmarry,-1,sizeof(rmarry));  
    memset(visl,false,sizeof(visl));  
    memset(visr,false,sizeof(visr));  
    memset(mp,0,sizeof(mp));  
    for(int i=0;i<1212;i++)  
        G[i].clear();  
}  
  
bool dfs(int x)  
{  
    visl[x]=true;  
    for(int i=0;i<G[x].size();i++)  
    {  
        int v=G[x][i];  
        if(!visr[v])  
        {  
            visr[v]=true;  
            if(lmarry[v]==-1 || dfs(lmarry[v]))  
            {  
                lmarry[v]=x;  
                rmarry[x]=v;  
                return 1;  
            }  
        }  
    }  
    return 0;  
}  
  
  
int main(void)  
{  
    while(scanf("%d %d %d",&n,&m,&k),n+m+k)  
    {  
        clear();  
        int u,v;  
        for(int i=0;i<k;i++)  
        {  
            scanf("%d %d",&u,&v);  
            G[u].push_back(v);//用邻接表比较快,邻接表记录也比较方便  
        }  
        int ans=0;  
        for(int i=1;i<=n;i++)//跟poj3041一模一样的 反过来想其实就是求最多有几个点不在同一行也不在同一列上  
        {  
            memset(visr,false,sizeof(visr));  
            if(dfs(i))  
                ans++;  
        }  
        printf("%d",ans);  
        memset(visl,false,sizeof(visl));  
        memset(visr,false,sizeof(visr));  
        for(int i=1;i<=n;i++)  
            if(rmarry[i]==-1)//从没有匹配过的点开始拓展,再次匹配  
                dfs(i);  
        for(int i=1;i<=n;i++)//没有被匹配过的行,也就是左集合中的点输出  
            if(!visl[i])  
                printf(" r%d",i);  
        for(int i=1;i<=m;i++)//被匹配上的列,也就是右集合中的点  
            if(visr[i])  
                printf(" c%d",i);  
        printf("\n");  
    }  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,