题意：裸的最大流，什么是最大流，参考别的博客
运用复杂度最高的EK算法 O（M*N),模板来自紫书
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#define INF 0x3f3f3f3f
#define oo 0x13131313
const int maxn=200+5;
using namespace std;
struct Edge {
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct EdmondsKarp{
int n,m;
vector<Edge> edges; //边集数组，边数*2
vector<int> G[maxn]; //邻接表
int a[maxn]; //起点到i的可改进量
int p[maxn]; //最短路树上p的弧编号
void init(int n){
for(int i = 0;i < n; i++) G[i].clear();
edges.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);
} int Maxflow(int s,int t)
{
int flow=0;
for(;;){
memset(a,0,sizeof(a));
queue<int> Q;
// while(!Q.empty()) Q.pop();
Q.push(s);
a[s]=INF;
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(!a[e.to]&&(e.cap>e.flow)) {
p[e.to]=G[x][i];
a[e.to]=min(a[x],e.cap-e.flow);
Q.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u=t;u!=s;u=edges[p[u]].from){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t]; }
flow+=a[t];
}
return flow;
}
};
完整代码：
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#define INF 0x3f3f3f3f
#define oo 0x13131313
const int maxn=200+5;
using namespace std;
struct Edge {
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct EdmondsKarp{
int n,m;
vector<Edge> edges; //边集数组，边数*2
vector<int> G[maxn]; //邻接表
int a[maxn]; //起点到i的可改进量
int p[maxn]; //最短路树上p的弧编号
void init(int n){
for(int i = 0;i < n; i++) G[i].clear();
edges.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);
} int Maxflow(int s,int t)
{
int flow=0;
for(;;){
memset(a,0,sizeof(a));
queue<int> Q;
// while(!Q.empty()) Q.pop();
Q.push(s);
a[s]=INF;
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(!a[e.to]&&(e.cap>e.flow)) {
p[e.to]=G[x][i];
a[e.to]=min(a[x],e.cap-e.flow);
Q.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u=t;u!=s;u=edges[p[u]].from){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t]; }
flow+=a[t];
}
return flow;
}
};
EdmondsKarp A;
int N;
void File()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
void input()
{
int a,b,c;
for(int i=1;i<=N;i++)
{
scanf("%d%d%d",&a,&b,&c);
A.AddEdge(a,b,c);
}
}
void solve()
{
int ans=0;
ans=A.Maxflow(1,A.n);
printf("%d\n",ans);
}
int main()
{
// File();
A.init(maxn);
while(scanf("%d%d",&N,&A.n)!=EOF)
{
input();
solve();
A.init(maxn); //注意用maxn 去初始化！
}
return 0;
}