POJ 1325 Machine schedine (二分图-最小点覆盖数=最大匹配边数)
There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, ..., mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, ... , mode_m-1. At the beginning they are both work at mode_0.
For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.
Obviously, to accomplish all the jobs, we need to change the machine's working mode from time to time, but unfortunately, the machine's working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.
Input
The input will be terminated by a line containing a single zero.
Output
Sample Input
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
Sample Output
3
题解:最小点覆盖数==最大匹配边数
参考代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<vector>
#include<map>
using namespace std;
const int maxn=;
int n,m,k,ok[maxn];
bool a[maxn][maxn],vis[maxn]; bool Find(int x)
{
for(int i=;i<=m;i++)
{
if(a[x][i]&&!vis[i])
{
vis[i]=true;
if(!ok[i]||Find(ok[i]))
{
ok[i]=x;
return true;
}
}
}
return false;
}
int maxP()
{
int ans=;
memset(ok,,sizeof(ok));
for(int i=; i<=n; i++)
{
memset(vis,false,sizeof(vis));
if(Find(i)) ans++;
}
return ans;
}
int main()
{
int kase=;
while(scanf("%d",&n) && n)
{
scanf("%d%d",&m,&k);
memset(a,false,sizeof(a));
int x,y,z;
while(k--)
{
cin>>x>>y>>z;
a[y][z]=true;
}
int ans=maxP();
int cnt=;
printf("%d\n",ans);
}
return ;
}
最新文章
- java中的锁
- Jquery 操作CheckBox ,RadioButtonList,DropDownList
- HQL查询——select子句
- kudu playground
- RandomUser – 生成随机用户 JSON 数据的 API
- find command in linux terminal
- js中的 !!
- ZOJ 1202 Divide and Count(排列组合)
- iOS8 Core Image In Swift:人脸检测以及马赛克
- Xcode-App Transport Security has blocked a cleartext HTTP (http://) resource load since it is insecure.
- JavaScript中的栈及通过栈操作的实例
- React Router 使用教程
- 使用rsync备份与同步文件
- frame的用法
- C++模板的要点
- 前端入门3-CSS基础
- Window应急响应(四):挖矿病毒
- Spring Boot 揭秘与实战 源码分析 - 工作原理剖析
- C++ STL 数据结构与算法 —— 排序
- pyinstaller 将.py生成.exe ----报错 “IndexError: tuple index out of range”
热门文章
- K8S入门系列之集群yum安装(一)
- Servlet相关学习
- 微服务SpringCloud之GateWay熔断、限流、重试
- Nginx做缓存服务器
- Sturts2整合Spring报错:org.springframework.beans.factory.BeanDefinitionStoreException: IOException parsing XML document from ServletContext resource [/WEB-INF/applicationContext.xml];
- Leetcode算法【114. 二叉树展开为链表】
- hdu 5495 LCS (置换群)
- mysql 索引笔记
- 简单地迁移你的android jni代码逻辑到iOS - 编写iOS下jni.h的替代 - ocni.h
- Redux中间件Redux-thunk的配置