TTTTTTTTTTTTTTTTTT POJ 2724 奶酪消毒机 二分匹配 建图 比较难想
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 5004 | Accepted: 1444 |
Description
One day, Mike's machine was infected. When Mike found out, he had already done some operations and the cheeses operated by this infected machine were infected too. He cleaned his machine as quickly as he could, and now he needs to clean the infected cheeses with the minimum number of operations. If a cheese is infected, cleaning this cheese with the machine one or more times will make this cheese free from virus again; but if a cheese is not infected, operation on this cheese will make it go bad.
Now given the infected operations Mike has done, you need to find out the minimum number of operations that must be performed to clean all the infected cheeses without making any clean cheese go bad.
Input
Output
Sample Input
3 3
*01
100
011
0 0
Sample Output
Source
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
#define MM(a,b) memset(a,b,sizeof(a))
using namespace std; vector<int> G[2200];
int match[2200],used[2200];
int g,b,m,cnt,l,r;
int mp[2200],posi[2200]; void add_edge(int u,int v)
{
G[u].push_back(v);
G[v].push_back(u);
} bool dfs(int u)
{
used[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
int w=match[v];
if(w<0||!used[w]&&dfs(w))
{
match[u]=v;
match[v]=u;
return true;
}
}
return false;
} int bipartite_match()
{
MM(match,-1);
int res=0;
for(int i=1;i<=1000+r;i++)
if(match[i]<0)
{
memset(used,0,sizeof(used));
if(dfs(i)) res++;
}
return res;
} bool onlyonedifer(int i,int j)
{
int c=(i^j);
return (c&&((c&(c-1))==0));
}//处理i,j,两个数字二进制表示只有一位不同模板 bool jione(int i)
{
int j=0;
while(i)
{
if(i&1) j++;
i>>=1;
}
return j%2==1;
} void build()
{
l=0;r=0;
for(int i=1;i<=cnt;i++)
{ if(jione(mp[i]))
{
l++;
posi[l]=mp[i];
}
else
{
r++;
posi[1000+r]=mp[i];
}
} for(int i=1;i<=1000+r;i++) G[i].clear(); for(int i=1;i<=l;i++)
for(int j=1;j<=r;j++)
if(onlyonedifer(posi[i],posi[j+1000]))
add_edge(i,j+1000);
} char s[15];
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m)&&(n||m))
{
cnt=0;
MM(mp,0);
for(int i=1;i<=m;i++)
{
scanf("%s",s);
int flag=0;
++cnt;
for(int j=0;j<n;j++)
{
if(s[j]=='*')
{
flag=j+1;
mp[cnt]=(mp[cnt]<<1)+0;
}
else
mp[cnt]=(mp[cnt]<<1)+s[j]-'0';
}
if(flag)
{
mp[cnt+1]=(mp[cnt]|(1<<(n-1-(flag-1))));
++cnt;
}
}
sort(mp+1,mp+cnt+1);//unique处理前先排序
cnt=unique(mp+1,mp+cnt+1)-(mp+1);//去重
build();
int w=bipartite_match();
printf("%d\n",w+cnt-2*w);
}
return 0;
}
分析:细节很多的一道题;
1.处理两个数字二进制表示只有一位不同的模板,见代码
2.出现*时,进行二分匹配,建图很有技巧,将1出现个数为奇数次的放左边,偶数次的放右边
3.要进行去重处理
4.&运算符的优先级很低
最新文章
- GFF3格式文件
- 网络层、传输层、应用层、端口通信协议编程接口 - http,socket,tcp/ip 网络传输与通讯知识总结
- 为什么使用Sass
- [转]如何启用Ubuntu的休眠模式
- NYOJ题目1051simone牌文本编辑器
- Java反射机制深入研究
- linux下一键安装 powershell,的bash脚本
- 驱动之路-platform简例按键驱动☆☆☆
- HDOJ/HDU 1328 IBM Minus One(水题一个,试试手)
- 深入理解Fsync----JBD内核调试 专业打杂程序员 @github yy哥
- Unity NGUI Tween动画回调不执行问题
- centos7 下安装mysql教程
- [转]启动tensorboard
- Git实战手册(三): stash解惑与妙用
- Swift 栈和堆
- C#-1-2-C#基础
- Visual Studio 2015 开发Android Cordova出现unsupported major minor version 52.0错误的解决方法
- MQTT服务器搭建--Mosquitto用户名密码配置
- 《Python黑帽子:黑客与渗透测试编程之道》 Scapy:网络的掌控者
- 【node.js】回调函数