zoj 3229 有源汇有上下界的最大流模板题

/*坑啊,pe的程序在zoj上原来是wa。 题目大意:一个?潘扛?个女神拍照,计划拍照n天,每一天?潘孔疃喔?个女神拍照,每天拍照数不能超过D张,而且给每个女神i拍照有数量限制[Li,Ri], 对于每个女神n天的拍照总和不能超过Gi,如果有解求?潘孔疃嗄芘亩嗌僬耪眨?⑶竺刻旄?杂ε?衽亩嗌僬耪眨环裨蚴涑?1。 解题思路:增设一源点st,汇点sd,st到第i天连一条上界为Di下界为0的边,每个女神到汇点连一条下界为Gi上界为oo的边,对于每一天,当天到第i个女孩连一条[Li,Ri]的边。 建图模型:源点s,终点d。超级源点ss,超级终点dd。首先判断是否存在满足所有边上下界的可行流,方法可以转化成无源汇有上下界的可行流问题。怎么转换呢? 增设一条从d到s没有下界容量为无穷的边,那么原图就变成了一个无源汇的循环流图。接下来的事情一样,超级源点ss连i(du[i]>0),i连超级汇点(du[i]0)之和时,有可行流,否则没有。 当有可行流时,删除超级源点ss和超级终点dd,再对(s,d)进行一次最大流,此时得到的maxflow则为题目的解。为什么呢? 因为第一次maxflow()只是求得所有满足下界的流量,而残留网络(s,d)路上还有许多自由流(没有和超级源点和超级汇点连接的边)没有流满, 所有最终得到的maxflow=(第一次流满下界的流+第二次能流通的自由流)。 */ #include #include #include using namespace std; #define N 1500 #define ii 400000 #define inf 0x3fffffff struct node { int u,v,w,f,next; }bian[ii*2]; int head[N],yong,dis[N],work[N]; void init(){ yong=0; memset(head,-1,sizeof(head)); } void addbian(int u,int v,int w,int f) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].f=f; bian[yong].next=head[u]; head[u]=yong++; } void add(int u,int v,int w,int f) { addbian(u,v,w,f); addbian(v,u,0,f); } int min(int a,int b) { return aq; q.push(s); dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==-1) { dis[v]=dis[u]+1; q.push(v); if(v==t) return 1; } } } return 0; } int dfs(int s,int limit,int t) { if(s==t)return limit; for(int &i=work[s];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==dis[s]+1) { int tt=dfs(v,min(limit,bian[i].w),t); if(tt) { bian[i].w-=tt; bian[i^1].w+=tt; return tt; } } } return 0; } int dinic(int s,int t) { int ans=0; while(bfs(s,t)) { memcpy(work,head,sizeof(head)); while(int tt=dfs(s,inf,t)) ans+=tt; } return ans; } int main() { int n,m,i,j,k,s,t,S,T,a,b,d,index[ii],id,suma,w[N]; while(scanf("%d%d",&n,&m)!=EOF) { init(); s=0;t=m+n+1; S=t+1;T=S+1; memset(w,0,sizeof(w)); for(i=1;i0) { suma+=w[i]; add(S,i,w[i],0); } else add(i,T,-w[i],0); } int f=dinic(S,T); if(f==suma) { head[S]=head[T]=-1; printf("%d\n",dinic(s,t)); for(i=0;i

点击复制链接 与好友分享!回本站首页

您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:POJ 3071 Football(简单 概率DP)
下一篇:杭电 1754 I Hate It(线段树求最值)
相关文章

