求助 dinic 几乎照着题解打，题解A了我T了。。

潜翎 @ 2019-01-29 17:59:01

#include <queue>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define INF 0x3f3f3f3f
#define N 10010
#define M 100010
using namespace std;
int n,m,s,t,tot=1;//边从2开始存 
int head[N],vec[M],next[M],val[M];
int q[M],dep[M];
void add(int x,int y,int v)
{
    vec[++tot]=y;
    val[tot]=v;
    next[tot]=head[x];
    head[x]=tot;
}
int bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int>q;
    while(!q.empty()) q.pop();
    dep[s]=1;//源点深度
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=next[i])
        {
            int v=vec[i];
            if(val[i]>0&&dep[v]==0)//还能走并且没有被访问
            {
                dep[v]=dep[u]+1;
                q.push(v);
            } 
        }
    }
    if(dep[t]) return 1;//还有增广路 
    else return 0;//么得咯 
}
int dfs(int u,int dis)
{
    if(u==t) return dis;//当前可行流大小 
    for(int i=head[u];i;i=next[i])
    {
        int v=vec[i];
        if((dep[v]==dep[u]+1)&&(val[i]))
        {
            int di=dfs(v,min(val[i],dis));
            if(di>0)
            {
                val[i]-=di;
                val[i^1]+=di;
                return di;
            } 
        }
    }
    return 0;
} 
int dinic()
{
    int ans=0;
    while(bfs())
        while(int di=dfs(s,INF))
            ans+=di;
    return ans;
}
int main()
{
    int i,x,y,z;
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    printf("%d",dinic());
    return 0;
}

by YZhe @ 2019-01-29 18:01:00

要不你参考一下我的吧，没吸氧200多ms

#include<bits/stdc++.h>
using namespace std;
#define oo 0x3f3f3f3f
#define N 100005
#define M 10005
#define ri register int 
typedef long long ll;
int timer = 0,n,m,s,t,tot = -1,head[M],dis[M],vis[M]; 
struct Edge{
    int to,next,w;
}e[N<<1];

template<class T>
inline void read(T &res){
    static char ch;T flag = 1;
    while( ( ch = getchar() ) < '0' || ch > '9' )
      if( ch == '-' ) flag = -1;
    res = ch - 48;
    while( ( ch = getchar() ) >= '0' && ch <= '9' )
      res = res * 10 + ch - 48;
    res *= flag;
}

inline void add( int from , int to , int w ){
    e[ ++tot ].to = to;
    e[ tot ].w = w;
    e[ tot ].next = head[ from ];
    head[ from ] = tot;
}

int dfs( int x , int lim ){
    if( x == t ) return lim;
    int ans = 0;
    for( ri i = head[ x ] ; i != -1 ; i = e[ i ].next )
      if( e[ i ].w && dis[ e[ i ].to ] == dis[ x ] + 1 ){
          int y = dfs( e[ i ].to , min( e[ i ].w , lim ) );
          if( y ){
              e[ i ].w -= y;e[ i^1 ].w += y;
              ans += y;lim -= y;
              if( !lim ) return ans;
          }
      }
    return ans;
}

inline bool bfs(){
    timer++;
    queue<int> q;
    dis[ s ] = 0;vis[ s ] = timer;
    q.push( s );
    while( !q.empty() ){
        int x = q.front();q.pop();
        for( ri i = head[ x ] ; i != -1 ; i = e[ i ].next ){
            int v = e[ i ].to;
            if( e[ i ].w == 0 ) continue;
            if( vis[ v ] != timer ){
                vis[ v ] = timer;
                dis[ v ] = dis[ x ] + 1;
                q.push( v ); 
            }
        }
    }
    return vis[ t ] == timer;
}//判断是否可以增广 

int dinic(){
    int ans = 0;
    while( bfs() ) ans += dfs( s , 0x3f3f3f3f );
    return ans;
}

int main()
{
    read( n );read( m );read( s );read( t );
    for( ri i = 1 ; i <= n ; i++ ) head[ i ] = -1;//初始化
    for( ri i = 1 ; i <= m ; i++ ){
        int x,y,z;read( x );read( y );read( z );
        add( x , y , z );add( y , x , 0 );//建边的同时要建一条虚拟边 
    }
    cout<<dinic();
//    while( getchar() );
    return 0;
}

by LJC00118 @ 2019-01-29 18:17:09

边数组开小了？

by 潜翎 @ 2019-01-29 18:20:47

@LJC00118 是的，发现了，谢谢您

by 潜翎 @ 2019-01-29 18:21:35

@Tryer 非常有帮助，谢谢您

参考dalao程序使我跑的比题解快