Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

为什么isap TLE，dinic却过了，我表示很不能理解，哪位大牛帮忙看下,而且我换了两个sap的板，都是TLE，哎

Posted by yaws at 2011-05-05 13:07:40 on Problem 1637

isap板一：   TLE
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

#define inf 1000000000
#define N 1500

struct node {
    int to, c, next;
} edge[1000];

int head[N], dis[N], cur[N], pre[N], gap[N];
int in[N], out[N];
int n, m, NUM;
int tot;
int s, t;

void init() {
    for (int i = 0; i <NUM; i++)
    {
        head[i] = -1;
        in[i]=0;
        out[i]=0;
    }
    tot =0;
}

int sap(int s, int t) {
    int u;
    bool flag;
    int aug = inf, flow = 0;
    for(int i=0;i<NUM;i++)
        pre[i]=0;
    for (int i = 0; i < NUM; i++) {
        cur[i] = head[i];
        gap[i] = 0;
        dis[i] = 0;
    }
    gap[s]=NUM;
    u = pre[s] = s;
    while (dis[s]<NUM) {
        flag = 0;
        for (int &j = cur[u]; j != -1; j = edge[j].next) {
            int v = edge[j].to;
            if (edge[j].c > 0 && dis[u] == dis[v] + 1) {
                flag = 1;
                if (edge[j].c < aug)
                    aug = edge[j].c;
                pre[v] = u;
                u = v;
                if (u == t) {
                    flow += aug;
                    while (u != s) {
                        u = pre[u];
                        edge[cur[u]].c -= aug;
                        edge[cur[u] + 1].c += aug;
                    }
                    aug = inf;
                }
                break;
            }
        }
        if (flag)continue;
        int mindis = NUM;
        for (int j = head[u]; j != -1; j = edge[j].next) {
            int v = edge[j].to;
            if (edge[j].c > 0 && dis[v] < mindis) {
                mindis = dis[v];
                cur[u] = j;
            }
        }
        gap[dis[u]]--;
        if (gap[dis[u]] == 0)
            return flow;
        dis[u] = mindis + 1;
        gap[dis[u]]++;
        if(pre[u]!=s)
        u = pre[u];
    }
    return flow;
}

void add(int from, int to, int w) {
    edge[tot].to = to;
    edge[tot].c = w;
    edge[tot].next = head[from];
    head[from] = tot++;
    edge[tot].to = from;
    edge[tot].c = 0;
    edge[tot].next = head[to];
    head[to] = tot++;
}

int main() {
    int tt;
    scanf("%d", &tt);
    while (tt--) {
        bool ok=1;
        scanf("%d%d", &n, &m);
        s = 0;
        t = n + 1;
        NUM = n + 2;
        init();
        for (int i = 1; i <= m; i++) {
            int u, v, id;
            scanf("%d%d%d", &u, &v, &id);
            if (id == 0) {
                add(u, v, 1);
            }
            in[v]++;
            out[u]++;
        }
        for(int i=1;i<=n;i++)
        {
           if(abs(in[i]-out[i])%2==1)
            {
                ok=0;
                break;
            }
        }
        if(ok==0)
            printf("impossible\n");
        else
        {
            int sum=0;
            for(int i=1;i<=n;i++)
            {
                int tmp=(out[i]-in[i])/2;
                if(tmp<0)
                    add(i,t,-tmp);
                else if(tmp>0)
                {
                    add(s,i,tmp);
                    sum+=tmp;
                }
            }
            if(sap(s,t)!=sum)
               ok=0;
            if(!ok)
                 printf("impossible\n");
            else
                printf("possible\n");
        }
    }
    return 0;
}




ISAP  板2：  TLE。。。。
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdlib>
using namespace std;

#define inf 1000000000
#define N 1500

struct edge{
    int u,v,c,next;
}e[10000];

int head[N],dist[N],now[N],pre[N],cnt[N],cur[N];
int n,m,NUM;//n表示点数,m表示边数 ,NUM表示总点数
int s,t,in[N],out[N];

