Ikki's Story I - Road Reconstruction

Description

Ikki is the king of a small country – Phoenix, Phoenix is so small that there is only one city that is responsible for the production of daily goods, and uses the road network to transport the goods to the capital. Ikki finds that the biggest problem in the country is that transportation speed is too slow.

Since Ikki was an ACM/ICPC contestant before, he realized that this, indeed, is a maximum flow problem. He coded a maximum flow program and found the answer. Not satisfied with the current status of the transportation speed, he wants to increase the transportation ability of the nation. The method is relatively simple, Ikki will reconstruct some roads in this transportation network, to make those roads afford higher capacity in transportation. But unfortunately, the country of Phoenix is not so rich in GDP that there is only enough money to rebuild one road. Ikki wants to find such roads that if reconstructed, the total capacity of transportation will increase.

He thought this problem for a loooong time but cannot get it. So he gave this problem to frkstyc, who put it in this POJ Monthly contest for you to solve. Can you solve it for Ikki?

Input

The input contains exactly one test case.

The first line of the test case contains two integers N, M (N ≤ 500, M ≤ 5,000) which represents the number of cities and roads in the country, Phoenix, respectively.

M lines follow, each line contains three integers a, b, c, which means that there is a road from city a to city b with a transportation capacity of c (0 ≤ a, b < n, c ≤ 100). All the roads are directed.

Cities are numbered from 0 to n − 1, the city which can product goods is numbered 0, and the capital is numbered n − 1.

Output

You should output one line consisting of only one integer K, denoting that there are K roads, reconstructing each of which will increase the network transportation capacity.

Sample Input

2 1
0 1 1

Sample Output

1
题意：这个题意真坑爹。给出点跟边，问对最大流之后的每条路径中只重建一条边。使得流更大。
分析：这么说来，能被重建的边就满足最小割。但每个流路中最小割可以多个，由于题目要求每个流路只能重建一条边。所有一个流路出现两个最小割就肯定不能被重建边。如果只出现一个最小割边u,v，那最大流后，从源还可容纳更多流到u，从v还有更多流量到t，只要增加u跟v的容量，就是一个满足题意的边。所以最大流之后从s做dfs，在从t做dfs。
#include <stdio.h>  
#include <string.h> 
#include <queue> 
#include <algorithm>
#include <iostream>
#define Min(a, b) (a) < (b) ? a : b  
#define Max(a, b) (a) > (b) ? a : b
using  namespace std;  
const  int MAXN = 2005;  
const  int MAXM = 700000;  
const  int INF = 1100000000;  
struct  Edge  
{  
    int  st, ed;  
    int  next;  
    int  flow; 
    int cap; 
}edge[MAXM]; 
int  head[MAXN], level[MAXN], que[MAXN], E;
int lf[MAXN], rf[MAXN], map[MAXN][MAXN];
void add(int u, int v, int w)  
{  
    edge[E].flow = 0;  
    edge[E].cap = w;
    edge[E].st = u;  
    edge[E].ed = v;  
    edge[E].next = head[u];  
    head[u] = E++;      
    edge[E].flow = 0; 
    edge[E].cap = 0; 
    edge[E].st = v;  
    edge[E].ed = u;  
    edge[E].next = head[v];  
    head[v] = E++;  
}
int dinic_bfs(int src, int dest, int ver)        
{        
    int i, j;         
    for (i = 0; i <= ver; i++)
    {    
        level[i] = -1;
    }
    int rear = 1;        
    que[0] = src; level[src] = 0;        
    for(i = 0; i < rear; i++) 
    {        
          for(j = head[que[i]]; j != -1; j = edge[j].next)
         {        
            if(level[edge[j].ed] == -1 && edge[j].cap > edge[j].flow)        
            {        
              level[edge[j].ed] = level[que[i]]+1;        
              que[rear++] = edge[j].ed;        
            }
         }
    }
    return  level[dest] >= 0;        
}        
     
