现在的位置: 首页 > 综合 > 正文

POJ 3469 Dual Core CPU 最小割入门题

2014年09月05日 ⁄ 综合 ⁄ 共 1215字 ⁄ 字号 评论关闭
#include<stdio.h>
 #include<string.h>
 
 const int maxn = 20100;
 const int maxm = 200200;
 const int inf = 1<<29;
 
 struct node
 {
     int v, c, next;
 }edge[maxm*6];
 
 int head[maxn], tot;
 int n, m;
 
 void init()
 {
     int i;
     for(i = 0; i <= n+2; i++)
         head[i] = -1;
     tot = 0;
 }
 
 void add(int s, int t, int c)
 {
     edge[tot].v = t;
     edge[tot].c = c;
     edge[tot].next = head[s];
     head[s] = tot++;
     edge[tot].v = s;
     edge[tot].c = 0;
     edge[tot].next = head[t];
     head[t] = tot++;
 }
 
 int gap[maxn], dis[maxn], cur[maxn], pre[maxn];
 int sap(int s, int t, int vs)
 {
     bool flag;
     int i;
     for(i = 0; i <= vs; i++)
     {
         cur[i] = head[i];
         gap[i] = dis[i] = 0;
     }
     gap[0] = vs;
     int u = pre[s] = s, maxf = 0, aug = inf, v;
     while(dis[s] < vs)
     {
 loop:    for(i = cur[u]; i != -1; i = edge[i].next)
         {
             v = edge[i].v;
             if(edge[i].c > 0 && dis[u] == dis[v] + 1)
             {
                 flag = 1;
                 if(edge[i].c < aug) aug = edge[i].c;
                 pre[v] = u;
                 cur[u] = i;
                 u = v;
                 if(u == t)
                 {
                     maxf += aug;
                     while(u != s)
                     {
                         u = pre[u];
                         edge[cur[u]].c -= aug;
                         edge[cur[u]^1].c += aug;
                     }
                     aug = inf;
                 }
                 goto loop;
             }
         }
         int min_d = vs;
         for(i = head[u]; i != -1; i = edge[i].next)
         {
             v = edge[i].v;
             if(edge[i].c > 0 && dis[v] < min_d)
             {
                 min_d = dis[v];
                 cur[u] = i;
             }
         }
         if(!(--gap[dis[u]])) break;
         ++gap[dis[u] = min_d + 1];
         u = pre[u];
     }
     return maxf;
 }
 
 int main()
 {
     int i, j;
     int x, y, z;
     scanf("%d%d", &n, &m);
     init();
     int S = 0, T = n+1;
     for(i = 1; i <= n; i++)
     {
         scanf("%d%d", &x, &y);
         add(S, i, x);
         add(i, T, y);
     }
     for(i = 1; i <= m; i++)
     {
         scanf("%d%d%d", &x, &y, &z);
         add(x, y, z);
         add(y, x, z);
     }
     printf("%d\n", sap(S, T, n+2));
     return 0;
 }
 

抱歉!评论已关闭.