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++ ,