int dinic_dfs(int src, int dest, int ver)        
{        
    int stk[MAXN], top = 0;        
    int ret = 0, cur, ptr, pre[MAXN], minf, i;        
    int del[MAXN];        
    for (i = 0; i <= ver; i++) 
    {
        del[i] = 0;
    }
    stk[top++] = src;         
    pre[src] = src; 
    cur = src;        
    while(top)        
    {        
        while(cur != dest && top)        
        {        
            for(i = head[cur]; i != -1; i = edge[i].next)        
            {        
                if(level[edge[i].ed] == level[cur] + 1 && edge[i].cap > edge[i].flow  && !del[edge[i].ed])        
                {        
                    stk[top++] = edge[i].ed;      
                    cur = edge[i].ed;        
                    pre[edge[i].ed] = i;                       
                    break;     
                }        
            }     
            if(i == -1)       
            {        
                del[cur] = 1;        
                top--;        
                if(top) cur = stk[top-1];        
            }        
        }                
        if(cur == dest)        
        {       
            minf = INF;        
            while(cur != src)        
            {        
                cur = pre[cur];        
                if(edge[cur].cap - edge[cur].flow < minf) minf = edge[cur].cap - edge[cur].flow;        
                cur = edge[cur].st;        
            }
            cur = dest;        
            while(cur != src)        
            {        
                cur = pre[cur];        
                edge[cur].flow += minf;        
                edge[cur^1].flow -= minf;        
                if(edge[cur].cap - edge[cur].flow == 0)
                {
                     ptr = edge[cur].st;
                }
                cur = edge[cur].st;        
            }        
            while(top > 0&& stk[top-1] != ptr) top--;        
            if(top)  cur = stk[top-1];        
            ret += minf;      
        }        
    }        
    return ret;        
}        
int Dinic(int src, int dest, int ver)        
{        
    int  ret = 0, t;        
    while(dinic_bfs(src, dest, ver))        
    {        
        t = dinic_dfs(src, dest, ver);        
        if(t) ret += t;        
        else  break;        
    }        
    return ret;        
}
void dfs(int u)
{
    lf[u] = 1;
    int i;
    for (i = head[u]; i != -1; i = edge[i].next)
    {
        //表示能提供流量。这要保证每个走向t的弧有残流就可增广 
        if (!lf[edge[i].ed] && edge[i].cap - edge[i].flow > 0)
        {
            dfs(edge[i].ed);
        }
    }
}
void revdfs(int u)//通过t反搜
{
    rf[u] = 1;
    int i;
    for (i = head[u]; i != -1; i = edge[i].next)
    {
        /*
        如果edge[i]是反向弧，正弧有残流才可增广 
        */
        /*
        如果edge[i]是正向弧：
        1.如果edge[i]为空，这是反弧没残流， 
         2.如果edge[i]不为空，则反弧一定有残流 
        */
        //所以不管现在指向s的是什么弧，保证指向t的弧有残流，就可以增广 
        if (!rf[edge[i].ed] && edge[i].cap - edge[i].flow >= 0 && edge[i^1].cap > edge[i^1].flow)// 
        {
            revdfs(edge[i].ed);
        }
    }
}
int main()
{
    int n, m, i, j, u, v, w;
    
    scanf("%d%d", &n, &m);
    int s = 0, t = n - 1, ver = t + 1;
    E = 0;
    for (i = 0; i <= ver; i++)
    {
        head[i] = -1;
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            map[i][j] = -1;
        }
    }
    while (m--)
    {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        /*在这里标记出现了u到v的边。
        出现重边时，也只能有一条被重，因为这条边按题意可以被扩大最小割不再这个边上
        */
        map[u][v] = 1; 
    }
    int ans, num;
    ans = Dinic(s, t, ver);
    for (i = 0; i <= ver; i++) 
    {
        lf[i] = rf[i] = 0;
    }
    dfs(s), revdfs(t);
    num = 0;
    for (i = 0; i < E; i += 2)//这些都是正向弧，原图中的边。 
    {
        u = edge[i].st, v = edge[i].ed;
        if (map[u][v] == 1 && lf[u] && rf[v])
        {
            num++;
            map[u][v] = -1;//被重建过后就下次不会再被重建了。 
        }
    }
    printf("%d\n", num);
    return 0;
}
/*
4 4
0 1 2
1 2 1
1 2 1
2 3 2


4 4
0 1 3
1 2 1
1 2 1
2 3 3

6 6
0 1 2
1 2 1
1 3 1
2 4 1
3 4 1
4 5 2

2 1
0 1 1

2 1
0 1 0

4 3
0 1 2
2 1 2
2 3 2




*/