- 浏览: 379924 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出一个有向带权图,设1为源点,n为汇点。现在要在2~n-1的点中加上一条容量为无穷的边使得这个图的最小割最大。求加上这条边后最小割最大是多少。
大致思路:
先对原图求一遍最小割,割值为maxflow,在残余网络中分别找到两个点a,b,使得从1点到a的最大流值最大,为flowA,从b点到n点的最大流最大,为flowB。然后用maxflow+min(flowA,flowB)得到的就是答案。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; class node{ public: int u,v,next; int c; int cnm; };node edge[200050]; int ne, head[1000]; int cur[1000], ps[1000], dep[1000],n,m,ans,cnts,cntt; bool f[1000],ff[1000]; const int inf=90000000; void addedge(int u, int v,int c){ // dinic的加边,还是有点不同的。 edge[ne].u = u; edge[ne].v = v; edge[ne].c = c; edge[ne].next = head[u]; edge[ne].cnm=ne+1; head[u] = ne ++; edge[ne].u = v; edge[ne].v = u; edge[ne].c =0; edge[ne].next = head[v]; edge[ne].cnm=ne-1; head[v] = ne ++; } int dinic(int s, int t){ // dinic模板:源点为s,汇点为t 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; } void dfs1(int v){ // cout<<"v1 "<<v<<endl; f[v] = 1; cnts++; for(int i = head[v]; i != 0; i = edge[i].next){ int vs=edge[i].v; if(f[vs]==0&&edge[i].c) dfs1(vs); } } void dfs2(int v){ // cout<<"v2 "<<v<<endl; ff[v] = 1; cntt++; for(int i = head[v]; i != 0; i =edge[i].next){ int vs=edge[i].v; if(ff[vs]==0&&edge[edge[i].cnm].c) dfs2(vs); } } int aaa[100001]; int main(){ int i,j,cas,a,b,c,maxflow; scanf("%d",&cas); while(cas--){ ne=2; maxflow=0; cnts=cntt=0; memset(head,0,sizeof(head)); scanf("%d%d",&n,&m); while(m--){ scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } maxflow=dinic(1,n); memset(f,0,sizeof(f)); memset(ff,0,sizeof(ff)); dfs1(1); dfs2(n); int a1=0,a2=0; for(i=2;i<ne;i++){ aaa[i]=edge[i].c; // cout<<i<<" edge "<<edge[i].c<<endl; } for(i=2;i<n;i++){ if(f[i]){ for(j=2;j<ne;j++){ edge[j].c=aaa[j]; // cout<<j<<" edge "<<edge[j].c<<endl; } a1=max(a1,dinic(1,i)); // cout<<"a1 "<<a1<<endl; } if(ff[i]){ for(j=2;j<ne;j++){ edge[j].c=aaa[j]; // cout<<j<<" edge "<<edge[j].c<<endl; } a2=max(a2,dinic(i,n)); // cout<<"a2 "<<a2<<endl; } } cout<<maxflow+min(a1,a2)<<endl; } return 0; }
发表评论
-
[kruskal]hdoj 4786
2014-10-29 20:38 674大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 856题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1324题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1109题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 774大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 838读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 918题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1619大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1611大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1081大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1231大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 1935大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 988大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292:Food
2012-09-16 17:15 2230大致题意: 有F种食物和D种饮料,每种食物或饮料只能 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1311大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1080大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1109大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1116大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 929大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 943大致题意: 有n种原材料,每种一件。现在给出m个组合 ...
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
Problem Description Calculate A + B. Input Each line will contain two integers A and B....HDOJ 代码: #include int main() { int a,b; while(scanf("%d %d",&a,&b)!=EOF) printf("%d\n",a+b); }
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md 是工具自动生成 (无聊...
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码