请求加强数据+1

香风智乃 @ 2018-05-17 20:14:03

    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&q1,&q2,&q3);
        ed.push_back((edge){q1,q2,q3,0});
        g[q1].push_back(++u);
        ed.push_back((edge){q1,q2,0,0}); //反向边起点终点存反了
        g[q2].push_back(++u);
    }

by Flaranis @ 2018-05-17 21:40:46

事实上不建反向边都能过

by Explorer_CYC @ 2018-05-20 16:11:29

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define REG register
const int maxn=2e6+5;
const int inf=0x3f3f3fll;
#define min(a,b) a<b?a:b
typedef long long ll;
struct Input{
    #define SIZE 20000
    char BUF[SIZE],*S,*T;
    Input():S(BUF),T(BUF){}
    inline char Getchar(){return((S==T)&&(T=(S=BUF)+fread(BUF,1,SIZE,stdin),S==T)?EOF:*S++);}
    inline Input&operator>>(char&c){return(c=Getchar(),*this);}
    inline Input&operator>>(int&s){
        s=0;REG char c;
        while(c=Getchar(),c<48||c>57);
        while(s=s*10+c-48,c=Getchar(),c>47&&c<58);
        return*this;
    }inline Input&operator>>(ll&s){
        s=0;REG char c;
        while(c=Getchar(),c<48||c>57);
        while(s=(ll)s*10+c-48,c=Getchar(),c>47&&c<58);
        return*this;
    }
    #undef SIZE
}input;
struct Output{
    #define SIZE 20000
    char BUF[SIZE],*S,*Limit;
    Output():S(BUF),Limit(BUF+SIZE){}
    ~Output(){fwrite(BUF,1,S-BUF,stdout);}
    inline void Flush(){fwrite(BUF,1,S-BUF,stdout);S=BUF;}
    inline void Putchar(const char&c){if(S==Limit)Flush();*S++=c;}
    inline Output&operator<<(const char&c){return(Putchar(c),*this);}
    template<class T>inline Output&operator<<(T s){
        static char Stack[20];static int Top;
        Top=0;do Stack[++Top]=s%10+48;while(s/=10);
        while(Top)Putchar(Stack[Top--]);
        return*this;
    }
}output;
int head[maxn],p=-1;
int cur[maxn],G[maxn],depth[maxn];
int S,T,n,m,u,v,w;
struct Edge{
    int v,nxt,w;
}s[maxn<<2];
inline void add(REG int u,REG int v,REG int w)
{
    s[++p]=(Edge){v,head[u],w};
    head[u]=p;
    return;
}
inline void Add_Edge(REG int u,REG int v,REG int w)
{
    add(u,v,w);
    add(v,u,0);
    return;
}
inline void bfs()
{
    queue<int> Q;
    while(!Q.empty()) Q.pop();
    memset(G,0,sizeof(G));
    memset(depth,0,sizeof(depth));
    depth[S]=1;
    Q.push(S);
    do
    {
        int x=Q.front();
        Q.pop();
        for(REG int i=head[x];i;i=s[i].nxt)
        {
            int to=s[i].v;
            if(s[i].w>0&&!depth[to])
            {
                depth[to]=depth[x]+1;
                Q.push(to);
            }
        }
    }while(!Q.empty());
    return;
}
inline int dfs(REG int u,REG int val)
{
    if(u==T) return val;
    int ans=0;
    for(REG int&i=cur[u];i;i=s[i].nxt)
    {
        int to=s[i].v;
        if(depth[to]==depth[u]+1&&s[i].w>0)
        {
            int ok=dfs(to,min(val,s[i].w));
            ans+=ok;
            val-=ok;
            s[i^1].w+=ok;
        }//
        if(!val) return ans;
    }
    if(!(--G[depth[u]])) depth[S]=n+1;//
    ++G[++depth[u]];//
    cur[u]=head[u];//
    return ans;
}
inline int ISAP()
{
    bfs();

    int flow=dfs(S,inf);
    while(depth[S]<=n) flow+=dfs(S,inf);
    return flow;
}
int main()
{
    input>>n>>m>>S>>T;
    for(REG int i=1;i<=m;i++)
    {
        input>>u>>v>>w;
        Add_Edge(u,v,w);
    }
    output<<ISAP();
    return 0;
}