void add(int u,int v,int va,int &tot)
{
    e[++tot].u = u; e[tot].v = v; e[tot].c = va;
    e[tot].next = head[u]; head[u] = tot;

    e[++tot].u = v; e[tot].v = u; e[tot].c = 0;
    e[tot].next = head[v]; head[v] = tot;
}

int sap(int st,int ed)
{
    int tot_flow;//总流量
    int i = st,j,t;
    int now_flow, found, mini;
    memset( dist, 0, sizeof( dist ) );
    memset( now, -1, sizeof( now ) );
    memset( cnt, 0, sizeof( cnt ) );
    tot_flow = 0; now_flow = inf;
    cnt[0] = NUM;
    while( dist[st] < NUM )
    {
        cur[i] = now_flow;      found = 0;
        if( now[i] == -1 ) t = head[i];
        else t = now[i];
        while( t != -1 )
        {
            j = e[t].v;
            if(e[t].c > 0 && dist[j] + 1 == dist[i])
            {
                found = 1; now[i] = t;
                if( e[t].c < now_flow ) now_flow = e[t].c;
                pre[j] = t; i = j;
                if(i == ed)
                {
                    tot_flow += now_flow;
                    while(i != st)
                    {
                        e[pre[i]].c -= now_flow;
                        e[pre[i]^1].c += now_flow;
                        i = e[pre[i]].u;
                    }
                    now_flow = inf;
                }
                break;
            }
            t = e[t].next;
        }
        if( found ) continue;
        if( --cnt[ dist[i] ] == 0) break;
        mini = n - 1;
        t = head[i];
        while( t != -1 )
        {
            if( e[t].c > 0 && dist[e[t].v] < mini )
            {
                mini = dist[e[t].v];
                now[i] = t;
            }
            t = e[t].next;
        }
        dist[i] = mini + 1;
        cnt[ dist[i] ]++;
        if( i != st )
        {
            i = e[ pre[i] ].u;
            now_flow = cur[i];
        }
    }
    return tot_flow;
}


int main() {
    int tt;
    scanf("%d", &tt);
    while (tt--) {
         int top=-1;
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        bool ok=1;
        scanf("%d%d", &n, &m);
        s = 0;
        t = n + 1;
        NUM=t+1;
        for (int i = 1; i <= m; i++) {
            int u, v, id;
            scanf("%d%d%d", &u, &v, &id);
            if (id == 0) {
                add(u, v, 1,top);
            }
            in[v]++;
            out[u]++;
        }
        for(int i=1;i<=n;i++)
        {
           if(abs(in[i]-out[i])%2==1)
            {
                ok=0;
                break;
            }
        }
        if(ok==0)
            printf("impossible\n");
        else
        {
            int sum=0;
            for(int i=1;i<=n;i++)
            {
                int tmp=(out[i]-in[i])/2;
                if(tmp<0)
                    add(i,t,-tmp,top);
                else if(tmp>0)
                {
                    add(s,i,tmp,top);
                    sum+=tmp;
                }
            }
            if(sap(s,t)!=sum)
               ok=0;
            if(!ok)
                 printf("impossible\n");
            else
                printf("possible\n");
        }
    }
    return 0;
}

Followed by:

Re:我和你的sap模板一写的差不多，不过我是WA额…… (0) gzhgzh 2011-05-09 20:20:23
Re:为什么isap TLE，dinic却过了，我表示很不能理解，哪位大牛帮忙看下,而且我换了两个sap的板，都是TLE，哎 (30) Sue0610 2011-09-25 21:34:11

Post your reply here:

User ID:
Password:
Title:

Content:

