题意:给一张网络,问从1->n的最大流
思路:Dinic
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf=1e9+9;
const int N=305,M=305;
int cnt;
int ver[M<<1],edge[M<<1],Next[M<<1],head[N<<1];
///ver[i]:第i条边的终点;edge[i],第i条边的权值
///Next[i]:和第i条边同起点的 其他边的 编号
/// head[x]:节点x最后一次作为起点的边
void add(int u,int v,int w){
ver[++cnt]=v;edge[cnt]=w;Next[cnt]=head[u];head[u]=cnt;
}
void init(){
memset(head,-1,sizeof head);
cnt=1;
}
int s,t;
int dis[N];
bool bfs(){
memset(dis,0,sizeof dis);
/// dis[s]必须为1 ?不能为0, 看if语句,会把dis判断错误
dis[s]=1;
queue<int> q;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i!=-1;i=Next[i]){
if(edge[i]>0 && !dis[ver[i]]){
dis[ver[i]]=dis[x]+1;
q.push(ver[i]);
if(ver[i]==t) return true;
}
}
}
return false;
}
int Dinic(int x,int flow){/// flow代表流到节点x的流量,作为初始S,流量为inf
if(x==t) return flow;
int res=0; /// 保存从当前节点已经流出的流量
for(int i=head[x];i!=-1;i=Next[i]){
// cout << x <<" -> " << ver[i] <<" wight=" << edge[i] << " dis = " << dis[x] << endl;
if(flow-res>0&& dis[ver[i]]==dis[x]+1 && edge[i]){
int k=Dinic(ver[i],min(flow-res,edge[i]));/// 求某条路一直走下去的流
if(!k) dis[ver[i]]=0;/// 若发现k==0,即这条路不能走,就标记dis[ver[i]]=0,从此再不走这条边(路过ver[i])
edge[i]-=k; ///正向边容量-k
edge[i^1]+=k;///反向边容量+k (反悔)
res+=k;
}
}
return res;
}
int main(void){
int m,n;
while(scanf("%d%d",&m,&n)==2){
init();
s=1,t=n;
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
ll maxflow=0;
int flow;
while(bfs()){
// cout <<" GO " << endl;
// cout << "dis[s]="<<dis[s] << endl;
while(flow=Dinic(s,inf)) /*cout <<"flow="<<flow<<endl,*/maxflow+=flow;
}
printf("%lld\n",maxflow);
}
return 0;
}