题目大意：
无向图，求最大流。
算法讨论：
Dinic可过。终于我的常数还是太大。以后要注意下了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll; struct MF{
static const int N = + ;
static const int M = + ;
static const ll oo = 10000000000000LL; int n, m, s, t, tot, tim;
int first[N], next[M];
int u[M], v[M], cur[N], vi[N];
ll cap[M], flow[M], dis[N];
int que[N + N]; void Clear(){
tot = ;tim = ;
for(int i = ; i <= n; ++ i) first[i] = -;
}
void Add(int from, int to, ll cp, ll flw){
u[tot] = from; v[tot] = to; cap[tot] = cp; flow[tot] = flw;
next[tot] = first[u[tot]];
first[u[tot]] = tot;
++ tot;
}
bool bfs(){
++ tim;
dis[s] = ;vi[s] = tim; int head, tail;
head = tail = ;
que[head] = s;
while(head <= tail){
for(int i = first[que[head]]; i != -; i = next[i]){
if(vi[v[i]] != tim && cap[i] > flow[i]){
vi[v[i]] = tim;
dis[v[i]] = dis[que[head]] + ;
que[++ tail] = v[i];
}
}
++ head;
}
return vi[t] == tim;
}
ll dfs(int x, ll a){
if(x == t || a == ) return a;
ll flw = , f;
int &i = cur[x];
for(i = first[x]; i != -; i = next[i]){
if(dis[x] + == dis[v[i]] && (f = dfs(v[i], min(a, cap[i]-flow[i]))) > ){
flow[i] += f; flow[i^] -= f;
a -= f; flw += f;
if(a == ) break;
}
}
return flw;
}
ll MaxFlow(int s, int t){
this->s = s;this->t = t;
ll flw = ;
while(bfs()){
for(int i = ; i <= n; ++ i) cur[i] = ;
flw += dfs(s, oo);
}
return flw;
}
}Net;
int n, m; int main(){
int x, y;
ll z;
scanf("%d%d", &n, &m);
Net.n = n;
Net.Clear();
for(int i = ; i <= m; ++ i){
scanf("%d%d%lld", &x, &y, &z);
Net.Add(x, y, z, );
Net.Add(y, x, z, );
}
printf("%lld\n", Net.MaxFlow(,Net.n));
return ;
}
SPOJ 4110