pku3469 Dual Core CPU

Posted on 08 五月 2009

很久没贴代码了~

写这个题主要是为了练习ISAP(可能更多人叫SAP),ISAP实现起来不算太复杂,只是写的时候大意了把GAP优化写残废了,TLE很久,这也说明GAP是ISAP不可缺的优化~

#include<stdio.h>
#include<string.h>
#define MAX 20003
#define BIG 0x3fffffff
using namespace std;
struct data{
    int x,val,next;
}ln[MAX*30];
int e,n,lev[MAX],st[MAX]={0},pre[MAX],cnt[MAX]={0},bg[MAX],ed[MAX];
void ins(int x,int y,int val)//静态链表插入
{
    if(bg[x]==-1)
        st[x]=bg[x]=e;
    else
        ln[ed[x]].next=e;
    ed[x]=e;
    ln[e].x=y;
    ln[e].next=-1;
    ln[e++].val=val;
}
int isap()
{
    int i,mf,now,dif,t;
    bool flag;
    mf=now=lev[n-1]=0;
    cnt[0]=cnt[2]=1;//预先标号,也可以不用
    lev[0]=2;
    for(i=1;i<n-1;i++)
        lev[i]=1;
    cnt[1]=n-2;
    while(lev[0]<n)
    {
        if(now==n-1)
        {
            t=now;
            dif=BIG;
            while(t!=0)
            {
                t=pre[t];
                if(dif>ln[st[t]].val)
                    dif=ln[st[t]].val;
            }
            mf+=dif;
            while(now!=0)
            {
                now=pre[now];
                ln[st[now]].val-=dif;
                ln[st[now]^1].val+=dif;
            }
        }
        for(flag=true,i=st[now];i!=-1;i=ln[i].next)//st[now]保存的是当前弧
            if(ln[i].val>0&&lev[now]-1==lev[ln[i].x])
            {
                st[now]=i;//更新当前弧
                flag=false;
                break;
            }
            if(flag)
            {
                cnt[lev[now]]--;//cnt[i]表示标号为i的点的个数
                if(cnt[lev[now]]==0)//GAP优化。如果为0,说明出现了间断
                    return mf;
                for(t=n,i=bg[now];i!=-1;i=ln[i].next)
                    if(ln[i].val>0&&t>lev[ln[i].x])
                    {
                        st[now]=i;//重标号时也更新当前弧
                        t=lev[ln[i].x];
                    }
                    lev[now]=t+1;
                    cnt[t+1]++;
                    if(now!=0)
                        now=pre[now];
            }
            else
            {
                pre[ln[i].x]=now;
                now=ln[i].x;
            }
    }
    return mf;
}
int main()
{
    int i,j,m,x,y,val;
    scanf("%d%d",&n,&m);
    memset(bg,-1,sizeof(int)*(n+5));
    n++;
    for(e=0,i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ins(0,i,x);
        ins(i,0,0);
        ins(i,n,y);
        ins(n,i,0);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&val);
        ins(x,y,val);
        ins(y,x,val);
    }
    n++;
    printf("%d\n",isap());
    return 0;
}

2 responses to pku3469 Dual Core CPU

  • SpringBrother 说道:

    膜拜

  • wzc1989 说道:

    膜拜…

  • Leave a Response

    Recent Posts

    Tag Cloud

    ACM Contest Debian DP fucking cet-4 GCJ gdb Hash Linux PKU SAP TCO USACO vim 二分 数论 月赛 有道难题 校赛 测试 百度之星 高精度

    Meta

    Qinz' is proudly powered by WordPress and the SubtleFlux theme.

    Copyright © Qinz'