hdu 4280-白红宇

hdu 4280

阅读量：4127 次

发布时间：2019-05-25

本文共 5734 字，大约阅读时间需要 19 分钟。

最大流ISAP，邻接表+GAP+当前弧优化//时间为3877ms#include 
   
    #include 
    
     #define VM 100010#define EM 400010const int inf = 0x3f3f3f3f;struct E{    int to, frm, nxt, cap;}edge[EM];int head[VM],e,n,m,src,des;int dep[VM], gap[VM];void addedge(int cu, int cv, int cw){    edge[e].frm = cu;    edge[e].to = cv;    edge[e].cap = cw;    edge[e].nxt = head[cu];    head[cu] = e++;    edge[e].frm = cv;    edge[e].to = cu;    edge[e].cap = 0;    edge[e].nxt = head[cv];    head[cv] = e++;}int que[VM];void BFS(){    memset(dep, -1, sizeof(dep));    memset(gap, 0, sizeof(gap));    gap[0] = 1;    int front = 0, rear = 0;    dep[des] = 0;    que[rear++] = des;    int u, v;    while (front != rear)    {        u = que[front++];        front = front%VM;        for (int i=head[u]; i!=-1; i=edge[i].nxt)        {            v = edge[i].to;            if (edge[i].cap != 0 || dep[v] != -1)                continue;            que[rear++] = v;            rear = rear % VM;            ++gap[dep[v] = dep[u] + 1];        }    }}int cur[VM],stack[VM];int Sap()       //sap模板{    int res = 0;    BFS();    int top = 0;    memcpy(cur, head, sizeof(head));    int u = src, i;    while (dep[src] < n)    {        if (u == des)        {            int temp = inf, inser = n;            for (i=0; i!=top; ++i){                if (temp > edge[stack[i]].cap){                    temp = edge[stack[i]].cap;                    inser = i;                }            }            for (i=0; i!=top; ++i)            {                edge[stack[i]].cap -= temp;                edge[stack[i]^1].cap += temp;            }            res += temp;            top = inser;            u = edge[stack[top]].frm;        }        if (u != des && gap[dep[u] -1] == 0)            break;        for (i = cur[u]; i != -1; i = edge[i].nxt)            if (edge[i].cap != 0 && dep[u] == dep[edge[i].to] + 1)                break;        if (i != -1)        {            cur[u] = i;            stack[top++] = i;            u = edge[i].to;        }        else        {            int min = n;            for (i = head[u]; i != -1; i = edge[i].nxt)            {                if (edge[i].cap == 0)                    continue;                if (min > dep[edge[i].to])                {                    min = dep[edge[i].to];                    cur[u] = i;                }            }            --gap[dep[u]];            ++gap[dep[u] = min + 1];            if (u != src)                u = edge[stack[--top]].frm;        }    }    return res;}int main(){    int T, i;    scanf("%d", &T);    while (T--)    {        scanf("%d%d", &n, &m);        int x, y;        int Min = inf, Max = -inf;        for (i=1; i<=n; ++i)       //找出起点src 终点des        {            scanf("%d%d", &x, &y);            if (x <= Min)            {                src = i;                Min = x;            }            if (x >= Max)            {                des = i;                Max = x;            }        }        e = 0;        memset(head, -1, sizeof(head));        int u, v, c;        for (i=0; i!=m; ++i)        {            scanf("%d%d%d", &u, &v, &c);            addedge(u,v,c);            addedge(v,u,c);        }        int ans = Sap();        printf("%d\n", ans);    }    return 0;} 时间2770ms： #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;//Macro//STL-Alias#define UN(c, a) unique(c, a)#define MS(c, a) memset(c, a, sizeof c)#define FLC(c, a ,b) fill(c, c + a, b)#define LOS(c, a, b) lower_bound(c, a, b)#define UPS(c, a, b) upper_bound(c, a, b)//Syntax-Alias#define Rep(c, a, b) for (int c = (a); c < (b); c++)#define Nre(c, a, b) for (int c = (a); c > (b); c--)//DEBUG#define FK puts("Fu*k here!")#define PA(s, c, a, b, p, f){\ printf(s);\ Rep(c, a, b) printf(p, (f));\ puts("");}//Constant#define INFL (0x7fffffffffffffffLL)#define INFI (0x7fffffff)#define MOD ()#define MAXN (100005)//Type-Aliastypedef long long LL;typedef long double LD;typedef int AI[MAXN];typedef bool AB[MAXN];typedef double AD[MAXN];typedef LL ALL[MAXN];typedef LD ALD[MAXN];//FSGstruct Edge{ int v, w, next;};vector
                 
                   E;AI L;void G_ini(){ E.clear(); MS(L, -1);}void AE(int u, int v, int w){ Edge te = {v, w, L[u]}; L[u] = E.size(); E.push_back(te);}#define Ere(c, a, L) for (int c = L[a]; c != -1; c = E[c].next)//ISAPint ISAP(int src, int snk, int V){ static AI dis, gap, _L, se; int u = src, mxf = 0, te = 0; memcpy(_L, L, sizeof L); MS(dis, -1); MS(gap, 0); gap[dis[snk] = 0] = 1; queue
                  
                    Q; Q.push(snk); while (!Q.empty()) { int u = Q.front(); Q.pop(); Ere(i, u, L) if (E[i].w && dis[E[i].v] < 0) { gap[dis[E[i].v] = dis[u] + 1]++; Q.push(E[i].v); } } while (dis[src] < V) { int _i = -1; Ere(i, u, _L) if (E[i].w && dis[u] == dis[E[i].v] + 1) { _i = i; break; } if (_i != -1) { _L[u] = _i; u = E[se[te++] = _i].v; } else { int md = INFI; _i = -1; Ere(i, u, L) if (E[i].w && dis[E[i].v] < md) { md = dis[E[i].v]; _L[u] = i; } if (!--gap[dis[u]]) break; gap[dis[u] = md + 1]++; if (u != src) u = E[se[te-- - 1] ^ 1].v; } if (u == snk) { int _i = 0, mf = INFI; Rep(i, 0, te) if (E[se[i]].w < mf) { mf = E[se[i]].w; _i = i; } Rep(i, 0, te) { E[se[i]].w -= mf; E[se[i] ^ 1].w += mf; } mxf += mf; te = _i; u = E[se[_i] ^ 1].v; } } return mxf;}struct Isl{ int x, y; void inp() { scanf("%d%d", &x, &y); }} I[MAXN];int n, m;int main(){ int T; scanf("%d", &T); while (T--) { //Initialize scanf("%d%d", &n, &m); I[0].inp(); int src = 0, snk = 0; Rep(i, 1, n) { I[i].inp(); if (I[i].x < I[src].x) src = i; if (I[i].x > I[snk].x) snk = i; } G_ini(); while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); u--; v--; AE(u, v, w); AE(v, u, w); } //Solve printf("%d\n", ISAP(src, snk, n)); } return 0;}