> isap板一：   TLE
> #include<cstdio>
> #include<iostream>
> #include<cstring>
> #include<cstdlib>
> using namespace std;
> 
> #define inf 1000000000
> #define N 1500
> 
> struct node {
>     int to, c, next;
> } edge[1000];
> 
> int head[N], dis[N], cur[N], pre[N], gap[N];
> int in[N], out[N];
> int n, m, NUM;
> int tot;
> int s, t;
> 
> void init() {
>     for (int i = 0; i <NUM; i++)
>     {
>         head[i] = -1;
>         in[i]=0;
>         out[i]=0;
>     }
>     tot =0;
> }
> 
> int sap(int s, int t) {
>     int u;
>     bool flag;
>     int aug = inf, flow = 0;
>     for(int i=0;i<NUM;i++)
>         pre[i]=0;
>     for (int i = 0; i < NUM; i++) {
>         cur[i] = head[i];
>         gap[i] = 0;
>         dis[i] = 0;
>     }
>     gap[s]=NUM;
>     u = pre[s] = s;
>     while (dis[s]<NUM) {
>         flag = 0;
>         for (int &j = cur[u]; j != -1; j = edge[j].next) {
>             int v = edge[j].to;
>             if (edge[j].c > 0 && dis[u] == dis[v] + 1) {
>                 flag = 1;
>                 if (edge[j].c < aug)
>                     aug = edge[j].c;
>                 pre[v] = u;
>                 u = v;
>                 if (u == t) {
>                     flow += aug;
>                     while (u != s) {
>                         u = pre[u];
>                         edge[cur[u]].c -= aug;
>                         edge[cur[u] + 1].c += aug;
>                     }
>                     aug = inf;
>                 }
>                 break;
>             }
>         }
>         if (flag)continue;
>         int mindis = NUM;
>         for (int j = head[u]; j != -1; j = edge[j].next) {
>             int v = edge[j].to;
>             if (edge[j].c > 0 && dis[v] < mindis) {
>                 mindis = dis[v];
>                 cur[u] = j;
>             }
>         }
>         gap[dis[u]]--;
>         if (gap[dis[u]] == 0)
>             return flow;
>         dis[u] = mindis + 1;
>         gap[dis[u]]++;
>         if(pre[u]!=s)
>         u = pre[u];
>     }
>     return flow;
> }
> 
> void add(int from, int to, int w) {
>     edge[tot].to = to;
>     edge[tot].c = w;
>     edge[tot].next = head[from];
>     head[from] = tot++;
>     edge[tot].to = from;
>     edge[tot].c = 0;
>     edge[tot].next = head[to];
>     head[to] = tot++;
> }
> 
> int main() {
>     int tt;
>     scanf("%d", &tt);
>     while (tt--) {
>         bool ok=1;
>         scanf("%d%d", &n, &m);
>         s = 0;
>         t = n + 1;
>         NUM = n + 2;
>         init();
>         for (int i = 1; i <= m; i++) {
>             int u, v, id;
>             scanf("%d%d%d", &u, &v, &id);
>             if (id == 0) {
>                 add(u, v, 1);
>             }
>             in[v]++;
>             out[u]++;
>         }
>         for(int i=1;i<=n;i++)
>         {
>            if(abs(in[i]-out[i])%2==1)
>             {
>                 ok=0;
>                 break;
>             }
>         }
>         if(ok==0)
>             printf("impossible\n");
>         else
>         {
>             int sum=0;
>             for(int i=1;i<=n;i++)
>             {
>                 int tmp=(out[i]-in[i])/2;
>                 if(tmp<0)
>                     add(i,t,-tmp);
>                 else if(tmp>0)
>                 {
>                     add(s,i,tmp);
>                     sum+=tmp;
>                 }
>             }
>             if(sap(s,t)!=sum)
>                ok=0;
>             if(!ok)
>                  printf("impossible\n");
>             else
>                 printf("possible\n");
>         }
>     }
>     return 0;
> }
> 
> 
> 
> 
> ISAP  板2：  TLE。。。。
> #include<cstdio>
> #include<iostream>
> #include<queue>
> #include<cstring>
> #include<cstdlib>
> using namespace std;
> 
> #define inf 1000000000
> #define N 1500
> 
> struct edge{
>     int u,v,c,next;
> }e[10000];
> 
> int head[N],dist[N],now[N],pre[N],cnt[N],cur[N];
> int n,m,NUM;//n表示点数,m表示边数 ,NUM表示总点数
> int s,t,in[N],out[N];
> 
> void add(int u,int v,int va,int &tot)
> {
>     e[++tot].u = u; e[tot].v = v; e[tot].c = va;
>     e[tot].next = head[u]; head[u] = tot;
> 
>     e[++tot].u = v; e[tot].v = u; e[tot].c = 0;
>     e[tot].next = head[v]; head[v] = tot;
> }
> 
> int sap(int st,int ed)
> {
>     int tot_flow;//总流量
>     int i = st,j,t;
>     int now_flow, found, mini;
>     memset( dist, 0, sizeof( dist ) );
>     memset( now, -1, sizeof( now ) );
>     memset( cnt, 0, sizeof( cnt ) );
>     tot_flow = 0; now_flow = inf;
>     cnt[0] = NUM;
>     while( dist[st] < NUM )
>     {
>         cur[i] = now_flow;      found = 0;
>         if( now[i] == -1 ) t = head[i];
>         else t = now[i];
>         while( t != -1 )
>         {
>             j = e[t].v;
>             if(e[t].c > 0 && dist[j] + 1 == dist[i])
>             {
>                 found = 1; now[i] = t;
>                 if( e[t].c < now_flow ) now_flow = e[t].c;
>                 pre[j] = t; i = j;
>                 if(i == ed)
>                 {
>                     tot_flow += now_flow;
>                     while(i != st)
>                     {
>                         e[pre[i]].c -= now_flow;
>                         e[pre[i]^1].c += now_flow;
>                         i = e[pre[i]].u;
>                     }
>                     now_flow = inf;
>                 }
>                 break;
>             }
>             t = e[t].next;
>         }
>         if( found ) continue;
>         if( --cnt[ dist[i] ] == 0) break;
>         mini = n - 1;
>         t = head[i];
>         while( t != -1 )
>         {
>             if( e[t].c > 0 && dist[e[t].v] < mini )
>             {
>                 mini = dist[e[t].v];
>                 now[i] = t;
>             }
>             t = e[t].next;
>         }
>         dist[i] = mini + 1;
>         cnt[ dist[i] ]++;
>         if( i != st )
>         {
>             i = e[ pre[i] ].u;
>             now_flow = cur[i];
>         }
>     }
>     return tot_flow;
> }
> 
> 
> int main() {
>     int tt;
>     scanf("%d", &tt);
>     while (tt--) {
>          int top=-1;
>         memset(head,-1,sizeof(head));
>         memset(in,0,sizeof(in));
>         memset(out,0,sizeof(out));
>         bool ok=1;
>         scanf("%d%d", &n, &m);
>         s = 0;
>         t = n + 1;
>         NUM=t+1;
>         for (int i = 1; i <= m; i++) {
>             int u, v, id;
>             scanf("%d%d%d", &u, &v, &id);
>             if (id == 0) {
>                 add(u, v, 1,top);
>             }
>             in[v]++;
>             out[u]++;
>         }
>         for(int i=1;i<=n;i++)
>         {
>            if(abs(in[i]-out[i])%2==1)
>             {
>                 ok=0;
>                 break;
>             }
>         }
>         if(ok==0)
>             printf("impossible\n");
>         else
>         {
>             int sum=0;
>             for(int i=1;i<=n;i++)
>             {
>                 int tmp=(out[i]-in[i])/2;
>                 if(tmp<0)
>                     add(i,t,-tmp,top);
>                 else if(tmp>0)
>                 {
>                     add(s,i,tmp,top);
>                     sum+=tmp;
>                 }
>             }
>             if(sap(s,t)!=sum)
>                ok=0;
>             if(!ok)
>                  printf("impossible\n");
>             else
>                 printf("possible\n");
>         }
>     }
>     return 0;
> }

Home Page Go Back To top