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




*/