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;
}

UVAOJ 1515 Pool construction

給每個格子一個點
連到s代表選地，連到t代表選洞
相鄰的再連一條cost為b的無向邊
做最大流

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 10000000
using namespace std;
typedef long long int int64;
struct{ int a, b, val; }lks[100000]; int lks_cnt;
vector<int> to[100000];
int _n;
void init(int n){
 _n = n;
 for(int lx = 0;lx < n;lx++){
  to[lx].clear();
 }
 lks_cnt = 0;
 return;
}
void addlink(int a, int b, int ab){
 //printf("link %d -> %d with %d\n", a, b, ab);
 lks[lks_cnt].a = a, lks[lks_cnt].b = b, lks[lks_cnt].val = ab; to[a].push_back(lks_cnt++);
 lks[lks_cnt].a = b, lks[lks_cnt].b = a, lks[lks_cnt].val = 0; to[b].push_back(lks_cnt++);
 return;
}
int dis[100000], que[100000] ;
int bfs(int s, int t){
 int n = _n;
 for(int lx = 0;lx < n;lx++){
  dis[lx] = -1;
 }
 dis[s] = 0;
 int qs = 0, qe = 1;
 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[100000];
int dfs(int vv, int df, int s, int t){
 //printf("dfs: %d\n", vv);
 //for(int lx = 0;lx/100000 < 100;lx++);
 if(vv == t) return df;
 if(vis[vv]) return 0;
 vis[vv] = true;
 for(int lx = 0;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(df, lks[lind].val), 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 = 0;
 while(bfs(s, t))
  for(;;){
   memset(vis, 0, sizeof(vis));
   int df = dfs(s, 1000000000, s, t);
   if(df == 0) break;
   f += df;
  }
 return f;
}
int ctr = 0; int get_ind(){return ctr++;}
int main()
{
 int T;scanf("%d", &T);
 while(T--){
  int w, h; scanf("%d %d", &w, &h);
  int d, f, b;scanf("%d %d %d", &d, &f, &b);
  int Map[60][60];
  for(int lx = 0;lx < h;lx++){
   char str[1000];
   scanf("%s", str);
   for(int ly = 0;ly < w;ly++)
    Map[lx][ly] = str[ly] == '#';
  }

  ctr = 0;
  int ss = get_ind(), tt = get_ind();
  int map_nod[100][100];
  for(int lx = 0;lx < h;lx++)
   for(int ly = 0;ly < w;ly++)
    map_nod[lx][ly] = get_ind();
  int ind_count = get_ind();
  init(ind_count);
  for(int lx = 0;lx < h;lx++){
   for(int ly = 0;ly < w;ly++) {
    if((lx == 0) or (lx == h-1) or (ly == 0) or (ly == w-1)){
     if(Map[lx][ly]){
      addlink(map_nod[lx][ly], tt, INF);
     }else{
      addlink(ss, map_nod[lx][ly], f);
      addlink(map_nod[lx][ly], tt, INF);
     }
    }else{
     if(Map[lx][ly]){
      addlink(map_nod[lx][ly], tt, d);
     }else{
      addlink(ss, map_nod[lx][ly], f);
     }
    }
   }
  }
  for(int lx = 0;lx < h-1;lx++){
   for(int ly = 0;ly < w;ly++){
    //down
    addlink(map_nod[lx][ly], map_nod[lx+1][ly], b);
    addlink(map_nod[lx+1][ly], map_nod[lx][ly], b);
   }
  }
  for(int lx = 0;lx < h;lx++){
   for(int ly = 0;ly < w-1;ly++){
    //down
    addlink(map_nod[lx][ly], map_nod[lx][ly+1], b);
    addlink(map_nod[lx][ly+1], map_nod[lx][ly], b);
   }
  }
  printf("%d\n", dinic(ss, tt));
 }
 return 0;
}

UVA 10330 - Power Transmission

點流量

#include<cstdio>
#include<cstdlib>
#include<vector>
#define INF 100000000
using namespace std;
vector<int> to[1000];
struct{ int a, b, val;} es[10001]; int ecnt;
int _n;
void init(int n){
    _n = n;
    for(int lx = 0;lx <= n;lx++)
        to[lx].clear();
    ecnt = 0;
    return;
}
void addedge(int a, int b, int val){
    //printf("%d~%d = %d\n", a, b, val);
    es[ecnt].a = a, es[ecnt].b = b, es[ecnt].val = val; to[a].push_back(ecnt++);
    es[ecnt].a = b, es[ecnt].b = a, es[ecnt].val = 0; to[b].push_back(ecnt++);
    return;
}
int que[10000];
int frm[10000];
int vis[10000];
int pth[10000]; int pathcnt;
int bfs(int s, int t){
    int n = _n;
    for(int lx = 0;lx <= n;lx++)
        frm[lx] = -1, vis[lx] =0;
    int qs = 0, qe = 1;
    que[0] = s, vis[s] = 1;
    while(qs < qe){
        int g = que[qs++];
        for(int lx = 0;lx < to[g].size();lx++){
            int lind = to[g][lx];
            int pind = es[lind].b;
            if(vis[pind]) continue;
            if(es[lind].val <= 0) continue;
            frm[pind] = lind;
            que[qe++] = pind;
            vis[pind] = 1;
        }
    }
    if(vis[t] == -1) return 0;
    int pp = t;
    pathcnt = 0;
    int min_val = INF;
    while(pp != s){
        int lind = frm[pp];
        pth[pathcnt++] = lind;
        min_val = min(min_val, es[lind].val);
        pp = es[lind].a;
    }
    for(int lx = 0;lx < pathcnt;lx++){
        int lind = pth[lx];
        es[lind].val -= min_val;
        es[lind^1].val += min_val;
    }
    return min_val;
}
int Ekarp(int s, int t){
    int f = 0, df = 1;
    while(df){
        df = bfs(s, t);
        f += df;
    }
    return f;
}

int now_ind;
int get_ind(){return now_ind++;}

int main()
{
    int n;
    while(scanf("%d", &n) == 1){
        int pmax[1000] = {0};
        int mat[101][101] = {0};
        int ss, tt;
        int starr[100];
        for(int lx = 0;lx < n;lx++)
            scanf("%d", pmax+lx);
        int m; scanf("%d", &m);
        while(m--){
            int a, b, val; scanf("%d %d %d", &a, &b, &val);
            mat[a-1][b-1] += val;
        }
        scanf("%d %d", &ss, &tt);
        for(int lx = 0;lx < ss+tt;lx++){
            scanf("%d", starr+lx);
            starr[lx]--;
        }
        now_ind = 0;
        int ms = get_ind(), mt = get_ind();
        //printf("ms %d, mt %d\n", ms, mt);
        int mpin[101], mpout[101];
        for(int lx = 0;lx < n;lx++)
            mpin[lx] = get_ind(), mpout[lx] = get_ind();
        init(get_ind());
        for(int lx = 0;lx < ss;lx++)
            addedge(ms, mpin[starr[lx]], INF);
        for(int lx = 0;lx < tt;lx++)
            addedge(mpout[starr[ss+lx]], mt, INF);
        for(int lx = 0;lx < n;lx++)
            addedge(mpin[lx], mpout[lx], pmax[lx]);
        for(int lx = 0;lx < n;lx++)
            for(int ly = 0;ly < n;ly++)
                if(mat[lx][ly])
                    addedge(mpout[lx], mpin[ly], mat[lx][ly]);
        printf("%d\n", Ekarp(ms, mt));
    }
    return 0;
}