HDU 3157 Crazy Circuits(有源汇上

HDU 3157 Crazy Circuits(有源汇上

POJ 2396 Budget 有上下界的网络流

SGU 194 无源无汇上下界网络流

ACM:二分查找,以及利用二分法来找上

Acdream 1171 Matrix sum 上下界费用流

hdu 4940 无源汇有上下界最大流

C++/CLR泛型与C++模板的对比

图文推荐
zoj 3229 有源汇有上下界的最大流模板题
ZOJ 3640 Help Me
zoj 3229 有源汇有上下界的最大流模板题
CF 518C(Anya and
zoj 3229 有源汇有上下界的最大流模板题
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-07 人气:18
本文关键词:
分享到:

相关文章

  • Acdream 1171 Matrix sum 上下界费用流 2012-01-10

    题目链接:点击打开链接 Matrix sum Time Limit: 8000/4000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others) SubmitStatisticNext Problem Problem Description sweet和zero在玩矩阵游戏,sweet画了一个N * M的矩阵,矩阵的每个格子有一个整数。zero给出N个数Ki,和M个数Kj,zero要求sweet选出一些数,满足从第 i 行至少选出了Ki

  • SGU 194 无源无汇上下界网络流 2013-10-14

    题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=194 题意: n 个点 m条有向边 u v l r 代表该边的流量区间为 [l,r] 若存在最大流则输出每条边的流量 若不存在则输出NO #include #include #include #include #include #include using namespace std; #define ll int #define N 10004 #define M 105000

  • HDU 3157 Crazy Circuits(有源汇上下界最小流) 2013-10-29

    HDU 3157 Crazy Circuits 题目链接 题意:一个电路板,上面有N个接线柱(标号1~N),还有两个电源接线柱 + -,给出一些线路,每个线路有一个下限值求一个可以让所有部件正常工作的总电流 没有则输出impossible 思路: 有源汇有上下界求最小流,建模方法为: 按无源汇先建图,跑超级源汇ss->tt一次,然后加入t->s,容量INF的边,在跑一次ss->tt,如果是满流,就有解,解为t->s边的当前流量 顺带写个最大流的,最大流就先把t->s

  • zoj 2822 Sum of Different Primes (01背包) 2012-01-18

    ///给你n 求他能分解成多少个的不同的k个素数相加之和 ///01背包,素数打表 # include # include # include # include # include using namespace std; int cot; int used[1500]; int prime[1500]; void sushu()///素数打表 { memset(used,0,sizeof(used)); cot=0; for(int i=2; i=1;j--) { for(p=n;p>

  • ZOJ 3723 Starfruit 2012-02-09

    恶心的状压DP。。。 与炮兵阵地类似。。。多了两个方向。而且发射的炮弹可能被石头挡住。。。。 1.因为方向是对称的,所以可以把下面两条边翻上来,考虑这样只要考虑上面的行就行了。。。。 2.被石头挡住。。。可以模拟一下 3.卡内存。。。。要用滚动数组+把可能的状态存下来 Starfruit Time Limit: 4 Seconds Memory Limit: 65536 KB Plants VS Zombie is an interesting game, recently Edward has

  • ZOJ 3644 Kitty's Game (记忆化搜索) 2012-02-11

    OJ题目:click here~~ 题目分析:1e6的约数很大 , 但是个数确很少,不到60个。所以状态可以简化为dp[ i ][ j ] , j为约束的id 。 AC_CODE const int mod = 1000000007; vector List[2001]; int num[2008]; int dp[2008][60]; int n , k , ans = 0; map mp; inline int gcd(int x , int y){ return y == 0 ? x :

  • ZOJ 1655 Transport Goods 2012-02-16

    The HERO country is attacked by other country. The intruder is attacking the capital so other cities must send supports to the capital. There are some roads between the cities and the goods must be transported along the roads. According the length of

  • ZOJ 2476 Total Amount 2012-02-17

    题意: 比较简单的题目,就是把给定格式的数字加起来,再按规定格式输出,想想感觉很简单,写起来还是不是很顺,wa了5次,能注意的点都注意了,重新写了一遍才过的。现在总结以下几点易错点: 1.像小于10和小于100的需要特判。 2.不要用double解,精度不能保证,最后处理也烦,建议直接把数字读出来,虽说范围是int内,但不知道数据会不会坑,最好用long long。 3.处理','的时候,要注意总长度减去小数点后两位后刚好能整除3的情况,要注意这种情况下最前面不能带有','。 总结:虽说是简单题

  • ZOJ 3209 Dancing Links 2012-03-04

    思路:这题挺好的,本来模板不是自己敲的嘛,理解了Dancing Links后是找了一个模板的,然后正好这题让自己加深理解了,也知道在实际中怎么建矩阵求解了。 把n*m的矩阵看成n*m个格子,像那个数独一样,作为n*m列;每一个矩形一行。 行列都建好矩阵后,就可以用舞蹈链求解了。 问题即转化为从这些行中选择最少的一部分使每一列被覆盖且仅覆盖一次。 #pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #i

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.177 (s). 10 q(s)