ISAP 模板

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <queue>
  5
  6 using namespace std;
  7 const int INF=2147483647;
  8 const int maxn=210,maxm=410;
  9 int cnt,fir[maxn],nxt[maxm],cap[maxm],to[maxm],dis[maxn],gap[maxn],path[maxn];
 10
 11 void addedge(int a,int b,int c)
 12 {
 13     nxt[++cnt]=fir[a];
 14     to[cnt]=b;
 15     cap[cnt]=c;
 16     fir[a]=cnt;
 17 }
 18
 19 bool BFS(int S,int T)
 20 {
 21     memset(dis,0,sizeof(dis));
 22     dis[T]=1;
 23     queue<int>q;q.push(T);
 24     while(!q.empty())
 25     {
 26         int node=q.front();q.pop();
 27         for(int i=fir[node];i;i=nxt[i])
 28         {
 29             if(dis[to[i]])continue;
 30             dis[to[i]]=dis[node]+1;
 31             q.push(to[i]);
 32         }
 33     }
 34     return dis[S];
 35 }
 36 int fron[maxn];
 37 int ISAP(int S,int T)
 38 {
 39     if(!BFS(S,T))
 40         return 0;
 41     for(int i=1;i<=T;i++)++gap[dis[i]];
 42     int p=S,ret=0;
 43     memcpy(fron,fir,sizeof(fir));
 44     while(dis[S]<=T)
 45     {
 46         if(p==T){
 47             int f=INF;
 48             while(p!=S){
 49                 f=min(f,cap[path[p]]);
 50                 p=to[path[p]^1];
 51             }
 52             p=T;ret+=f;
 53             while(p!=S){
 54                 cap[path[p]]-=f;
 55                 cap[path[p]^1]+=f;
 56                 p=to[path[p]^1];
 57             }
 58         }
 59         int &ii=fron[p];
 60         for(;ii;ii=nxt[ii]){
 61             if(!cap[ii]||dis[to[ii]]+1!=dis[p])
 62                 continue;
 63             else
 64                 break;
 65         }
 66
 67         if(ii){
 68             p=to[ii];
 69             path[p]=ii;
 70         }
 71
 72
 73         else{
 74             if(--gap[dis[p]]==0)break;
 75             int minn=T+1;
 76             for(int i=fir[p];i;i=nxt[i])
 77                 if(cap[i])
 78                     minn=min(minn,dis[to[i]]);
 79             gap[dis[p]=minn+1]++;
 80             fron[p]=fir[p];
 81             if(p!=S)
 82                 p=to[path[p]^1];
 83         }
 84     }
 85     return ret;
 86 }
 87
 88 void Init()
 89 {
 90     memset(fir,0,sizeof(fir));
 91     cnt=1;
 92 }
 93 int main()
 94 {
 95     int n,m;
 96     while(~scanf("%d%d",&m,&n))
 97     {
 98         Init();
 99         for(int i=1;i<=m;i++){
100             int x,y,c;
101             scanf("%d%d%d",&x,&y,&c);
102             addedge(x,y,c);
103             addedge(y,x,0);
104         }
105         printf("%d\n",ISAP(1,n));
106     }
107
108     return 0;
109 }
时间: 02-26

ISAP 模板的相关文章

【CodeVS 1993】草地排水 isap模板题

开始网络流的学习,更新一下isap的模板 #include<cstdio> #include<cstring> #include<algorithm> #define read(x) x=getint() using namespace std; const int N = 403; int getint() { int k = 0, fh = 1; char c = getchar(); for(; c < '0' || c > '9'; c = getc

最大流isap模板

isap+bfs初始化+栈优化,点的编号从0开始: 1 const int MAXN = 100010; 2 const int MAXM = 400010; 3 const int INF = 0x3f3f3f3f; 4 struct Edge 5 { 6 int to, next, cap, flow; 7 }edge[MAXM]; 8 int tol; 9 int head[MAXN]; 10 int gap[MAXN], dep[MAXN], cur[MAXN]; 11 void ini

HDUOJ--4888--Redraw Beautiful Drawings【isap】网络流+判环

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4888 题意:一个矩阵,限定每行行和.列和,每个格子数字不超过k,问矩阵是否存在,如存在判断有单解还是多解. 思路:之前多校的题目,那时候还不会网络流,现在A掉了,矩阵的建图模型,判断网络流是否可行只要判断最大流是否等于总行和或总列和即可,判环是看的别人的解题报告,方法是使用dfs查找残余网络中是否有还存在容量的弧形成了环,如果有,说明可以通过这个环改变容量网络内部的增广路方式,而源汇的流量是不会变的,就

hdu4292 Food 最大流模板题

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4292 题意:水和饮料,建图跑最大流模板. 我用的是学长的模板,最然我还没有仔细理解,不过这都不重要直接贴就行了. 下面是AC代码,以后就当做最大流的模板来用了. 代码: #include<cstdio> #include<iostream> using namespace std; const int oo=1e9; const int mm=2e5+5; const int mn=1

2017 百度之星 资格赛 题解

百度之星 2017 资格赛 题解(原创)(2~5题 第一题方法是错的 第二题数据太水 并不会正解) 转载请注明出处http://www.cnblogs.com/nflslzt/p/7302377.html (题目在HDU上可以找到) 1001 度度熊保护村庄 题意 给你两个点集,A和B,问你在B中最少选取多少个点,使得B中剩余点的凸包能将A的凸包完全包住 数据范围 A,B中有500个点 多测 (n^3会超时) 想法 首先把两个点集的凸包求出来 贪心:B的凸包内部点全部可以去掉 可能(就)是伪证:

ZOJ--2314--Reactor Cooling【无源汇上下界可行流】

链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314 题意:某恐怖组织要建立一个核反应堆,他们需要设计一个冷却系统,n个点由m个管子连接,为使液体循环流动,每个节点的总流入量需要等于总流出量,现告诉你每根管子的最小流量及最大流量及它们连接的两点(有向),问是否存在可行流,如存在,输出每个管子的流量. 有上下界的网络流分为四种:无源汇的上下界可行流.有源汇的上下界可行流.有源汇的上下界最大流.有源汇的上下界最小流,这道

网络流之最大流问题

Reference: http://blog.csdn.net/rrerre/article/details/6751520 http://blog.csdn.net/y990041769/article/details/21026445 最大流Edmonds_Karp算法模板: 算法思想:step 1. 令所有弧的流量为0,从而构造一个流量为0的可行流f(称作零流).step 2. 若f中找不到可改进路则转step 5:否则找到任意一条可改进路P.step 3. 根据P求delta.step

HDU 1532Drainage Ditches(最大流模板题 ISAP)

Drainage Ditches Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11306    Accepted Submission(s): 5328 Problem Description Every time it rains on Farmer John's fields, a pond forms over Bessie'

HDU 3572 Task Schedule(ISAP)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3572 题意:m台机器,需要做n个任务.第i个任务,你需要使用机器Pi天,且这个任务要在[Si  ,  Ei]区间内完成才有效.对于一个任务,只能由一个机器来完成,一个机器同一时间只能做一个任务.当然,一个任务可以分成几段不连续的时间来完成.问,能否做完全部任务. 题意很清晰,也就是判断是否是满流. 对于网络流问题,模板大家都有,关键在于如何建图(详见资料) 思路:今天问了龙哥,对建图有了一定的了解,