Help! 90 Points with one WrongAnswer.What's the matter?

P3376 【模板】网络最大流

Huami360 @ 2018-05-10 22:27:51

Here is the code.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;++i)
#define dop(i,m,n) for(int i=m;i>=n;--i)
#define lowbit(x) (x&(-x))
#define ll long long
#define INF 2147483647
#define re register
using namespace std;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
//Qihoo360's own mode
//Luogu P3376 MaxFlow : 10/5/2018
const int maxn=10010;
const int maxm=100010;
map < int , int > Position [ maxn ] ;
struct Edge {
    int to , next , cap , flow ;
} e [ maxm << 1 ] ;
int num , head [ maxn ] ;
void Add ( int from , int to , int cap ) {
     e [ ++num ] . to = to ;
     e [ num ] . next = head [ from ] ;
     head [ from ] = num ;
     e [ num ] . cap = cap ;
     e [ num ] . flow = 0 ;
     Position [ from ] [ to ] = num ;
     e [ ++num ] . to = from ;
     e [ num ] . next = head [ to ] ; 
     head [ to ] = num ;
     e [ num ] . cap = 0 ;
     e [ num ] . flow = 0 ;
     Position [ to ] [ from ] = num ;
}
int n , m , s , t , x , last [ maxn ] , flow , a [ maxn ] , tmp , i1 , i2 , i3 ;
queue < int > Q ;
int main(){
    n = read() ; m = read() ;  s = read() ; t = read() ;
    rep ( i , 1 , m ) {
        i1 = read() ; i2 = read() ; i3 = read() ; 
        Add ( i1 , i2 , i3 ) ;
    }
    while ( 1 ) {
        memset ( a , 0 , sizeof ( a ) ) ;
        while ( !Q . empty() ) Q . pop();
        Q . push ( s ) ;
        a [ s ] = INF ;
        while ( ! Q . empty() ) {
            x = Q.front() ;
            Q . pop() ;
            for ( int i = head [ x ] ; i ; i = e [ i ] . next ) {
                if ( !a [ e [ i ] . to ] && e [ i ] . cap > e [ i ] . flow ) {
                    a [ e [ i ] . to ] = min ( a [ x ] , e [ i ] . cap - e [ i ] . flow ) ;
                    last [ e[ i ] . to ] = x ;
                    Q . push ( e [ i ] . to ) ;
                }
            }
            if ( a [ t ] ) break ;
        }
        if ( !a [ t ] ) break ;
        for ( int i = t ; i != s ; i = last [ i ] ) {
            tmp = Position [ i ] [ last [ i ] ] ;
            e [ tmp ] . flow -= a [ t ] ;
            e [ tmp - 1 ] . flow += a [ t ] ;
        }
        flow += a [ t ] ;
    }
    printf ( "%d\n" , flow ) ;
    return 0 ;
}

Who can help me ? Thans a lot .


by 独活 @ 2018-05-10 23:22:48

あなたは中国人ですね?何を間違っているのか教えてあげる


by wky32768 @ 2018-05-11 07:13:47

Thans a lot的大佬。。 太强了


by star_magic_young @ 2018-05-11 09:24:20

@qihoo360

Don't speak\color{white}\text{嘤}English

\color{white}\text{你叫了吧,别不中考}

by Huami360 @ 2018-05-11 19:40:31

@star_magic_young You speak Japanese , don't you ?


by Huami360 @ 2018-05-11 19:42:16

This problem has been solved by specially judging


by star_magic_young @ 2018-05-12 06:45:41

@Qihoo360 Don't use the spj.

\color{white} \text{I didn't speak Japenese at all.Are you kidding me???}

by YLWang @ 2018-06-10 21:21:13

@Qihoo360 Where are you from?


|