谁来救救初学OI的萌新啊。。

P3376 【模板】网络最大流

Sai0511 @ 2018-10-04 18:18:59

RT,实在找不出问题了。。

#include<bits/stdc++.h>  
#define gc getchar    
const int MAXN=10010;
const int MAXM=100010;
const int INF=0x7f7f7f7f;
using namespace std;   
int n,m,i,j,x,y,z,cnt=1,Beg,End,ans;
struct Pre{int side,pre;};
Pre pre[MAXM];
int head[MAXM];
struct Edge{int to,val,nxt;};  
Edge g[MAXM];   
bool vis[MAXN];
void addEdge(int u,int v,int val){
    g[++cnt].to=v;
    g[cnt].val=val;
    g[cnt].nxt=head[u];
    head[u]=cnt;  
}    
struct io{
    int read(){
        int x=0;char c;
        for(c=gc();!isdigit(c);c=gc()) ;
        for(;isdigit(c);c=gc()) x=x*10+c-48;
        return x;
    }
}Fio;
#define read Fio.read  
queue<int>q;   
bool bfs(){
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
    vis[Beg]=1;q.push(Beg);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=g[i].nxt){
            int to=g[i].to;
            if(vis[to]||g[i].val==0) continue;   
            //cout << to << endl;
            vis[to]=1;
            pre[to].side=i;
            pre[to].pre=u;      
            if(to==End) return 1;
            q.push(to);
            //while(!q.empty()) q.pop();
        }
    }
    //cout << 1 << endl;
    return 0;
}   
int EK(){
    int ans=0;
    while(bfs()){
        int i,j;     
        int Min=INF;
        for(i=End;i!=Beg;i=pre[i].pre)
         Min=min(Min,g[pre[i].side].val);    
        for(i=End;i!=Beg;i=pre[i].pre){
            g[pre[i].side].val-=Min;
            g[pre[i].side^1].val+=Min;
        }
        ans+=Min;         
    }
    return ans;
}
int main(){
    n=read();m=read();Beg=read();End=read();   
    for(i=1;i<=m;i++){
        int u=read(); int v=read(); int l=read();
        addEdge(u,v,l);
        addEdge(v,u,0);
    }
    ans=EK();
    printf("%d\n",ans);
}

by Sai0511 @ 2018-10-04 18:19:51

不要在意EK的复杂度,反正能过就行了


by caidzh @ 2018-10-04 18:22:04

萌新网络流,可啪。。。

又是初学OI的都是怪物系列


by zzqDeco @ 2018-10-04 18:24:28

@Sai_0511 e


by zzqDeco @ 2018-10-04 18:25:42

@Sai_0511 好强


by Sai0511 @ 2018-10-04 18:29:06

@zzqzzqzzq Orz话说我错在哪了QAQ


by zzqDeco @ 2018-10-04 18:32:00

@Sai_0511 不知道,我还没学网络流(自己只打了一道题)


by Smile_Cindy @ 2018-10-04 18:32:55

@Sai_0511

%%%


by SofanHe @ 2018-10-04 18:36:36

@Sai_0511 果然人如其像,像不虚传(头像)


by suyiheng @ 2018-10-04 18:43:41

// luogu-judger-enable-o2

include<iostream>

include<vector>

include<cstdio>

include<queue>

using namespace std; int n,m,ans,f[10001],r[10001][2],st,en,x,y,z; struct data{ int a,b,c; data(int a,int b,int c){ this->a=a; this->b=b; this->c=c; } }; vector<data> v; vector<int> u[10001]; void bfs(){ queue<int> q; int k=0; while(1){ for(int i=1;i<=n;i++)f[i]=0; f[st]=1000000000; q.push(st); while(!q.empty()){ x=q.front(); q.pop(); for(int i=0;i<u[x].size();i++){ y=u[x][i]; data d=v[y]; if(f[d.b]==0&&d.c){ f[d.b]=min(f[x],d.c); r[d.b][0]=x; r[d.b][1]=y; q.push(d.b); } } } if(f[en]==0)break; for(int i=en;i!=st;i=r[i][0]){ v[r[i][1]].c-=f[en]; v[r[i][1]^1].c+=f[en]; } ans+=f[en]; } return; } int main(){ scanf("%d %d %d %d",&n,&m,&st,&en); for(int i=1;i<=m;i++){ scanf("%d %d %d",&x,&y,&z); v.push_back(data(x,y,z)); u[x].push_back(v.size()-1); v.push_back(data(y,x,0)); u[y].push_back(v.size()-1); } bfs(); printf("%d",ans); }


by suyiheng @ 2018-10-04 18:44:28

发个我A了的代码


| 下一页