POJ 3469 Dual Core CPU

把常數壓一壓就好了

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
struct{int a, b, val;}lks[500000]; int lkcnt; int _n;
vector<int> to[30000]; int cur[30000];
void init(int n){
 lkcnt = 0;
 _n = n;
 for(int lx = 0;lx < n;lx++)
  to[lx].clear();
 return;
}
void addlink(int a, int b, int ab, int ba = 0){
 lks[lkcnt].a = a, lks[lkcnt].b = b, lks[lkcnt].val = ab; to[a].push_back(lkcnt++);
 lks[lkcnt].a = b, lks[lkcnt].b = a, lks[lkcnt].val = ba ; to[b].push_back(lkcnt++);
 return;
}
int dis[30000], que[30000];
int bfs(int s, int t){
 int n = _n;
 for(int lx = 0;lx < n;lx++) dis[lx] = -1;
 int qs = 0, qe = 1; dis[s] = 0, que[0] = s;
 while(qs < qe){
  int g = que[qs++];
  for(int lx = 0;lx < to[g].size();lx++){
   int lind = to[g][lx];
   int pind = lks[lind].b;
   if(dis[pind] != -1) continue;
   if(lks[lind].val == 0) continue;
   dis[pind] = dis[g] + 1;
   que[qe++] = pind;
  }
 }
 return dis[t] != -1;
}
bool vis[30000];
int dfs(int vv, int df, int s, int t){
 if(vv == t) return df;
 if(vis[vv]) return 0;
 vis[vv] = true;
 for(int& lx = cur[vv];lx < to[vv].size();lx++){
  int lind = to[vv][lx];
  int pind = lks[lind].b;
  if(lks[lind].val == 0) continue;
  if(dis[pind] != dis[vv]+1) continue;
  int f = dfs(pind, min(lks[lind].val, df), s, t);
  if(f > 0){
   lks[lind].val -= f;
   lks[lind^1].val += f;
   return f;
  }
 }
 return 0;
}
int dinic(int s, int t){
 int f = 0, df;
 while(bfs(s, t)){
  memset(cur, 0, sizeof(cur));
  for(;;){
   memset(vis, 0, sizeof(vis));
   df = dfs(s, 1000000000, s, t);
   if(df == 0) break;
   f += df;
  }
 }
 return f;
}
int main()
{
    int n, m, a, b, w;
    scanf("%d %d", &n, &m);
    init(n+2);
    for(int lx = 0;lx < n;lx++){
  scanf("%d %d", &a, &b);
  addlink(0, lx+1, a);
  addlink(lx+1, n+1, b);
    }
    for(int lx = 0;lx < m;lx++){
  scanf("%d %d %d", &a, &b, &w);
  addlink(a, b, w, w);
    }
    printf("%d\n", dinic(0, n+1));
 return 0;
}