1 /**  2  * Uva  3  * Problem#1658  4  * Accepted  5  */  6 #include<iostream>  7 #include<cstdio>  8 #include<cctype>  9 #include<cstring> 10 #include<cstdlib> 11 #include<fstream> 12 #include<sstream> 13 #include<algorithm> 14 #include<map> 15 #include<set> 16 #include<queue> 17 #include<vector> 18 #include<stack> 19 using namespace std; 20 typedef bool boolean; 21 #define INF 0xfffffff 22 #define smin(a, b) a = min(a, b) 23 #define smax(a, b) a = max(a, b) 24 template<typename T> 25 inline boolean readInteger(T& u){ 26     char x; 27     int aFlag = 1; 28     while(!isdigit((x = getchar())) && x != ‘-‘ && ~x); 29     if(x == -1){ 30         return false; 31     } 32     if(x == ‘-‘){ 33         x = getchar(); 34         aFlag = -1; 35     } 36     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 37     ungetc(x, stdin); 38     u *= aFlag; 39     return true; 40 } 41  42 ///map template starts 43 typedef class Edge{ 44     public: 45         int end; 46         int next; 47         int cap; 48         int flow; 49         int cost; 50         Edge(const int end = 0, const int next = 0, const int cap = 0, const int flow = 0, const int cost = 0):end(end), next(next), cap(cap), flow(flow), cost(cost){} 51 }Edge; 52  53 typedef class MapManager{ 54     public: 55         int ce; 56         int *h; 57         Edge *edge; 58         MapManager(){} 59         MapManager(int points, int limit):ce(0){ 60             h = new int[(const int)(points + 1)]; 61             edge = new Edge[(const int)(limit + 1)]; 62             memset(h, 0, sizeof(int) * (points + 1)); 63         } 64         inline void addEdge(int from, int end, int cap, int flow, int cost){ 65             edge[++ce] = Edge(end, h[from], cap, flow, cost); 66             h[from] = ce; 67         } 68         inline void addDoubleEdge(int from, int end, int cap, int cost){ 69             addEdge(from, end, cap, 0, cost); 70             addEdge(end, from, cap, cap, -cost); 71         } 72         Edge& operator [](int pos){ 73             return edge[pos]; 74         } 75         inline int reverse(int pos){ 76             return (pos & 1) ? (pos + 1) : (pos - 1); 77         } 78         inline void clean(){ 79             delete[] h; 80             delete[] edge; 81             ce = 0; 82         } 83 }MapManager; 84 #define m_begin(g, i) (g).h[(i)] 85 /// map template ends 86  87 int n, m; 88 MapManager g; 89  90 inline boolean init(){ 91     if(!readInteger(n))    return false; 92     readInteger(m); 93     g = MapManager(n * 2, m * 2 + n * 2); 94     for(int i = 1, a, b, w; i <= m; i++){ 95         readInteger(a); 96         readInteger(b); 97         readInteger(w); 98         g.addDoubleEdge(a + n, b, 1, w); 99     }100     for(int i = 1; i <= n; i++){            //拆点 101         g.addDoubleEdge(i, i + n, 1, 0);102     }103     return true;104 }105 106 int* dis;107 boolean* visited;108 int* last;109 int* laste;110 int* mflow;111 int cost;112 int s, t;113 queue<int> que;114 int sizee;115 116 inline void spfa(){117     memset(dis, 0x7f, sizeof(int) * (sizee));118     memset(visited, false, sizeof(boolean) * (sizee));119     que.push(s);120     last[s] = 0;121     dis[s] = 0;122     laste[s] = 0;123     mflow[s] = INF;124     visited[s] = true;125     while(!que.empty()){126         int e = que.front();127         que.pop();128         visited[e] = false;129         for(int i = m_begin(g, e); i != 0; i = g[i].next){130             int &eu = g[i].end;131             if(dis[e] + g[i].cost < dis[eu] && g[i].flow < g[i].cap){132                 dis[eu] = dis[e] + g[i].cost;133                 last[eu] = e;134                 laste[eu] = i;135                 mflow[eu] = min(g[i].cap - g[i].flow, mflow[e]);136                 if(!visited[eu] && eu != t){137                     que.push(eu);138                     visited[eu] = true;139                 }140             }141         }142     }143     for(int i = t; i != s; i = last[i]){144         g[laste[i]].flow += mflow[t];145         g[g.reverse(laste[i])].flow -= mflow[t];146         cost += mflow[t] * g[laste[i]].cost;147     }148 }149 150 inline void minCostFlow(){151     s = 1 + n, t = n, sizee = 2 * n + 1;152     dis = new int[(const int)(sizee)];153     visited = new boolean[(const int)(sizee)];154     last = new int[(const int)(sizee)];155     laste = new int[(const int)(sizee)];156     mflow = new int[(const int)(sizee)];157     spfa();158     spfa();159 }160 161 inline void solve(){162     cost = 0;163     minCostFlow();164     printf("%d\n", cost);165     g.clean();166 }167 168 int main(){169     while(init()){170         solve();        171     }172     return 0;173 }