二分图匹配问题
属性为一边,装备为另一边,每一个装备连2条边,枚举属性进行匈牙利算法
但是这题有一个优化 因为flag每次都重置的话需要花很长时间,我们采用一个时间戳,每次进行匹配的时候T++,flag就用T来代替
注意不能直接输出T-1,因为如果匹配完全的话,就是输出T了
#include <cstdio> #include <algorithm> using namespace std; const int N=1000010; int to[N*2],pre[N*2],now[N],from[N],flag[N],T,tail,n,a,b; void add(int u,int v){to[++tail]=v;pre[tail]=now[u];now[u]=tail;} bool hungary(int a){ for(int i=now[a];i;i=pre[i]) if(flag[to[i]]!=T){ flag[to[i]]=T; if(!from[to[i]] || hungary(from[to[i]])){from[to[i]]=a;return true;} } return false; } void read(int &x){ char c; while((c=getchar())<'0'||c>'9');x=c-'0'; while((c=getchar())>='0'&&c<='9') x=x*10+c-'0'; } int main(){ //freopen("1854.in","r",stdin);freopen("1854.out","w",stdout); read(n); for(int i=1;i<=n;i++) read(a),read(b),add(a,i),add(b,i); for(int i=1;i<=10000;i++){ T++; if(!hungary(i)) {T--;break;} } printf("%d",T); return 0; }
二分图匹配 从第一个开始找匹配 找到第一个无法匹配的break并输出
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=1010; int help[N][2],from[N],n,m,ans,flag[N]; bool hungary(int x){ for(int i=0;i<=1;i++) { int tmp=help[x][i]; if(flag[tmp]) continue;else flag[tmp]=1; if(!from[tmp] || hungary(from[tmp])){from[tmp]=x;return true;} } return false; } int main(){ //freopen("1191.in","r",stdin);freopen("1191.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&help[i][0],&help[i][1]); for(int i=1;i<=m;i++){ memset(flag,0,sizeof(flag)); if(hungary(i)) ans++;else break; } printf("%d",ans); return 0; }
类似于这道题的题似乎以前多面体在codevs月赛里出过
不管怎么动 处在同一列的格子总是处在同一列 行同理 则问题转化成要找到一些黑格子 其中任意两个都不在同一行或同一列
把行号看成二分图的一部 列看成另一部 那么就变成了一个二分图匹配的问题 对于每一个f[i][j]是黑的 我们连边(i,j),之后匈牙利算法(不会的百度一下或者问学长)搞一下就好了
我在打匈牙利算法的时候 忘记在每一轮的匹配中加上这一轮匹配是否用过的标记 于是就wa了……
还有注意边的数比较多……
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=41000; int e[N],pre[N],now[N],T,n,tail,to[N],from[N],vis[N],tmp; bool flag; void add(int u,int v){e[++tail]=v;pre[tail]=now[u];now[u]=tail;} bool hungary(int a){ for(int i=now[a];i;i=pre[i]){ if(vis[e[i]]) continue;else vis[e[i]]=1; if(!from[e[i]] || hungary(from[e[i]])) {from[e[i]]=a,to[a]=e[i];return true;} } return false; } int main(){ freopen("1059.in","r",stdin);freopen("1059.out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d",&n); memset(e,0,sizeof(e)); memset(pre,0,sizeof(pre)); memset(now,0,sizeof(now)); memset(to,0,sizeof(to)); memset(from,0,sizeof(from)); tail=0;flag=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&tmp); if(tmp) add(i,j); } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(!hungary(i)) {flag=0;break;} } printf(flag?"Yes\n":"No\n"); } return 0; }