//RQ的板子真的很好用
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn=200+5;
struct Edge
{
int from,to,cap,flow;
Edge(){}
Edge(int f,int t,int c,int flow):from(f),to(t),cap(c),flow(flow){}
};
struct Dinic
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];
int cur[maxn];
int d[maxn];
void init(int n,int s,int t)
{
this->n=n, this->s=s, this->t=t;
edges.clear();
for(int i=1;i<=n;i++) G[i].clear();
}
void AddEdge(int from,int to,int cap)
{
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from,0,0));
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BFS()
{
memset(vis,0,sizeof(vis));
queue<int> Q;
d[s]=0;
Q.push(s);
vis[s]=true;
while(!Q.empty())
{
int x=Q.front(); Q.pop();
for(int i=0;i<G[x].size();i++)
{
Edge& e=edges[G[x][i]];
if(!vis[e.to] && e.cap>e.flow)
{
vis[e.to]=true;
Q.push(e.to);
d[e.to]= 1+d[x];
}
}
}
return vis[t];
}
int DFS(int x,int a)
{
if(x==t || a==0) return a;
int flow=0,f;
for(int& i=cur[x]; i<G[x].size(); i++)
{
Edge& e=edges[G[x][i]];
if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow) ))>0 )
{
e.flow+=f;
edges[G[x][i]^1].flow -=f;
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}
int Maxflow()
{
int flow=0;
while(BFS())
{
memset(cur,0,sizeof(cur));
flow += DFS(s,INF);
}
return flow;
}
}DC;
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)==2)
{
DC.init(n,1,n);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
DC.AddEdge(u,v,w);
}
printf("%d\n",DC.Maxflow());
}
return 0;
}
风骨散人Chiam
认证博客专家
拖更专业户????
大学僧，考研狗，没上岸，ACM退役选手。名字的含义：希望可以通过努力，能力让家人拥有富足的生活而不是为了生计而到处奔波。“世人慌慌张张，不过是图碎银几两。偏偏这碎银几两，能解世间惆怅，可让父母安康，可护幼子成长 …”Chiam是 -am爱 China中国文章主要内容：Python,C++,C语言,JAVA,C#等语言的教程，ACM题解、模板、算法等，主要是数据结构，数学和图论设计模式，数据库，计算机网络，操作系统，计算机组成原理，Python爬虫、深度学习、机器学学习，计算机系408考研的所有专业课内容。目前还在更新中，博客园，微信公众号同名“风骨散人”，关注公众号可获软件大礼包
