【poj1274】 The Perfect Stall

时间:2022-09-19 22:52:18

http://poj.org/problem?id=1274 (题目链接)

题意

  懒得写了

Solution

  二分图匹配裸题。注意清空数组。

代码

// poj3020
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi 3.1415926535898
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=500;
struct edge {int next,to;}e[maxn<<2];
int head[maxn],p[maxn],vis[maxn],cnt,n,m; void insert(int u,int v) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
bool find(int x) {
for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) {
vis[e[i].to]=1;
if (p[e[i].to]==0 || find(p[e[i].to])) {
p[e[i].to]=x;
return 1;
}
}
return 0;
}
int main() {
while (scanf("%d%d",&n,&m)!=EOF) {
for (int i=1;i<=n;i++) p[i]=head[i]=0;
cnt=0;
for (int i=1;i<=n;i++) {
int x;scanf("%d",&x);
for (int j=1;j<=x;j++) {
int t;scanf("%d",&t);
insert(i,t);
}
}
int ans=0;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) vis[j]=0;
if (find(i)) ans++;
}
printf("%d\n",ans);
}
return 0;
}

  

【poj1274】 The Perfect Stall的更多相关文章

  1. POJ1274:The Perfect Stall(二分图最大匹配 匈牙利算法)

    The Perfect Stall Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 17895   Accepted: 814 ...

  2. 【leetcode】507&period; Perfect Number

    problem 507. Perfect Number solution: /* class Solution { public: bool checkPerfectNumber(int num) { ...

  3. 【LeetCode】279&period; Perfect Squares 解题报告(C&plus;&plus; & Java)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 四平方和定理 动态规划 日期 题目地址:https: ...

  4. 【LeetCode】507&period; Perfect Number 解题报告(Python & Java & C&plus;&plus;)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 日期 题目地址:https://leetcode.c ...

  5. 【POJ】3398 Perfect Service

    1. 题目描述某树形网络由$n, n \in [1, 10^4]$台计算机组成.现从中选择一些计算机作为服务器,使得每当普通计算机恰好与一台服务器连接(并且不超过一台).求需要指定服务器的最少数量 2 ...

  6. 【题解】UVA1218 Perfect Service

    UVA1218:https://www.luogu.org/problemnew/show/UVA1218 刷紫书DP题ing 思路 参考lrj紫书 不喜勿喷 d(u,0):u是服务器,孩子是不是服务 ...

  7. 【CodeForces】947 C&period; Perfect Security 异或Trie

    [题目]C. Perfect Security [题意]给定长度为n的非负整数数组A和数组B,要求将数组B重排列使得A[i]^B[i]的字典序最小.n<=3*10^5,time=3.5s. [算 ...

  8. 【LeetCode】数学(共106题)

    [2]Add Two Numbers (2018年12月23日,review) 链表的高精度加法. 题解:链表专题:https://www.cnblogs.com/zhangwanying/p/979 ...

  9. 【LeetCode】二分 binary&lowbar;search(共58题)

    [4]Median of Two Sorted Arrays [29]Divide Two Integers [33]Search in Rotated Sorted Array [34]Find F ...

随机推荐

  1. jQuery根据name取input值问题

    最近做项目用$("input[name=inputName]").val();去取input值得时候发现取值有问题:总是取第一次输入的值,如果在同一个页面不发生表单提交,然后将in ...

  2. linux命令:chgrp

    1.命令介绍: chgrp用来改变文件或目录所属组的权限,要改变成的组必须在/etc/group文件存在才可以. 2.命令格式: chgrp [选项] 组 文件 3.命令参数: 必要参数: -c 当发 ...

  3. 【原&plus;转】用CMake代替makefile进行跨平台交叉编译

    在开始介绍如何使用CMake编译跨平台的静态库之前,先讲讲我在没有使用CMake之前所趟过的坑.因为很多开源的程序,比如png,都是自带编译脚本的.我们可以使用下列脚本来进行编译: ./configu ...

  4. YARN内存使用优化配置

    在Hadoop2.0中, YARN负责管理MapReduce中的资源(内存, CPU等)并且将其打包成Container. 这样可以精简MapReduce, 使之专注于其擅长的数据处理任务, 将无需考 ...

  5. java实现渐变效果工具

    [html] view plain copy package gradient; import java.awt.Color; import java.awt.Dimension; import ja ...

  6. Servlet过滤器——过滤器分析流量

    1.概述 Servlet过滤器可以对用户提交的数据或服务器返回的数据进行更改.任何到达服务器的请求都会首先经过过滤器的处理.本实例应用过滤器的这个特点,编写了一个在过滤器中统计网站流量的实例. 本实例 ...

  7. CSS3制作日历

    目标是制作如下面DEMO显示的一个日历效果: HTML Markup 先来看看其结构: <div class="calendar"> <span class=&q ...

  8. Update Case的用法与execute执行字符串

    摘自于网路:http://www.cnblogs.com/joinger/articles/1297160.html update h_crm_SafetyAccessUser set         ...

  9. jQuery UI 入门之实用实例

    jQuery UI 入门 jQuery UI 简介 jQuery UI 是一个建立在 jQuery JavaScript 库上的小部件和交互库,您可以使用它创建高度交互的 Web 应用程序.无论您是创 ...

  10. Spark数据倾斜及解决方案

    一.场景 1.绝大多数task执行得都非常快,但个别task执行极慢.比如,总共有100个task,97个task都在1s之内执行完了,但是剩余的task却要一两分钟.这种情况很常见. 2.原本能够正 ...