227737329rrr @ 2023-06-01 18:44:53
//n个点,m条边,源点编号1,汇点编号n
#include<bits/stdc++.h>
using namespace std;
long long Source,Collect;//源点、汇点
long long N;//图的点数
long long**cap;//容量
long long**flow;//流量
long long*Ceng_ISAP;//Ceng_ISAP[i]: 访问i需要进过的最小的路径, 层次结构
long long*cur;//当前弧,用于弧优化
long long*gap;//gap优化,gap[i]表示i层的结点个数
//与Dinic算法不同的是,ISAP是从汇点往源点构建层次的
long long BFS_ISAP(){
//初始化层次数组
for(long long i=0;i<N;i++){
Ceng_ISAP[i]=N;
}
Ceng_ISAP[Collect]=0;
queue<long long> que;
que.push(Collect);//将汇点加入队列
while(!que.empty()){
long long temp=que.front();
que.pop();
gap[Ceng_ISAP[temp]]++;
//遍历temp的所有出边
for(long long i=0;i<N;i++){
//如果边的剩余容量大于0且终点未访问过
if(Ceng_ISAP[i]==N&&cap[i][temp]-flow[i][temp]>0){
Ceng_ISAP[i]=Ceng_ISAP[temp]+1;//更新终点的层次
que.push(i);
}
}
}
return Ceng_ISAP[Source]<N;
}
long long DFS_ISAP(long long now_p,long long limit)
{
//如果当前节点是汇点,返回当前DFS通路最大的流量limit
if(now_p==Collect) return limit;
long long cost=0;//流量limit已经消耗的消耗的流量cost,即增广量
//从当前弧开始遍历now_p的所有出边
for(long long i=cur[now_p];i<N;i++){
cur[now_p]=i;//更新当前弧
//如果边的容量大于0且终点的层次比当前节点小1
if(Ceng_ISAP[now_p]==Ceng_ISAP[i]+1&&cap[now_p][i]-flow[now_p][i]>0){
long long temp=DFS_ISAP(i,min(limit-cost,cap[now_p][i]-flow[now_p][i]));//递归寻找增广路并返回增广量
//如果增广成功
if(temp>0){
flow[now_p][i]+=temp;//更新正向边的流量
flow[i][now_p]-=temp;//更新反向边的流量
cost+=temp;//累加增广流量
if(limit==cost) return cost;//如果流量限制已经达到,退出循环
}
}
}
//if(cost==0){ //如果当前节点无法继续增广
gap[Ceng_ISAP[now_p]]--; //更新 gap 数组
if(gap[Ceng_ISAP[now_p]]==0){
Ceng_ISAP[Source]=N; //如果当前高度没有节点,则更新源点高度为 N
}
long long minn=N-1; //记录当前节点能够到达的最小高度
for(long long i=0;i<N;i++){ //遍历当前节点的所有出边
if(cap[now_p][i]-flow[now_p][i]>0) minn=min(minn,Ceng_ISAP[i]); // 更新最小高度
}
Ceng_ISAP[now_p]=minn+1; //更新当前节点的高度标签
gap[Ceng_ISAP[now_p]]++; //更新 gap 数组
cur[now_p]=0; // 重置当前弧
//}
return cost;//返回增广流量
}
long long ISAP()
{
long long ret=0;
Ceng_ISAP=new long long[N];
cur=new long long[N];
gap=new long long[N+1];
BFS_ISAP();
while(Ceng_ISAP[Source]<N){
for(long long i=0;i<N;i++){
cur[i]=0;
}
ret+=DFS_ISAP(Source,INT_MAX);
}
delete[]Ceng_ISAP;
delete[]cur;
delete[]gap;
return ret;
}
void CreatMapp();
void DeleteMemory();
int main ()
{
CreatMapp();
cout<<ISAP()<<endl;
DeleteMemory();
}
//根据参数初始化图和变量
void CreatMapp(){
cin>>N;
long long m;
cin>>m;
cin>>Source;Source--;
cin>>Collect;Collect--;
cap=new long long*[N];
flow=new long long*[N];
for(long long i=0;i<N;i++){
cap[i]=new long long[N];
flow[i]=new long long[N];
for(long long j=0;j<N;j++){
cap[i][j]=flow[i][j]=0;
}
}
for(long long i=0;i<m;i++){
long long u,v,c;
cin>>u>>v>>c;
cap[u-1][v-1]=+c;
}
// cout<<"N:"<<N<<" Source:"<<Source<<" Collect:"<<Collect<<endl;
// for(long long i=0;i<N;i++){
// for(long long j=0;j<N;j++){
// cout<<"("<<i<<","<<j<<"):"<<cap[i][j]<<" ";
// }
// cout<<endl;
// }
}
//清除动态分配的空间
void DeleteMemory(){
for(long long i=0;i<N;i++){
delete[]cap[i];
delete[]flow[i];
}
delete[]cap;
delete[]flow;
}
by toolazy @ 2023-10-12 22:27:35
同问
by kabout @ 2024-04-09 19:57:48
同问