- 浏览: 377014 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
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 662大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 845题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1311题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1095题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 765大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 828读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 902题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1609大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1593大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1068大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1220大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 1917大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 973大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1299大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1067大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1094大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1103大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 919大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 931大致题意: 有n种原材料,每种一件。现在给出m个组合 ... -
[最小费用流]zoj 3308:Move the Knights
2012-06-15 15:45 931大致题意: 一个国际象棋棋盘上有n个马分布在不同的黑 ...
相关推荐
ACM/ICPC参赛者必备!模版库,数十页的C++代码,涵盖ACM/ICPC中出现的各种算法!此为吉林大学版,内容相对比较全,排版质量是各校的模板中最好的!
ACM/ICPC亚洲预赛成都赛区网络赛真题,分享给广大热衷于ACM的人们们!
ACM/ICPC大赛
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中国*辽宁第二届大学生程序设计竞赛题目
2010年ACM/ICPC珠海区域赛决赛题目
acm/icpc算法集合。acm/icpc算法集合。acm/icpc算法集合。
ACM/ICPC World Finals 1990 task
搜索
ACM/ICPC的教学与实践
浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
有关于2011华中南赛区ACM/ICPC程序设计邀请赛及“永新视博”杯程序设计大赛的解题报告,希望对名位有所帮助!!!!!
THE 30th ACM/ICPC ASIA REGIONAL 2005 HANGZHOU SITE Onsite Contest Session 8:30am – 13:30pm, November 20th 2005 (GMT+8) <br>知道是什么了吧。。。
ACM/ICPC模板 内容大概有这些 其他 --高精度模板 --RMQ --改点堆优化的dijkstra算法 --快速付利叶变换 --稳定婚姻问题 --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --...
本代码包括了常见的ACM算法,并给出了详细地实现过程,并附上了ACM/ICPC 竞赛之STL。
吉林大学计算机科学学院2005年制作的ACMICPC代码库