网路流裸题，用来测试模板吧。
1.EK－1
// Created by Chenhongwei in 2015.
// Copyright (c) 2015 Chenhongwei. All rights reserved.
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#include"climits"
#include"queue"
#include"cmath"
#include"map"
#include"set"
#include"stack"
#include"vector"
#include"sstream"
#include"algorithm"
using namespace std;
typedef long long ll;
const int inf=1e8;
const int maxn=1100;
struct node
{
int to,cap,rev;
};
int n,m;
int used[maxn];
vector g[maxn];
int dfs(int s,int t,int f)
{
if(s==t)
return f;
used[s]=1;
for(int i=0;i0)
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
while(1)
{
memset(used,0,sizeof used);
int f=dfs(s,t,inf);
if(f==0)
return flow;
flow+=f;
}
}
int main()
{
//ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
for(int z=1;z<=T;z++)
{
scanf("%d%d",&n,&m);
memset(g,0,sizeof g);
for(int i=0;i
EK－2
// Created by Chenhongwei in 2015.
// Copyright (c) 2015 Chenhongwei. All rights reserved.
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "climits"
#include "queue"
#include "cmath"
#include "map"
#include "set"
#include "stack"
#include "vector"
#include "sstream"
#include "algorithm"
using namespace std;
typedef long long ll;
const int inf=1e8;
const int maxn=1100;
struct node
{
int from,to,cap,rev;
node(int from,int to,int cap):from(from),to(to),cap(cap) {}
};
vector edge;
vectorg[maxn];
int pre[maxn],a[maxn];
int bfs(int s,int t)
{
queueq;
q.push(s);
memset(a,0,sizeof a);
a[s]=inf;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i0)
{
pre[e.to]=g[u][i];
a[e.to]=min(a[u],e.cap);
q.push(e.to);
}
}
if(a[t])break;
}
if(!a[t]) return 0;
for(int u=t;u!=s;u=edge[pre[u]].from)
{
edge[pre[u]].cap-=a[t];
edge[pre[u]^1].cap+=a[t];
}
return a[t];
}
int max_flow(int s,int t)
{
int flow=0;
while(1)
{
memset(pre,0,sizeof pre);
int f=bfs(s,t);
if(f==0)
return flow;
flow+=f;
}
}
int main()
{
//ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m,T;
scanf("%d",&T);
for(int z=1;z<=T;z++)
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
g[i].clear();
edge.clear();
for(int i=0;i
// Created by Chenhongwei in 2015.
// Copyright (c) 2015 Chenhongwei. All rights reserved.
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#include"climits"
#include"queue"
#include"cmath"
#include"map"
#include"set"
#include"stack"
#include"vector"
#include"sstream"
#include"algorithm"
using namespace std;
typedef long long ll;
const int inf=1e8;
const int maxn=20;
int n;
int d[maxn];
int g[maxn][maxn];
bool tag;
int dfs(int cur,int aug,int s,int t)
{
if(cur==t)
{
tag=true;
return aug;
}
for(int i=1;i<=n;i++)
{
if(g[cur][i]>0&&d[cur]==d[i]+1)
{
int f=dfs(i,min(aug,g[cur][i]),s,t);
if(d[s]>=n)
return 0;
if(tag)
{
g[cur][i]-=f;
g[i][cur]+=f;
return f;
}
}
}
d[cur]++;
return 0;
}
int sap(int s,int t)
{
int flow=0;
memset(d,0,sizeof d);
while(d[s]
DINIC
// Created by Chenhongwei in 2015.
// Copyright (c) 2015 Chenhongwei. All rights reserved.
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#include"climits"
#include"queue"
#include"cmath"
#include"map"
#include"set"
#include"stack"
#include"vector"
#include"sstream"
#include"algorithm"
using namespace std;
typedef long long ll;
const int inf=1e8;
const int maxn=1100;
struct node
{
int to,cap,rev;
};
int n,m;
int cur[maxn],d[maxn];
vector g[maxn];
void bfs(int s)
{
memset(d,-1,sizeof d);
d[s]=0;
queueq;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i0&&d[e.to]<0)
{
d[e.to]=d[u]+1;
q.push(e.to);
}
}
}
}
int dfs(int s,int t,int f)
{
if(s==t)
return f;
for(int i=cur[s];i0&&d[e.to]>d[s])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int dinic(int s,int t)
{
int flow=0;
while(1)
{
bfs(s);
if(d[t]<0)
return flow;
memset(cur,0,sizeof cur);
int f;
while((f=dfs(s,t,inf))>0)
flow+=f;
}
}
int main()
{
//ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
for(int z=1;z<=T;z++)
{
scanf("%d%d",&n,&m);
memset(g,0,sizeof g);
for(int i=0;i
ISAP
// Created by Chenhongwei in 2015.
// Copyright (c) 2015 Chenhongwei. All rights reserved.
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "climits"
#include "queue"
#include "cmath"
#include "map"
#include "set"
#include "stack"
#include "vector"
#include "sstream"
#include "algorithm"
using namespace std;
typedef long long ll;
const int inf=1e8;
const int maxn=1100;
struct node
{
int from,to,cap;
node(int from,int to,int cap):from(from),to(to),cap(cap) {}
};
vector edge;
vectorg[maxn];
int p[maxn],cur[maxn];
int num[maxn],d[maxn];
int n;
void addedge(int u,int v,int w)
{
edge.push_back(node(u,v,w));
edge.push_back(node(v,u,0));
int t=edge.size();
g[u].push_back(t-2);
g[v].push_back(t-1);
}
void BFS(int s,int t)
{
memset(d,-1,sizeof d);
queueq;
q.push(t);
d[t]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i0)
{
d[e.from]=d[u]+1;
q.push(e.from);
}
}
}
}
int augment(int s,int t)
{
int x=t,ans=inf;
while(x!=s)
{
node& e=edge[p[x]];
ans=min(ans,e.cap);
x=edge[p[x]].from;
}
x=t;
while(x!=s)
{
edge[p[x]].cap-=ans;
edge[p[x]^1].cap+=ans;
x=edge[p[x]].from;
}
return ans;
}
int ISAP(int s,int t)
{
int flow=0;
BFS(s,t);
memset(num,0,sizeof num);
for(int i=0;i0&&d[x]==d[e.to]+1)
{
ok=1;
p[e.to]=g[x][i];
cur[x]=i;
x=e.to;
break;
}
}
if(!ok)
{
int m=n-1;
for(int i=0;i0)
m=min(m,d[e.to]);
}
if(--num[d[x]]==0)
break;
d[x]=m+1;
num[d[x]]++;
cur[x]=0;
if(x!=s)
x=edge[p[x]].from;
}
}
return flow;
}
int main()
{
//ios::sync_with_stdio(false);
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T,m,u,v,w;
scanf("%d",&T);
for(int z=1;z<=T;z++)
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
g[i].clear();
edge.clear();
for(int i=0;i