记录编号	379167	评测结果	AAAAAAAAAA
题目名称	双核cpu	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.422 s
提交时间	2017-03-05 20:12:12	内存使用	0.63 MiB

#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <list>
using namespace std;
#define MAXN 20005
struct edge{
  int from, to;
  int rem;
};vector<edge> edges;
vector<int> G[MAXN];
void addedge(int u, int v, int c, bool magic = false){
  edges.push_back((edge){u, v, c});
  edges.push_back((edge){v, u, magic?c:0});
  int k = edges.size();
  G[u].push_back(k-2);
  G[v].push_back(k-1);
}
int dist[MAXN];
bool vis[MAXN];
bool bfs(int s, int t){
  queue<int> q;
  memset(vis, 0, sizeof(vis));
  q.push(s);
  dist[s] = 0;
  vis[s] = true;
  while(!q.empty()){
    int u = q.front(); q.pop();
    for(int i = 0; i < G[u].size(); i++){
      edge &e = edges[G[u][i]];
      if(!vis[e.to] && e.rem > 0){
        q.push(e.to); dist[e.to] = dist[u]+1, vis[e.to] = true;
      }
    }
  }
  return vis[t];
}
int dfs(int u, int t, int f){
  if(!f || u == t)return f;
  int tot = 0;
  for(int i = 0; i < G[u].size(); i++){
    edge &e = edges[G[u][i]];
    int next = 0;
    if(dist[e.to] == dist[u]+1 && (next = dfs(e.to, t, min(f, e.rem))) > 0){
      tot += next, e.rem -= next, edges[1^G[u][i]].rem += next, f -= next;
      if(!f)break;
    }
  }
  return tot;
}
int maxflow(int s, int t){
  int f = 0;
  while(bfs(s, t))f += dfs(s, t, 0x7fffffff);
  return f;
}
int main(){
  freopen("cpu.in", "r", stdin);
  freopen("cpu.out", "w", stdout);
  int n, m; scanf("%d %d", &n, &m);
  int s = 0, t = n+1;
  for(int i = 1, x, y; i <= n; i++){
    scanf("%d %d", &x, &y);
    addedge(s, i, x); addedge(i, t, y);
  }
  for(int i = 0, x, y, w; i < m; i++){
    scanf("%d %d %d", &x, &y, &w);
   // addedge(x, y, w, true);
     addedge(x, y, w);
     addedge(y, x, w);
  }
  printf("%d\n", maxflow(s, t));
  return 0;
}