题目描述：N个城市（500），0点是生产商，N-1点是接受城市。现在0向n-1运输商品。

其中有M条有向边，每条边有容量，表示最大的运输量。

如果一条边的容量增加导致总流量的增加，这条边就是我们需要的。问一共有多少条这样的边，输出之。

解题报告：

直观理解，求最大流后，如果某一条边的残留是0，那么这条边有可能是我们需要的边（如0->1->2->3, 容量都是1，那么没有一条边是我们需要的，所以说是“可能是”），只有源点s到这条边的起点有增广路，同时这条边的终点到汇点t也有增广路的时候，增加这条边的容量才能使总流量增加。

那么，从原点s dfs一遍得到残留网络中原点s能到达的点。同时把边反向，从汇点t出发，得t可达的点。然后扫描残留为0的每条边，看看是不是起点可达s，汇点可达t。统计这样边的数量的就是答案。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n, m;
#define Max 0x1fffffff
#define size 600
struct edge{int from, to, val, next;}e[100000], e2[100000];
int v[size], que[size], dis[size], cnt, cur[size], v2[size], cnt2;
void insert(int from, int to, int va, int *v, edge *e, int &cnt)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt ;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
    e[cnt].next = v[to];v[to] = cnt ;
}
bool bfs(int n, int s, int t)
{
    int head, tail, id;
    head = tail = 0; que[tail ] = s;
    memset(dis, -1, sizeof(int) * n);dis[s] = 0;
    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
        for(id = v[que[head ]]; id != -1; id = e[id].next)
            if (e[id].val > 0 && dis[e[id].to] == -1)
            {
                dis[e[id].to] = dis[e[id].from] 1;
                que[tail ] = e[id].to;
                if (e[id].to == t) return true;
            }
    return false;
}

int Dinic(int n, int s, int t)
{
    int maxflow = 0, tmp, i;
    while(bfs(n, s, t))
    {
        int u = s, tail = 0;
        for(i = 0; i < n; i ) cur[i] = v[i];
        while(cur[s] != -1)
            if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] 1 == dis[e[cur[u]].to])
            {que[tail ] = cur[u]; u = e[cur[u]].to;}
            else if (u == t)
            {
                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
                for(maxflow = tmp, i = tail - 1; i >= 0; i--)
                {
                    e[que[i]].val -= tmp;
                    e[que[i] ^ 1].val = tmp;
                    if (e[que[i]].val == 0) tail = i;
                }
                u = e[que[tail]].from;
            }
            else
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
bool vst[2][size];
void dfs(int id, int *v, edge *e, bool flag)
{
    vst[flag][id] = 1;
    for(int i = v[id]; i != -1; i = e[i].next)
        if (e[i].val > 0 && !vst[flag][e[i].to]) dfs(e[i].to, v, e, flag);
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        int s = 0, t = n - 1; memset(v, -1, sizeof(int) * (t 1)); cnt = cnt2 = 0;
        for(int i = 0; i < m; i )
        {
            int a, b, c;scanf("%d%d%d", &a, &b, &c);
            insert(a, b, c, v, e, cnt);
        }
        for(int i = 0; i < n; i ) vst[0][i] = vst[1][i] = 0;
        Dinic(t 1, s, t);
        memset(v2, -1, sizeof(int) * (n 1));
        for(int i = 0; i < cnt; i = 2)
            if (e[i].val > 0) insert(e[i].to, e[i].from, e[i].val, v2, e2, cnt2);
        dfs(s, v, e, 0), dfs(t, v2, e2, 1);
        int ans = 0;
        for(int i = 0; i < cnt; i = 2)
            if (e[i].val <= 0 && vst[0][e[i].from] && vst[1][e[i].to]) ans ;
        printf("%d\n", ans);
    }
    return 0;
}