【POJ 1273】Drainage Ditches（网络流）

一直不明白为什么我的耗时几百毫秒，明明差不多的程序啊，我改来改去还是几百毫秒。
...一个小时后：明白了，原来把最大值0x3f（77）取0x3f3f3f3f就把时间缩短为16ms了。可是为什么原来那样没有WA呢？哦，明白了，因为最大值写小了，dicnic会多跑几遍。
嗯顺便：0x3f3f3f3f也就是1061109567，也就是10^9级别的，是一个很大的数，而且加上一个10^9级别以下的数字也不会溢出。所以很多时候最大值取这个会比较好。最大的int是0x7fffffff，可以用常量INT_MAX 代替。

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

int arc[][], d[], q[];

int m, n, ans,tans;

bool bfs()

{

    memset(d, -, sizeof d);

    queue<int>q;

    q.push();

    d[] = ;

    while(!q.empty())

    {

        int i,k=q.front();

        q.pop();

        for(i = ; i <= n; i++)

            if(arc[k][i] >  && d[i] == -)

            {

                d[i] = d[k] + ;

                q.push(i);

            }

    }

    return d[n]>;

}

int dinic (int k, int low)

{

    if(k == n)return low;

    int a,i;

    for(i = ; i <= n; i++)

        if(d[i] == d[k] + &&  arc[k][i] >  &&(a = dinic(i, min(low, arc[k][i]))))

        {

                arc[k][i] -= a;

                arc[i][k] += a;

                return a;

        }

    return ;

}

int main()

{

    while(~scanf("%d%d", &m, &n))

    {

        memset(arc, , sizeof arc);

        for(int i = ; i < m; i++)

        {

            int u, v, c;

            scanf("%d%d%d", &u, &v, &c);

            arc[u][v] += c;

        }

        ans = ;

        while(bfs())

            while(tans=dinic(, 0X3f3f3f3f)) ans += tans;

        printf("%d\n",ans);

    }

    return ;

}