//非当前弧优化版
#include <iostream>
#include <cstdio>
#include <math.h>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
int tab[250][250];//邻接矩阵
int dis[250];//距源点距离,分层图
int N,M;//N:点数;M,边数
queue<int> Q;
int BFS()
{
memset(dis,0xff,sizeof(dis));//以-1填充
dis[1]=0;
Q.push(1);
while (Q.size())
{
int head=Q.front();
Q.pop();
for (int i=1; i<=N; i++)
if (dis[i]<0 && tab[head][i]>0)
{
dis[i]=dis[head]+1;
Q.push(i);
}
}
if (dis[N]>0) return 1;
else return 0;//汇点的DIS小于零,表明BFS不到汇点
}
//dfs代表一次增广,函数返回本次增广的流量,返回0表示无法增广
int dfs(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
{
int a=0;
if (x==N)
return low;//是汇点
for (int i=1; i<=N; i++)
if (tab[x][i] >0 //联通
&& dis[i]==dis[x]+1 //是分层图的下一层
&&(a=dfs(i,min(low,tab[x][i]))))//能到汇点(a != 0)
{
tab[x][i]-=a;
tab[i][x]+=a;
return a;
}
return 0;
}
int dinic()
{
int ans=0,tans;
while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束
{
while(tans=dfs(1,0x7fffffff))ans+=tans;//一次BFS要不停地找增广路,直到找不到为止
}
return ans;
}
int main()
{
int i,j,f,t,flow,tans;
while (scanf("%d%d",&M,&N)!=EOF)
{
memset(tab,0,sizeof(tab));
for (i=1; i<=M; i++)
{
scanf("%d%d%d",&f,&t,&flow);
tab[f][t]+=flow;
}
printf("%d\n",dinic());
}
}
//当前弧优化版
#include <iostream>
#include <cstdio>
#include <math.h>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
int tab[250][250];//邻接矩阵
int dis[250];//距源点距离,分层图
int cur[280]; //当前弧优化
int N,M;//N:点数;M,边数
queue<int> Q;
int BFS()
{
memset(dis,0xff,sizeof(dis));//以-1填充
dis[1]=0;
Q.push(1);
while (Q.size())
{
int head=Q.front();
Q.pop();
for (int i=1; i<=N; i++)
if (dis[i]<0 && tab[head][i]>0)
{
dis[i]=dis[head]+1;
Q.push(i);
}
}
if (dis[N]>0) return 1;
else return 0;//汇点的DIS小于零,表明BFS不到汇点
}
//dfs代表一次增广,函数返回本次增广的流量,返回0表示无法增广
int dfs(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
{
int a=0;
if (x==N)
return low;//是汇点
for (int &i=cur[x]; i<=N; i++)
if (tab[x][i] >0 //联通
&& dis[i]==dis[x]+1 //是分层图的下一层
&&(a=dfs(i,min(low,tab[x][i]))))//能到汇点(a != 0)
{
tab[x][i]-=a;
tab[i][x]+=a;
return a;
}
return 0;
}
int dinic()
{
int ans=0,tans;
while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束
{
for(int i=1;i<=N;i++)
cur[i]=1;
while(tans=dfs(1,0x7fffffff))ans+=tans;//一次BFS要不停地找增广路,直到找不到为止
}
return ans;
}
int main()
{
int i,j,f,t,flow,tans;
while (scanf("%d%d",&M,&N)!=EOF)
{
memset(tab,0,sizeof(tab));
for (i=1; i<=M; i++)
{
scanf("%d%d%d",&f,&t,&flow);
tab[f][t]+=flow;
}
printf("%d\n",dinic());
}
}
风骨散人Chiam
认证博客专家
拖更专业户????
大学僧，考研狗，没上岸，ACM退役选手。名字的含义：希望可以通过努力，能力让家人拥有富足的生活而不是为了生计而到处奔波。“世人慌慌张张，不过是图碎银几两。偏偏这碎银几两，能解世间惆怅，可让父母安康，可护幼子成长 …”Chiam是 -am爱 China中国文章主要内容：Python,C++,C语言,JAVA,C#等语言的教程，ACM题解、模板、算法等，主要是数据结构，数学和图论设计模式，数据库，计算机网络，操作系统，计算机组成原理，Python爬虫、深度学习、机器学学习，计算机系408考研的所有专业课内容。目前还在更新中，博客园，微信公众号同名“风骨散人”，关注公众号可获软件大礼包
