Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 3中所示的都是图 2中的无向图的最小生成树：

输入文件的第一行有3个正整数n、m、Lab分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。

接下来m行依次描述标号为1,2,3…m的无向边，每行描述一条边。每个描述包含3个整数x、y、d，表示这条边连接着标号为x、y的点，且这条边的权值为d。

输入文件保证1<=x,y<=N,x不等于y,且输入数据保证这个无向图一定是一个连通图。

#include <queue>

#include <cstdio>

#include <cstring>

#define N 510

#define K 810

#define M 100010

using namespace std;

queue<int> q;

int x[K] , y[K] , z[K] , head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N];

void add(int x , int y , int z)

{

    to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;

    to[++cnt] = x , val[cnt] = z , next[cnt] = head[y] , head[y] = cnt;

}

bool bfs()

{

    int x , i;

    memset(dis , 0 , sizeof(dis));

    while(!q.empty()) q.pop();

    dis[s] = 1 , q.push(s);

    while(!q.empty())

    {

        x = q.front() , q.pop();

        for(i = head[x] ; i ; i = next[i])

        {

            if(val[i] && !dis[to[i]])

            {

                dis[to[i]] = dis[x] + 1;

                if(to[i] == t) return 1;

                q.push(to[i]);

            }

        }

    }

    return 0;

}

int dinic(int x , int low)

{

    if(x == t) return low;

    int temp = low , i , k;

    for(i = head[x] ; i ; i = next[i])

    {

        if(val[i] && dis[to[i]] == dis[x] + 1)

        {

            k = dinic(to[i] , min(temp , val[i]));

            if(!k) dis[to[i]] = 0;

            val[i] -= k , val[i ^ 1] += k;

            if(!(temp -= k)) break;

        }

    }

    return low - temp;

}

int main()

{

    int n , m , p , i , ans = 0;

    scanf("%d%d%d" , &n , &m , &p);

    for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d" , &x[i] , &y[i] , &z[i]);

    s = x[p] , t = y[p];

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

        if(i != p && z[i] <= z[p])

            add(x[i] , y[i] , z[p] - z[i] + 1);

    while(bfs()) ans += dinic(s , 1 << 30);

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

    return 0;

}