HDU1532
Drainage Ditches
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19000 Accepted Submission(s): 9058
Problem Description
Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Input
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.
Output
For each case, output a single integer, the maximum rate at which water may emptied from the pond.
Sample Input
5 41 2 401 4 202 4 202 3 303 4 10
Sample Output
50
【解析】：
输入m个点，和n条边，求从1到m的最大流。（我的代码中，n和m颠倒了）
直接上dinic或者sap的模板跑一遍即可
【代码dinic】：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=220;
struct node{
ll t,cap,flow,next; //cap容量，flow流量
}e[N*N];
int head[N],vis[N],cnt; //vis优化dfs中的head
void add(int u,int v,int cap) //u->v容量为cap
{
e[cnt]=node{v,cap,0,head[u]};
head[u]=cnt++;
e[cnt]=node{u,0,0,head[v]}; //容量为0的反向边
head[v]=cnt++;
}
int d[N]; //bfs深度
bool bfs(int s,int t) //O(n+m)
{
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].t;
if(d[v]==0&&e[i].cap-e[i].flow>0)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
return d[t]>0; //存在增广路
}
ll dfs(int s,int t,ll minedge)
{
if(s==t)return minedge;
ll flow=0; //从当前s点流出的流量
for(int &i=vis[s];~i;i=e[i].next)
{
int v=e[i].t;
if(d[v]==d[s]+1&&e[i].cap-e[i].flow>0) //层次关系&&有剩余流量
{
ll temp=dfs(v,t,min(minedge-flow,e[i].cap-e[i].flow));
e[i].flow+=temp; //流量增加
e[i^1].flow-=temp; //反向边流量减少
flow+=temp; //flow已分配的流量
if(flow==minedge)return flow; //已达到祖先的最大流，无法再大，剪枝
}
}
if(flow==0)d[s]=0; //此点已无流，标记掉
return flow;
}
ll dinic(int s,int t) //一定要建立反向边cap=0
{
ll maxflow=0;
while(bfs(s,t)) //有增广路
{
memcpy(vis,head,sizeof(head));
maxflow+=dfs(s,t,INF);
}
return maxflow;
}
int main()
{
int n,m,s,t,l;
while(cin>>m>>n) //m边，n点
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&s,&t,&l);
add(s,t,l);
}
int ans=dinic(1,n);
cout<<ans<<endl;
}
return 0;
}
【代码sap】：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAX=1e3;
struct node{
int s,t,cap,next;
}edge[6*MAX];
int head[MAX],cnt;
void add(int s,int t,int cap)
{
edge[cnt]={s,t,cap,head[s]};
head[s]=cnt++;
edge[cnt]={t,s,0,head[t]}; //反向边便于反悔
head[t]=cnt++;
}
int pre[MAX];//前驱边
int dep[MAX];//节点的标号
int gap[MAX];//gap[i]表示编号i出现的次数
int sap(int s,int t)
{
memset(pre,-1,sizeof(pre));
memset(dep,0,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=t; //所有标号预设为0,故有t个点
int u=s,v,i,flow=INF,ansflow=0;
while(1) //起点u为s
{
int mindep=t;
for(i=head[u];i!=-1;i=edge[i].next)//找一个允许弧
{
node &e=edge[i];
if(e.cap&&mindep>dep[e.t])
mindep=dep[e.t];//顺便记下与u相连的最小编号
if(e.cap&&dep[u]==dep[e.t]+1){
flow=min(flow,e.cap);
break;
}
}
if(i!=-1)//找到了允许弧edge[i]
{
v=edge[i].t;
pre[v]=i;//记下前驱边
u=v;//前进
if(u==t)//到达汇点
{
ansflow+=flow;
while(u!=s)
{
int e=pre[u];
edge[e].cap-=flow;
edge[e^1].cap+=flow;
u=edge[e].s;
}
flow=INF;
}
}
else//找不到允许弧
{
gap[dep[u]]--;
if(gap[dep[u]]==0)return ansflow;
dep[u]=mindep+1;
gap[dep[u]]++;
if(u!=s)
u=edge[pre[u]].s;//往源点退
}
}
}
int main()
{
int n,m,s,t,l;
while(cin>>m>>n) //m边，n点
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&s,&t,&l);
add(s,t,l);
}
int ans=sap(1,n);
cout<<ans<<endl;
}
return 0;
}