70partWA了三个救救孩子

美景、 @ 2019-06-14 21:09:13

#include<bits/stdc++.h>
#define maxn 10010
#define maxm 100010
#define inf 0x7fffffff
using namespace std;

inline int read(){
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') t=-1,ch=getchar();
    while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
    return x*t;
}

int s,t;
int cnt,head[2*maxm];
struct Edge{
    int to,next,w,depth;
}edge[2*maxm];
int n;int m;
int u,v,val;

inline void add(int u,int v,int val){
    edge[++cnt].to=v;
    edge[cnt].w=val;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline int dfs(int u,int dis){
    if(u==t) return dis;
    for(register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if((edge[v].depth==edge[u].depth+1)&&edge[i].w!=0){
            int minn=dfs(v,min(edge[i].w,dis));
            if(minn>0){
                edge[i].w-=minn;
                edge[i^1].w+=minn;
                return minn;
            }
        }
    }
    return 0;
}

int bfs(){
    queue<int> q;
    while(!q.empty()) q.pop();
    for(register int i=1;i<=n;++i) edge[i].depth=0;
    edge[s].depth=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(register int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(edge[i].w>0&&edge[v].depth==0){
                edge[v].depth=edge[u].depth+1;
                q.push(v);
            }
        }
    }
    if(edge[t].depth>0) return 1;
    return 0;
}

int main()
{
    n=read(); m=read(); s=read(); t=read();
    for(register int i=1;i<=m;++i){
        u=read(); v=read(); val=read();
        add(u,v,val); add(v,u,0);
    }
    int ans=0;
    while(bfs()){
        while(int sum=dfs(s,inf)) ans+=sum;
    }
    printf("%d",ans);
    return 0;
}

by Smile_Cindy @ 2019-06-14 21:09:48

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N=1000005;
const int INF=0x3f3f3f3f;
struct edge
{
    int to,cap,rev;
    edge(){}
    edge(int _to,int _cap,int _rev)
    {
        to=_to;
        cap=_cap;
        rev=_rev;
    }
};
vector<edge> G[MAX_N];
int n,m,s,t;
int level[MAX_N],iter[MAX_N];
void add_edge(int from,int to,int cap)
{
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int> q;
    level[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0;i<(int)G[v].size();i++)
        {
            edge &e=G[v][i];
            if(e.cap>0 && level[e.to]<0)
            {
                level[e.to]=level[v]+1;
                q.push(e.to);
            }  
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int i=iter[v];i<(int)G[v].size();i++)
    {
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to])
        {
            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 -1;
}
int max_flow(int s,int t)
{
    int flow=0;
    while(true)
    {
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f=dfs(s,t,INF);
        while(f>0)
        {
            flow+=f;
            f=dfs(s,t,INF);
        }
    }
}
signed main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    cout<<max_flow(s,t)<<endl;
    return 0;
} 

by 美景、 @ 2019-06-14 21:13:26

@Alpha qaq表示还是看不出我的有什么锅

by 美景、 @ 2019-06-14 21:15:49

emm我好想。。。知道了（此贴结束）

by BinDir0 @ 2019-06-14 21:24:35

@美景、 捕捉dalao！！！

by 美景、 @ 2019-06-14 21:57:24

@恨妹不成穹 （逃

by charliegong @ 2019-06-14 22:01:41

@恨妹不成穹 @美景、 捕捉dalao！！！

by BinDir0 @ 2019-06-15 11:50:08

@charliegong 又一位奆佬qaq

by 森岛帆高 @ 2019-06-15 17:13:59

cnt=-1