求调16分
查看原帖
求调16分
1037011
CandyCai楼主2025/7/3 16:28
#include<bits/stdc++.h>
#define N 100005
#define INF (1<<30)
using namespace std;
int head[N],deep[N],ans;
int n,m,ed,st,p,c;
int cnt=1;
int cur[N];
struct node{
    int to,w,fr;
    int nt;
}edge[N];
void add(int x,int y,int z){
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nt=head[x];
    edge[cnt].w=z;
    head[x]=cnt;
}
int bfs(int s,int t){
    memset(deep,0,sizeof(deep));
    memcpy(cur,head,sizeof(head));
    queue<int> q;
    q.push(s);
    deep[s]=1;
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        for(int i=head[tmp];i!=-1;i=edge[i].nt){
            int v=edge[i].to;
        	if(deep[v]||edge[i].w<=0){
        		continue;
			}
            deep[v]=deep[tmp]+1;
            q.push(v);
            if(v==t){
            	return 1;
			}
        }
    }
    if(deep[t]){
		return 1;
	}else{
		return 0;
	}
}
int dfs(int u,int ed,int flow){
    if(u==ed)return flow;
    int ans=0;
    for(int i=cur[u];i!=-1&&ans<flow;i=edge[i].nt){
        int v=edge[i].to;
        cur[u]=i;
        if(deep[v]!=deep[u]+1){
        	continue;
		}
        if(!edge[i].w){
        	continue;
		}
        int x=dfs(v,ed,min(edge[i].w,flow-ans));
        edge[i].w-=x;
        edge[i^1].w+=x;
        ans+=x;
    }
    return ans;
}
int dinic(int s,int t){
    int sum=0;
    while(bfs(s,t)){
        sum+=dfs(s,t,INF);
	}
    return sum;
}
int main(){
	memset(head,-1,sizeof(head));
	memset(edge,-1,sizeof(edge));
	cin>>n>>m>>st>>ed;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    cout<<dinic(st,ed);
	return 0;
}
2025/7/3 16:28
加载中...