- 浏览: 389115 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
有F种食物和D种饮料,每种食物或饮料只能供有限次,且每个人只享用一种食物和一种饮料。现在有n头牛,每个人都有自己喜欢的食物种类列表和饮料种类列表,问最多能使几个人同时享用到自己喜欢的食物和饮料。
大致思路:
把人给拆点,把食物和水的点放在人的两侧
求出s到t的网络流即可
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int inf=1<<30; const int nMax=101050; const int mMax=3000000; class node{ public: int c,u,v,next; };node edge[mMax]; int ne, head[nMax]; int cur[nMax], ps[nMax], dep[nMax]; void addedge(int u, int v,int w){ ////dinic邻接表加边 // cout<<u<<" add "<<v<<" "<<w<<endl; edge[ne].u = u; edge[ne].v = v; edge[ne].c = w; edge[ne].next = head[u]; head[u] = ne ++; edge[ne].u = v; edge[ne].v = u; edge[ne].c = 0; edge[ne].next = head[v]; head[v] = ne ++; } int dinic(int s, int t){ // dinic int tr, res = 0; int i, j, k, f, r, top; while(1){ memset(dep, -1, sizeof(dep)); for(f = dep[ps[0]=s] = 0, r = 1; f != r;) for(i = ps[f ++], j = head[i]; j; j = edge[j].next) if(edge[j].c && dep[k=edge[j].v] == -1){ dep[k] = dep[i] + 1; ps[r ++] = k; if(k == t){ f = r; break; } } if(dep[t] == -1) break; memcpy(cur, head, sizeof(cur)); i = s, top = 0; while(1){ if(i == t){ for(tr =inf, k = 0; k < top; k ++) if(edge[ps[k]].c < tr) tr = edge[ps[f=k]].c; for(k = 0; k < top; k ++){ edge[ps[k]].c -= tr; edge[ps[k]^1].c += tr; } i = edge[ps[top=f]].u; res += tr; } for(j = cur[i]; cur[i]; j = cur[i] =edge[cur[i]].next){ if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break; } if(cur[i]){ ps[top ++] = cur[i]; i = edge[cur[i]].v; } else{ if(top == 0) break; dep[i] = -1; i = edge[ps[-- top]].u; } } } return res; } int food [10000]; int drink[10000]; char str[500][500]; int main() { int n,i,j,a,b,c,nf,nd,s,t; while(scanf("%d%d%d",&n,&nf,&nd)!=EOF) { s=0,t=nf+nd+n+n+10; ne=2; memset(head,0,sizeof(head)); for(i=1;i<=nf;i++) { scanf("%d",&food[i]); addedge(0,i,food[i]); } for(i=1;i<=nd;i++) { scanf("%d",&drink[i]); addedge(i+nf,t,drink[i]); } for(i=1;i<=n;i++) { addedge(nd+nf+i,nd+nf+n+i,1); } for(i=1;i<=n;i++) { scanf("%s",str[i]+1); for(j=1;j<=nf;j++) { if(str[i][j]=='Y') { addedge(j,nf+nd+i,1); } } } for(i=1;i<=n;i++) { scanf("%s",str[i]+1); for(j=1;j<=nd;j++) { if(str[i][j]=='Y') { addedge(nf+nd+n+i,nf+j,1); } } } cout<<dinic(s,t)<<endl; } return 0; }
评论
11 楼
暴风雪
2012-09-23
proverbs 写道
暴风雪 写道
proverbs 写道
YM 非递归的dinic!
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
大概是10^3左右的数量级吧,要看情况而定~~
不是吧,sap和dinic不都是n*n*m的么?最坏情况也就10^2把。
递归会用到系统栈神马的~~反正效率不高
10 楼
proverbs
2012-09-22
暴风雪 写道
proverbs 写道
YM 非递归的dinic!
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
我会说我的dinic也是考别人的模版么,欢迎鄙视~~反正一般递归的效率都不高,我的一个学妹acmer亲测的
妹子!!给有妹子的跪了!我们学校没有一个学OI(未来的ACMER)的妹子。。。寂寞ing,
9 楼
proverbs
2012-09-22
暴风雪 写道
proverbs 写道
YM 非递归的dinic!
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
大概是10^3左右的数量级吧,要看情况而定~~
不是吧,sap和dinic不都是n*n*m的么?最坏情况也就10^2把。
8 楼
proverbs
2012-09-22
是有复制按
呃,我不知道诶。在“cpp代码”旁边不是有复制按钮么
不是代码啦,是代码上面的中文,不知是我电脑的原因?复制不了。
暴风雪 写道
proverbs 写道
只能通过查看源代码来复制。。。。我侵犯版权了??
呃,我不知道诶。在“cpp代码”旁边不是有复制按钮么
不是代码啦,是代码上面的中文,不知是我电脑的原因?复制不了。
7 楼
暴风雪
2012-09-21
proverbs 写道
YM 非递归的dinic!
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
我会说我的dinic也是考别人的模版么,欢迎鄙视~~反正一般递归的效率都不高,我的一个学妹acmer亲测的
6 楼
暴风雪
2012-09-21
proverbs 写道
YM 非递归的dinic!
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
大概是10^3左右的数量级吧,要看情况而定~~
5 楼
暴风雪
2012-09-21
proverbs 写道
只能通过查看源代码来复制。。。。我侵犯版权了??
呃,我不知道诶。在“cpp代码”旁边不是有复制按钮么
4 楼
proverbs
2012-09-19
只能通过查看源代码来复制。。。。我侵犯版权了??
3 楼
proverbs
2012-09-19
为什么你的网页上的字不能复制。。。。
2 楼
proverbs
2012-09-19
YM 非递归的dinic!
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
嗯,弱弱的问一句,一般网络流点的个数,递归的不会爆栈吧?
如果点太多,必然就TLE了吧
1 楼
proverbs
2012-09-19
这题是HDU 4292.。。题目打错了貌似。。。
发表评论
-
[kruskal]hdoj 4786
2014-10-29 20:38 703大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 884题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1359题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1140题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 815大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 868读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 979题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1670大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1687大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1166大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1305大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 2033大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 1053大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1354大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1139大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1143大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1156大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 966大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 972大致题意: 有n种原材料,每种一件。现在给出m个组合 ... -
[最小费用流]zoj 3308:Move the Knights
2012-06-15 15:45 1021大致题意: 一个国际象棋棋盘上有n个马分布在不同的黑 ...
相关推荐
### ACM/ICPC常用算法的代码库(吉林大学版,强烈推荐) #### 概述 这份文档提供了由吉林大学计算机科学与技术学院整理的一套针对ACM/ICPC竞赛的算法代码库。它包含了多种算法及其实现方式,适用于ACM/ICPC参赛者的...
以下是ACM/ICPC的教学与实践的知识点: 一、ACM/ICPC的概念和特点 * ACM/ICPC是由国际计算机界权威组织美国计算机协会主办的世界公认的规模最大、水平最高的国际大学生程序设计竞赛。 * 该项竞赛旨在使大学生运用...
**ACM/ICPC大赛全称是ACM国际大学生程序设计竞赛(International Collegiate Programming Contest),是一项享誉全球的计算机科学竞赛。自1970年创办以来,它已经成为衡量大学计算机科学教育水平的重要标志之一,...
《ACM/ICPC题集》是吉林大学计算机科学学院在2005年精心制作的一份宝贵资源,专门针对ACM(国际大学生程序设计竞赛)/ICPC(国际大学生程序设计竞赛)进行训练和学习。这个压缩包包含了一本名为“ACM.pdf”的文档,...
### ACM/ICPC竞赛训练(北京大学暑期夏令营内容一览) #### 一、概述 ACM/ICPC(国际大学生程序设计竞赛)是一项面向全球大学生的计算机编程与算法设计比赛,旨在通过解决复杂的计算问题来培养学生的创新能力和...
《ACM/ICPC竞赛训练》是北京大学暑期课程的一个重要组成部分,主要针对计算机科学领域内的算法竞赛进行深度训练。在这些课程中,"搜索"是一个核心主题,涉及到一系列的算法和策略,旨在解决复杂的问题。这里我们将...
通过这个压缩包,我们可以深入探讨ACM/ICPC的相关知识点,包括其重要性、发展历程以及参赛者的心路历程。 首先,让我们谈谈“算法还重要么”这一话题。在ACM/ICPC中,算法的重要性不言而喻。算法是解决问题的关键...
ACM/ICPC2009 拉丁美洲区域赛 包含输入输出数据 题目PDF文档 详细解题报告+答案代码TXT文档 有一半是水题,2、3个比较难的 大家可以拿来做做 其中的输入输出数据,可以放到那个离线OJ系统去判断你的程序对错。(离线...
The 36th ACM/ICPC Asia Regional Shanghai Site —— Online Contest Problem Set
《ACM/ICPC全球总决赛试题集锦》是编程竞赛领域的瑰宝,它汇集了从1992年至2008年ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest,简称ACM/ICPC)全球总决赛的全部试题。这个珍贵的...
ACM/ICPC中国*辽宁第二届大学生程序设计竞赛题目
### ACM/ICPC亚洲预赛成都赛区网络赛 #### A. ASimpleProblem **知识点:** 1. **问题描述:** - 在本题中,给出了一行键盘上的数字键,用户通过两个特定的手指(一个在左,一个在右)进行输入。 - 每个手指在...
对于ACM/ICPC的新手,以下是一些关键点: 1. **在线评测系统**:OJ如杭电OJ(http://acm.hdu.edu.cn/)是学习和练习的重要平台。它提供各种难度的编程题目,并自动评估你的代码是否正确。在OJ上注册账号并开始做题...
2010年ACM/ICPC珠海区域赛决赛题目
### ACM/ICPC世界总决赛1990任务解析:罕见排序与方格游戏 #### 知识点一:罕见排序(Rare Order) 在1990年的ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest, ICPC)世界总决赛中,...
**ACM/ICPC培训讲义**是针对国际大学生程序设计竞赛(ACM/ICPC)准备的一份重要参考资料,旨在提升参赛者在算法和程序设计方面的能力。这份讲义涵盖了多个关键领域的知识,包括**搜索算法**、**计算几何**、**动态...
在ACM/ICPC竞赛中,图论问题是常见的题目来源,涉及到的问题包括最短路径、最小生成树、网络流、拓扑排序等。最大矩阵乘积问题虽然表面上可能不直接涉及图,但在优化策略中,可以借助图论的思想,如贪心选择和动态...
【ACM/ICPC微型Judge系统详解】 在编程竞赛领域,特别是ACM(国际大学生程序设计竞赛)/ICPC(国际大学生程序设计竞赛)中,Judge系统扮演着至关重要的角色。它负责评判参赛团队提交的代码是否能正确解决特定问题。...
【摘要】中提到的“融入ACM/ICPC竞赛的程序设计类课程教学改革与探讨”主要关注如何改进计算机科学与技术、软件工程等专业的程序设计教育,以应对学生逻辑思维能力相对较弱的问题。ACM/ICPC(国际大学生程序设计竞赛...