# 某島

… : "…アッカリ～ン . .. . " .. .
October 15, 2014

## BZOJ 1927. [Sdoi2010]星際競速

### Analysis:

```
//}/* .................................................................................................................................. */

int n, m;

namespace MinCostMaxFlow{

const int N = 2048, M = 2*N*N + 9;
const int NN = 2047; // cover_bit(N) - 1

int D[N], hd[N], suc[M], to[M], cap[M], cst[M];
int n, m, s, t; LL nesf, flow, cost;

int new_node(){
hd[n] = 0;
return n++;
}

inline void add_edge(int x, int y, int c, int w = 0){
suc[m] = hd[x], to[m] = y, cap[m] = c, cst[m] =  w, hd[x] = m++;
suc[m] = hd[y], to[m] = x, cap[m] = 0, cst[m] = -w, hd[y] = m++;
//nesf += w;
}

inline void add_edgee(int x, int y, int c, int w = 0){
}

int Q[NN+1], pre[N], cz, op; bool inQ[N];

#define v to[i]
#define c cap[i]
#define f cap[i^1]
#define w cst[i]

bool spfa(){
fill(inQ, inQ+n, 0), fill(D, D+n, INF);
cz = 0, op = 1; D[Q[cz] = s] = 0; while (cz != op){
int u = Q[cz++]; inQ[u] = 0; cz &= NN;
REP_G(i, u) if (c && checkMin(D[v], D[u]+w)){
pre[v] = i; if (!inQ[v]) Q[op++] = v, inQ[v] = 1, op &= NN;
}
}
return D[t] != INF;
}

#undef v

int d = INF; int u, v = t; do{
int i = pre[v]; checkMin(d, c);
u = to[i^1], v = u;
} while (u != s);

flow += d; u, v = t; do{
int i = pre[v]; f += d, c -= d; cost += d*w;
u = to[i^1], v = u;
} while (u != s);
}

pair<LL, LL> Run(){
cost = 0, flow = 0; while (spfa()) add_path();
return MP(cost, flow);
}

#undef c
#undef f
#undef w

void Init(){

RST(hd); m = 2; RD(::n, ::m); s = 0, t = 2*::n+1; n = t+1;

REP_1(i, ::n){
}

DO(::m){
int x, y, w; RD(x, y, w); if (x > y) swap(x, y);
}
}
} //using namespace MinCostMaxFlow;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

MinCostMaxFlow::Init();
cout << MinCostMaxFlow::Run().fi << endl;
}

```