POJ 1325 Machine Schedule(最小覆盖数)
http://poj.org/problem?id=1325
题意:
题目大意就是有两台机器A,B,分别由m和n种模式,初始时都在模式0,现在有k个工作,每一个工作都可以将A设置成模式i或将B设置成模式j,但每一次更换模式时机器不得不要重启,求完成所有工作的最小重启次数输入数据的第一行有三个数据,分别代表工作数,A/B的模式数,当输入0时结束程序,接下来多行,每行的开始代表工作的序号,和完成该工作需将A/B设置的模式数,输出一个整数,代表机器最小重启次数.
分析:
首先由于A和B机器初始都是模式0,所以我们对于输入任务可以在A 0 模式或B 0 模式下完成的,我们直接不考虑这些任务. 因为这些任务不会对最终机器最小重启次数有任何影响.
下面我们只考虑那些只能在A 模式 1 到n-1 和B模式 1到m-1 下完成的任务.
把A的1到n-1个模式看成是左边的n-1个点,把B模式的1到m-1个任务看成右边的m-1个点. 对于每个任务(x,i,j) ,连一条左边第i个点与右边第j个点的无向边. 那么该图的每条边就表示一个任务了.我们想要使得机器的重启次数最少,就是要在左边和右边选出总数最少的节点(每个节点代表机器重启了一次),让这些节点覆盖所有的边(即任务).
那么就是求该无向图的最小覆盖 = 无向图的最大匹配数.
注意:就算不同编号的任务所构成的边重复,依然能正确计算.因为最大匹配计算的是匹配的点对数目.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=100+5;
struct Max_Match
{
int n,m;
vector<int> g[maxn];
bool vis[maxn];
int left[maxn];
void init(int n,int m)
{
this->n=n;
this->m=m;
for(int i=1;i<=n;i++) g[i].clear();
memset(left,-1,sizeof(left));
}
bool match(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=true;
if(left[v]==-1 || match(left[v]))
{
left[v]=u;
return true;
}
}
}
return false;
}
int solve()
{
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ans++;
}
return ans;
}
}MM;
int main()
{
int n,m,k;
while(scanf("%d",&n)==1&&n)
{
scanf("%d%d",&m,&k);
MM.init(n-1,m-1);
while(k--)
{
int i,u,v;
scanf("%d%d%d",&i,&u,&v);
if(u==0 || v==0) continue;
MM.g[u].push_back(v);
}
printf("%d\n",MM.solve());
}
return 0;
}
分享到:
相关推荐
poj2516代码最小费用最大流
【标题】"POJ1276-Cash Machine"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Set of Peking University)。这个题目挑战程序员解决现金自动取款机(ATM)的现金提取问题,涉及到算法设计和实现。 ...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
标题“poj1251 最小生成树”是一个编程竞赛题目,来源于著名的在线编程平台POJ(Programming Online Judge)。这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
根据提供的信息,我们可以将POJ(Peking Online Judge)平台上的算法题目按照不同的类别进行整理与解析。这对于希望系统性地提高自己算法能力的学习者来说非常有用。下面将基于给出的分类来详细介绍每一类算法的核心...
* 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、poj3026。 * 拓扑排序:例如 poj1094。 * 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。...
北大POJ1276试题代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2206 Magic Multiplying Machine.md
总的来说,POJ第1861题是一道关于最小生成树的问题,要求参赛者运用图论知识和算法技巧编写程序,解决一个实际的计算问题。通过深入理解最小生成树的理论,熟练掌握Prim和Kruskal算法,以及熟悉编程语言的实现细节,...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
- 最小生成树算法:如Prim算法和Kruskal算法,用于找出图中的最小生成树,如`poj1789, poj2485`。 - 拓扑排序:适用于有向无环图,用于确定任务的执行顺序,如`poj1094`。 - 二分图的最大匹配:如匈牙利算法,...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
快速排序、归并排序和堆排序等,不仅用于排序,也常用于解决与逆序数相关的问题,如poj2388。 #### 并查集 用于处理集合的合并与查询操作,如poj3349所示。 #### 哈希表 高效查找数据的工具,利用哈希函数将数据...
这可能涉及到计算和处理大量正方形,例如找出一个范围内的所有完全平方数,或者计算不同大小正方形覆盖区域的重叠部分。动态规划是一种可能的解决方案,因为它能够有效地处理具有重叠子问题和最优子结构的复杂问题。...
#### 1325 Machine Schedule - 二分匹配 (最小点覆盖) - **知识点**:最小点覆盖问题,即在二分图中找到覆盖所有边所需的最少顶点集。 #### 1422 Air Raid - 二分匹配 - **知识点**:二分匹配算法。 #### 1459 ...
【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...