题意:有N场比赛,每场比赛需要一定数量的题目数,现在有M个题目,每个题目只能提供给特定的几场比赛,并且一次只能在一场比赛中出现。
问最多可以举办多少场比赛。
思路:因为N = 15 , 所以直接二进制枚举举办的比赛的情况,然后对于每种情况建图,
S - >题目,流量1
题目 ->比赛,流量1
比赛->T,流量为该场比赛需要的题目数。
每次都跑最大流,看是否等于所需的题目数,然后更新答案即可。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std;
#define N 222
#define M 5555
struct kdq {
int e , next , l ;
} ed[M] ;
int head[N] , num ;
void init() {
mem(head ,-1) ;
num = 0 ;
}
void add(int s ,int e ,int l) {
ed[num].e = e ;
ed[num].next = head[s] ;
ed[num].l = l ;
head[s] = num ++ ;
ed[num].e = s ;
ed[num].next = head[e] ;
ed[num].l = 0 ;
head[e] = num ++ ;
}
map<string ,int>MM;
int n , m ;
int a[N] ;
string x ;
int fk[111][111] ;
char now[M] ; int S , T ;
int deep[111] ;
int qe[111111] ; int dinic_bfs() {
mem(deep , -1) ;
deep[S] = 0 ;
int h = 0 , t = 0 ;
qe[h ++ ] = S ;
while(h > t) {
int tp = qe[t ++ ] ;
for (int i = head[tp] ; ~i ; i = ed[i].next ) {
int e = ed[i].e ;
int l = ed[i].l ;
if(l > 0 && deep[e] == -1) {
deep[e] = deep[tp] + 1 ;
qe[h ++ ] = e ;
}
}
}
return deep[T] != -1 ;
} int dinic_dfs(int now , int f) {
if(now == T)return f ;
int flow = 0 ;
for (int i = head[now] ; ~i ; i = ed[i].next ) {
int e = ed[i].e ;
int l = ed[i].l ;
if(deep[e] == deep[now] + 1 && l > 0 && (f - flow) > 0) {
int mm = min(l , f - flow) ;
int nn = dinic_dfs(e , mm) ;
flow += nn ;
ed[i].l -= nn ;
ed[i ^ 1].l += nn ;
}
}
if(!flow)deep[now] = -2 ;
return flow ;
} int dinic() {
int flow = 0 ;
while(dinic_bfs()) {
flow += dinic_dfs(S , inf) ;
}
return flow ;
}
int main() {
int ca = 0 ;
while(scanf("%d%d",&n,&m) , (n + m)) {
S = 0 , T = n + m + 1 ;
init() ;
MM.clear() ;
mem(fk ,0) ;
for (int i = 1 ; i <= n ; i ++ ) {
cin >> x ;
MM[x] = i ;
scanf("%d",&a[i]) ;
}
string st ;
st.clear() ;
gets(now) ;
for (int i = 1 ; i <= m ; i ++ ) {
gets(now) ;
st.clear() ;
int l = strlen(now) ;
if(l == 0)continue ;
for (int j = 0 ; j < l ; j ++ ) {
if(now[j] == ' ') {
if(st.size() == 0)continue ;
fk[MM[st]][i] = 1 ;
st.clear() ;
continue ;
}
st += now[j] ;
}
if(st.size()) {
fk[MM[st]][i] = 1 ;
}
}
int ans = 0 ;
for (int i = 0 ; i < (1 << n) ; i ++ ) {
init() ;
int nk = 0 ;
int sum = 0 ;
for (int j = 1 ; j <= m ; j ++ )add(S , j , 1) ;
for (int j = 0 ; j < n ; j ++ ) {
if(i & (1 << j)) {
for (int k = 1 ; k <= m ; k ++ ) {
if(fk[j + 1][k]) {
add(k , j + 1 + m , 1) ;
}
}
nk ++ ;
sum += a[j + 1] ;
add(j + 1 + m , T , a[j + 1]) ;
}
}
int fff = dinic() ;
if(fff == sum)ans = max(ans , nk) ;
}
printf("Case #%d: %d\n",++ ca ,ans) ;
}
return 0 ;
}
UVALIVE 4819 最大流的更多相关文章
-
POJ 1459 Power Network / HIT 1228 Power Network / UVAlive 2760 Power Network / ZOJ 1734 Power Network / FZU 1161 (网络流,最大流)
POJ 1459 Power Network / HIT 1228 Power Network / UVAlive 2760 Power Network / ZOJ 1734 Power Networ ...
-
uvalive 3231 Fair Share 公平分配问题 二分+最大流 右边最多流量的结点流量尽量少。
/** 题目: uvalive 3231 Fair Share 公平分配问题 链接:https://vjudge.net/problem/UVALive-3231 题意:有m个任务,n个处理器,每个任 ...
-
BZOJ 4819 Luogu P3705 [SDOI2017]新生舞会 (最大费用最大流、二分、分数规划)
现在怎么做的题都这么水了.. 题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=4819 (luogu) https://ww ...
-
UVALive - 6266 Admiral 费用流
UVALive - 6266 Admiral 题意:找两条完全不相交不重复的路使得权值和最小. 思路:比赛的时候时间都卡在D题了,没有仔细的想这题,其实还是很简单的,将每个点拆开,连一条容量为1,费用 ...
-
UVALive 6887 Book Club 最大流解最大匹配
题目连接: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show ...
-
UVALive - 6571 It Can Be Arranged 最大流
题目链接: http://acm.hust.edu.cn/vjudge/problem/48415 It Can Be Arranged Time Limit: 3000MS 问题描述 Every y ...
-
Uvalive 4865 Data Recovery 最大流
题意就是 给一个50 * 50的矩阵 然后给出每行每列元素的和 和一个初始矩阵 矩阵中有些是未知,有些是已知 然后我们求目标矩阵就是把能确定的元素的值求出来,实在不能确定的就置为-1 所有矩阵元素的值 ...
-
UVALive 3645 Objective: Berlin(最大流 :时序模型)
题意:已知n(n <= 150)个城市和m(m <= 5000)个航班,每个航班有出发地.到达地.乘坐人数.起飞时间和降落时间(时间用时和分表示),求从一个指定城市出发,去往另一个指定城市 ...
-
【Uvalive 2531】 The K-League (最大流-类似公平分配问题)
[题意] 有n个队伍进行比赛,每场比赛,恰好有一支队伍取胜.一支队伍败.每个队伍需要打的比赛场数相同,给你每个队伍目前已经赢得场数和输得场数,再给你一个矩阵,第 i 行第 j 列 表示队伍 i 和队伍 ...
随机推荐
-
.NetCore~框架版本号不同引起dotnet不能run它
对于.netCore来说,今年已经推出了正式版,这要求使用vs2015的开发者需要升级到beta3版,而如果使用老版VS开始的.netCore应用程序,它的架构版本将为是测试版"versio ...
-
win2008远程桌面会话数增加
1.[解决]由于没有远程桌面授权服务器可以提供许可证,远程回话被中断 你看到的这个文章来自于http://www.cnblogs.com/ayanmw 由于windows server 2008 R2 ...
-
TortoiseSVN文档
https://tortoisesvn.net/docs/release/TortoiseSVN_zh_CN/index.html TortoiseSVN 针对 Windows 平台的 Subvers ...
-
卷积神经网络CNN介绍:结构框架,源码理解【转】
1. 卷积神经网络结构 卷积神经网络是一个多层的神经网络,每层都是一个变换(映射),常用卷积convention变换和pooling池化变换,每种变换都是对输入数据的一种处理,是输入特征的另一种特征表 ...
-
session的固化(搁置)
Session在其生命周期中,可能会在运行时状态和持久化状态之间转换. 会话从运行时状态变为持久化状态的过程称为 -- 搁置:在以下情况下,Session会被搁置: 当服务器总之或单个Web应用终止时 ...
-
Linux 进程间通信(包含一个经典的生产者消费者实例代码)
前言:编写多进程程序时,有时不可避免的需要在多个进程之间传递数据,我们知道,进程的用户的地址空间是独立,父进程中对数据的修改并不会反映到子进程中,但内核是共享的,大多数进程间通信方式都是在内核中建立一 ...
-
vue2中使用transition
最终效果为 div元素从右向左出现, 然后从左向右消失. transition标签包裹要移动的元素: css 样式: 其中: 1: 为div元素显示时的状态 2: 为div元素移动的过程 (进入 ...
-
IE 浏览器的兼容性列表设置
打开 IE 浏览器 IE8 为例如:
-
Linux输入输出重定向和文件查找值grep命令
Linux输入输出重定向和文件查找值grep命令 一.文件描述符Linux 的shell命令,可以通过文件描述符来引用一些文件,通常使用到的文件描述符为0,1,2.Linux系统实际上有12个文件描述 ...
-
爬虫开发13.UA池和代理池在scrapy中的应用
今日概要 scrapy下载中间件 UA池 代理池 今日详情 一.下载中间件 下载中间件(Downloader Middlewares) 位于scrapy引擎和下载器之间的一层组件. - 作用: ( ...