Zhou xingxing is the successor of one style of kung fu called "Karate Kid".he is falling love with a beautiful judo student,after being humiliated by her boyfriend,a Taekwando master from Japan,Zhou is going to fight with his rival in love.The way they fight is to destroy the wooden plank between some wooden pegs,in order to cut these wooden pegs into two disconnected parts,and destroy each piece of plank need consume different energy.However Zhou xingxing is beginner after all,so he is turn to you for help,please calculate the minimum energy he need to destroy the wooden plank.

Input

The input consists of multiple test cases. 
Each test case starts with two integers n (0 < n <= 100) and m in one line, where n、m are the number of wooden pegs and wooden plank. 
Following are m lines, each line contains three integers s, e and q (0 <= s, e < n,q > 0), meaning that there need q energy to destroy the wooden plank between s and e.

Output

There is only one line for each test case, which contains the minimum energy they need to complete this fight.

Sample Input

2 1
0 1 50
3 2
0 1 50
1 2 10

Sample Output

50
10

题意：求最小割

题解：sw算法求最小割，代码先放在这。。以后再来写 思想

#include<stdio.h>
#include<string.h>
 
#define NN 504
#define INF 1 << 30
int vis[NN];
int wet[NN];
int combine[NN];
int map[NN][NN];
 
int S, T, minCut, N;
void Search(){
     int i, j, Max, tmp;
     memset(vis, 0, sizeof(vis));
     memset(wet, 0, sizeof(wet));
     S = T = -1;
     for (i = 0; i < N; i++){
         Max = -INF;
         for (j = 0; j < N; j++){
             if (!combine[j] && !vis[j] && wet[j] > Max){
                tmp = j;
                Max = wet[j];
             }
         }
         if (T == tmp) return;
         S = T; T = tmp;
         minCut = Max;
         vis[tmp] = 1;
         for (j = 0; j < N; j++){
             if (!combine[j] && !vis[j]){
                wet[j] += map[tmp][j];
             }
         }
     }
}
int Stoer_Wagner(){
    int i, j;
    memset(combine, 0, sizeof(combine));
    int ans = INF;
    for (i = 0; i < N - 1; i++){
        Search();
        if (minCut < ans) ans = minCut;
        if (ans == 0) return 0;
        combine[T] = 1;
        for (j = 0; j < N; j++){
            if (!combine[j]){
               map[S][j] += map[T][j];
               map[j][S] += map[j][T];
            }
        }
    }
    return ans;
}
int main()
{
    int a, b, c, M;
    while(scanf("%d%d", &N, &M) != EOF){
       memset(map, 0, sizeof(map));
       while(M--){
          scanf("%d%d%d", &a, &b, &c);
          map[a][b] += c;
          map[b][a] += c;
       }
       printf("%d\n", Stoer_Wagner());
    }
    return 0;
}