Author Archives: shadow

hdoj3401 Trade

Posted on by

单调队列优化dp，太菜了做不出来啊，看了题解才ok

dp[i][j]表示第i天有j张股票的最大money

dp[i][j]=max{dp[i-1][j],dp[i-w-1][k]-ap[i]*(j-k),dp[i-w-1][k]+bp[i]*(k-j)}

其中第二个决策表示买入股票，第三个决策表示卖出股票

复杂度太高需需优化

考虑第二个决策：dp[i-w-1][k]-ap[i]*(j-k)=dp[i-w-1][k]+ap[i]*k-ap[i]*j

可见对于dp[i][j]，要找的是dp[i-w-1][k]+ap[i]*k的最大值，因为ap[i]*j在当前阶段和状态确定后是常数。用单调队列将决策那一维优化到O(n)

第三个决策也可以这样考虑

 

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int ap[2010],bp[2010],as[2010],bs[2010],dp[2010][2010],q[2010],num[2010],head,tail;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int main()
{
    int i,j,T;
    int t,maxp,w;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&t,&maxp,&w);
        for(i=1;i<=t;i++) scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
        memset(dp,-inf,sizeof(dp));
        for(i=1;i<=1+w;i++)
        {
            for(j=0;j<=min(maxp,as[i]);j++)
                dp[i][j]=-ap[i]*j;
        }
        for(i=2;i<=t;i++)
        {
            for(j=0;j<=maxp;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
            head=0;tail=-1;
            for(j=0;j<=maxp;j++)
            {
                int bound=max(0,j-as[i]);
                while(head<=tail && num[head]<bound) head++;
                if(head<=tail) dp[i][j]=max(dp[i][j],q[head]-ap[i]*j);
                int tmp=i-w-1<0?0:i-w-1;
                while(head<=tail && dp[tmp][j]+ap[i]*j>=q[tail]) tail--;
                q[++tail]=dp[tmp][j]+ap[i]*j;num[tail]=j;
            }
            head=0;tail=-1;
            for(j=maxp;j>=0;j--)
            {
                int bound=min(maxp,j+bs[i]);
                while(head<=tail && num[head]>bound) head++;
                if(head<=tail) dp[i][j]=max(dp[i][j],q[head]-bp[i]*j);
                int tmp=i-w-1<0?0:i-w-1;
                while(head<=tail && dp[tmp][j]+bp[i]*j>=q[tail]) tail--;
                q[++tail]=dp[tmp][j]+bp[i]*j;num[tail]=j;
            }
        }
        int ans=dp[t][0];
        for(i=1;i<=maxp;i++)
            if(dp[t][i]>ans) ans=dp[t][i];
        printf("%d\n",ans);
    }
    return 0;
}

hdoj4122 Alice’s mooncake shop

Posted on by

哎，一道简单的单调队列比赛时候居然没做出来，很不应该。

假设第i小时定的月饼在第j小时或第k小时制作，那么j和k哪个更优呢？

(i-j)*s+cost[j]<(i-k)*s+cost[k]=====》cost[j]-j*s<cost[k]-k*s

可见，对于第i小时定的月饼用哪个决策与i无关:i choose min{cost[j]-j*s}其中i-T<=j<=i

区间最值，下界非递减，显然是单调队列。。

注意可能有两个及两个以上订单在同一小时。。

 

#include<stdio.h>
#include<string.h>
#include<map>
#include<string>
using namespace std;
typedef __int64 ll;
const int maxm=1e5+10;
map<string,int> mon;
ll num[maxm],cost[maxm];
ll cc[15];
bool is(ll year)
{
    if((year%100 && year%4==0) || (year%400==0)) return 1;
    return 0;
}
void cal(string m,ll date,ll year,ll h,ll r)
{
    int i,j;
    ll tmp=0;
    for(i=2000;i<=year-1;i++) tmp+=(is(i)?366:365);
    for(i=1;i<=mon[m]-1;i++) tmp+=((is(year)&&(i==2))?29:cc[i]);
    tmp+=date-1;tmp=tmp*24+h+1;
    num[tmp]+=r;
    return;
}
ll q[maxm],flag[maxm];
int head,tail;
int main()
{
    int i,j;
    ll n,m;
    mon["Jan"]=1;mon["Feb"]=2;mon["Mar"]=3;mon["Apr"]=4;mon["May"]=5;mon["Jun"]=6;mon["Jul"]=7;mon["Aug"]=8;mon["Sep"]=9;mon["Oct"]=10;mon["Nov"]=11;mon["Dec"]=12;
    cc[1]=31;cc[2]=28;cc[3]=31;cc[4]=30;cc[5]=31;cc[6]=30;cc[7]=31;cc[8]=31;cc[9]=30;cc[10]=31;cc[11]=30;cc[12]=31;
    while(~scanf("%I64d%I64d",&n,&m) && !(n==0 && m==0))
    {
        char month[5];ll date,year,h,r;
        memset(num,0,sizeof(ll)*(m+3));
        for(i=1;i<=n;i++)
        {
            scanf("%s%I64d%I64d%I64d%I64d",month,&date,&year,&h,&r);
            cal((string)month,date,year,h,r);
        }
        ll T,S;
        scanf("%I64d%I64d",&T,&S);
        for(i=1;i<=m;i++) scanf("%I64d",&cost[i]);
        ll ans=0;head=0;tail=-1;
        for(i=1;i<=m;i++)
        {
            while(head<=tail && q[tail]>=cost[i]-i*S) tail--;
            q[++tail]=cost[i]-i*S;flag[tail]=(ll)i;
            while(head<=tail && flag[head]<(ll)(i-T)) head++;
            if(num[i]==0) continue;
            ans+=(q[head]+i*S)*num[i];
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

hdoj3507 Print Article

Posted on by

比较水的斜率优化dp
dp[i]：前i个词的最小cost
s[i]：前i个词的cost之和
w[j,i]:把第j到i个词分在一行的cost
dp[i]=min{dp[j]+w[j+1,i]}(0<=j<=i-1)
其中w[j,i]=(s[i]-s[j])^2+m
dp[i]的是式子展开：dp[i]=min{dp[j]+s[j]^2-2s[i]*s[j]}+s[i]^2+m
k=2s[i]
x=s[j]
y=dp[j]+s[j]^2
点的横坐标非递减，所以可以用单调队列维护凸壳，因为斜率非递减(即决策单调)，所以可以均摊O(1)的求出最优决策是哪个，总复杂度O(n)
//////////////////
关于决策单调的另一种严格证明：
即证明w[i,j]满足四边形不等式：对于i<i’<j’<j,w[i,j']+w[i',j]<=w[i,j]+w[i',j']
(s[j']-s[i])^2+(s[j]-s[i'])^2<=(s[j]-s[i])^2+(s[j']-s[i'])^2
继续化简:-2s[i]s[j']-2s[i']s[j]<=-2s[i]s[j]-2s[i']s[j']
s[i]s[j']+s[i']s[j]>=s[i]s[j]+s[i']s[j']
(s[i']-s[i])(s[j]-s[j'])>=0
因为i<i’<j’<j,(s[i']-s[i])(s[j]-s[j'])>=0显然成立，所以w[i,j]满足四边形不等式，决策单调

#include<stdio.h>
#include<string.h>
int const maxn=5e5+10;
double const eps=1e-8;
typedef struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
}Point;
Point operator -(const Point &a,const Point &b)
{
    return Point(a.x-b.x,a.y-b.y);
}
int s[maxn],dp[maxn];
int n,m;
int head,tail;
Point q[maxn];
int cal(Point a,int k)
{
    return a.y+k*a.x;
}
bool cmp(Point a,Point b,Point c)
{
    Point p1=b-a,p2=c-b;
    return (double)(p1.y/(p1.x+eps))<(double)(p2.y/(p2.x+eps));
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        s[0]=0;dp[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&j);
            s[i]=s[i-1]+j;
        }
        head=tail=0;
        q[0]=Point(0,0);
        for(i=1;i<=n;i++)
        {
            int k=-2*s[i];
            while(head<tail && cal(q[head],k)>=cal(q[head+1],k)) head++;
            dp[i]=cal(q[head],k)+s[i]*s[i]+m;
            Point p(s[i],dp[i]+s[i]*s[i]);
            while(head<tail && !cmp(q[tail-1],q[tail],p)) tail--;
            q[++tail]=p;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

hdoj2829 Lawrence

Posted on by

我擦。。去掉一个语句居然就ac了，纠结n久。这题貌似不用斜率有优化，用四边形不等式优化也行。具体明天再说。。
第一道状态是二维，决策一维的斜率优化dp，其实和状态一维的差不多，无非多了层外层循环。每个阶段都用一下单调队列。。

#include<stdio.h>
#include<string.h>
const int maxn=1010;
const int inf=0x3f3f3f3f;
typedef struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y)
    {
        x=_x;y=_y;
    }
}Point;
Point operator -(const Point &a,const Point &b)
{
    return Point(a.x-b.x,a.y-b.y);
}
int cal(Point a,int k)
{
    return a.y+k*a.x;
}
bool cmp(Point a,Point b,Point c)
{
    Point p1=b-a,p2=c-b;
    return (p1.y*1.0/p1.x)<(p2.y*1.0/p2.x);
}
Point q[maxn];
int s[maxn],c[maxn],dp[maxn][maxn];
int head,tail,n,m;
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        c[0]=s[0]=0;
        for(i=1;i<=n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            s[i]=s[i-1]+tmp;
            c[i]=c[i-1]+tmp*s[i];
        }
        memset(dp,0,sizeof(dp));
        for(j=1;j<=n;j++) dp[1][j]=0;
        for(i=1;i<=n;i++)
            dp[i][1]=s[i]*s[i]-c[i];
        for(j=2;j<=m+1;j++)
        {
            head=tail=0;
            q[0]=Point(s[1],dp[1][j-1]+c[1]);
            for(i=2;i<=n;i++)
            {
                //if(i<j+1) continue;
                int k=-s[i];
                while(head<tail && cal(q[head],k)>=cal(q[head+1],k)) head++;
                dp[i][j]=cal(q[head],k)+s[i]*s[i-1]-c[i-1];
                Point p(s[i],dp[i][j-1]+c[i]);
                while(head<tail && !cmp(q[tail-1],q[tail],p)) tail--;
                q[++tail]=p;
            }
        }
        printf("%d\n",dp[n][m+1]);



    }
    return 0;
}

bzoj1010 玩具装箱toy

Posted on by

斜率优化dp第一题，纠结了n久。。最后输出改成%I64d就PE，要%lld才能ac，而且把输入也改成%lld比%I64d快看了200MS。。
终于大致清楚了斜率优化dp，记下几点：
(1)求最大值，维护上凸壳；求最小值，维护下凸壳；
(2)当点的横坐标单调，且斜率单调时，此时决策是单调的（即满足四边形不等式），可以用单调队列从前往后找最优决策(怎么找？只有最优决策点的值比两侧都要优，注意只有二字)，找到之后前面的都是无用决策了，插入点的时候维护队列凸壳。
(3)如果点的横坐标是单调的，而斜率不单调，这时候决策是不单调的，但是可以发现最优决策点与两侧相邻点的斜率分别是k1,k2(k1 那么显然此时直线簇的斜率k满足k1 (4)当点的横坐标不单调且直线斜率不单调的时候。如果用单调队列，那么求最优决策点还是可以二分。当插入一个点的时候，我们首先根据它的横坐标二分出它的插入位置，然后维护凸壳，但是由于可能插入在队列中间，两边都要删点，复杂度过高。
正确做法是用平衡树维护动态凸壳。（我擦，说着简单，写着蛋疼无比）(这种情况细节还不太会，有待学习)

#include<stdio.h>
typedef long long ll;
const int maxn=5e4+10;
typedef struct Node{
    ll x,y;
}Node;
Node q[maxn];
int n;
ll s[maxn],L,dp[maxn];
int head,tail;
ll cal(ll x,ll y,ll k)
{
    return y-2*k*x;
}
bool xielv(Node a,Node b,Node c)
{
    ll x1=a.x,y1=a.y,x2=b.x,y2=b.y,x3=c.x,y3=c.y;
    return (y2-y1)*(x3-x2)<(y3-y2)*(x2-x1);
}
int main()
{
    int i,j;
    while(~scanf("%d%lld",&n,&L))
    {
        s[0]=0;dp[0]=0;
        ll tmp;
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&tmp);s[i]=s[i-1]+tmp;
        }
        head=tail=0;q[0].x=0;q[0].y=0;
        for(i=1;i<=n;i++)
        {
            ll k=s[i]+i-1-L,x,y;
            while(head<tail && cal(q[head].x,q[head].y,k)>=cal(q[head+1].x,q[head+1].y,k))
                head++;
            dp[i]=cal(q[head].x,q[head].y,k)+k*k;
            x=s[i]+i;y=dp[i]+x*x;
            Node tt;tt.x=x;tt.y=y;
            while(head<tail && !xielv(q[tail-1],q[tail],tt))
                tail--;
            q[++tail]=tt;
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}

hdoj2993 MAX Average Problem

Posted on by

这篇论文里的例二：http://www.docin.com/p-47950655.html
分析不写了，论文里写的很清楚，虽说不是斜率优化dp，但应该也可以算是斜率优化dp的入门题了。。记得加外挂哦~~

#include<stdio.h>
#include<string.h>
const int maxn=1e5+10;
int a[maxn],s[maxn];
int q[maxn],head,tail;
double cal(int i,int j)
{
    return (double)(s[i]-s[j])/(double)(i-j);
}
void scan(int &num)//对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-');
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');//去负号后空格
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg) num=0-num;
}
int main()
{
    int i,j;
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        s[0]=0;
        for(i=1;i<=n;i++)
        {
            scan(a[i]);
            s[i]=s[i-1]+a[i];
        }
        head=tail=0;
        q[0]=0;
        double maxx=0;
        for(i=k;i<=n;i++)
        {
            while(head<tail && cal(i,q[head])<=cal(i,q[head+1]))
                head++;
            double tmp=cal(i,q[head]);
            if(tmp>maxx) maxx=tmp;
            while(head<tail && cal(q[tail],q[tail-1])>=cal(i-k+1,q[tail]))
                tail--;
            q[++tail]=i-k+1;
        }
        printf("%.2f\n",maxx);
    }
    return 0;
}

poj3017 Cut the Sequence

Posted on by

单调队列+treap
会爆栈，要c++扩栈。
题意：给出n个数(n<=10^5),给出m，要求将数列分成连续的若干段，使得每段之和<=m，且每段中的最大值的和最小，求这个最小的和
分析：
很容易得到：dp[i]=min{dp[j]+max{a[j+1……i]}|bound[i]<=j<=i-1},其中bound[i]是使得sigma(a[j+1]……a[i])<=m的最大下标，可以二分得到。
状态数O(n),转移O(n)，显然要优化。
由于bound[i]是随着i的增大单调不降的，而且一个点j要成为i的最优决策首先必须满足a[j]比a[j+1……i]都要大(这点还不明白)。那么我们可以用单调队列维护。
现在对于确定的决策j，我们可以O(1)时间知道a[j+1]~a[i]的最大值(若q[p]=a[j]，那么max{a[j+1]~a[i]}=q[p+1]，q[p+1]存在的前提下)，但是对于状态i，当前单调队列的队首元素的原始下标不一定就是最优决策值，所以我们要找到一种数据结构动态的维护dp[j]+max{a[j+1]~a[i]},其中a[j]是当前单调队列中的元素。那么显然当状态转移的时候需要对这种数据结构插入、删除、求最小值。显然这种数据结构应当是平衡树为好。
思路还是很清晰的，但是要注意细节，队列中的元素个数要时刻清晰，插入删除了哪些决策下的答案要清楚。还有就是对于决策是bound这种情况，要特判。因为我代码里面的单调队列都是从bound+1开始的元素。

#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
typedef long long ll;
const int maxn=1e6+10;
typedef struct Node{
    Node *ch[2];
    int r;
    ll v;
    int s;
    int cc;
    Node(){}
    Node(int v):v(v) {ch[0]=ch[1]=NULL;r=rand();s=1;cc=1;}
    void init(ll _v)
    {
        v=_v;
        ch[0]=ch[1]=NULL;r=rand()%1000007;s=1;cc=1;
        return;
    }
    bool operator <(const Node& rhs) const
    {
        return r<rhs.r;
    }
    int cmp(ll x) const
    {
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=cc;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
}Node;
Node pool[maxn];
int cnt;
void rotate(Node* &o,int d)
{
    Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
    o->maintain();k->maintain();o=k;
    return;
}
void insert(Node* &o,ll x)
{
    if(o==NULL)
    {
        o=&pool[cnt++];
        o->init(x);
    }
    else
    {
        int d=o->cmp(x);
        if(d==-1) o->cc++;
        else
        {
            insert(o->ch[d],x);
            if(*(o)<*(o->ch[d])) rotate(o,d^1);
        }
    }
    o->maintain();
    return;
}
void remove(Node* &o,ll x)
{
    int d=o->cmp(x);
    if(d==-1 && o->cc>1)
        o->cc--;
    else if(d==-1)
    {
        if(o->ch[0]!=NULL && o->ch[1]!=NULL)
        {
            int d2=(*(o->ch[1])<*(o->ch[0])?1:0);
            rotate(o,d2);remove(o->ch[d2],x);
        }
        else
        {
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
        }
    }
    else remove(o->ch[d],x);
    if(o!=NULL) o->maintain();
}
ll kth2(Node* o,int k)//第k大数
{
    if(o==NULL || k<=0 || k>o->s) return 0;//k不合法时返回0
    int s=(o->ch[1]==NULL?0:o->ch[1]->s);
    if(s+1<=k && k<=s+o->cc) return o->v;
    else if(k<=s) return kth2(o->ch[1],k);
    else return kth2(o->ch[0],k-s-o->cc);
}
ll a[maxn],s[maxn];
int head,tail,num[maxn];
ll q[maxn];
ll dp[maxn];
int n;
ll m;
int bsearch(int i,int l,int r)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(s[i]-s[mid]<=m) r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main()
{
    srand((unsigned int)time(NULL));
    int i,j;
    scanf("%d%lld",&n,&m);
        bool flag=1;
        cnt=0;s[0]=0;dp[0]=0;
        Node* root=NULL;
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            s[i]=s[i-1]+a[i];
            if(a[i]>m) flag=0;
        }
        if(flag==0)
        {
            printf("-1\n");return 0;
        }
        head=tail=0;
        q[tail]=0;num[0]=0;
        for(i=1;i<=n;i++)
        {
            int bound=bsearch(i,0,i-1);bound++;
            while(head<=tail && num[head]<bound)
            {
                if(tail>head)
                {
                    remove(root,dp[num[head]]+q[head+1]);
                }
                head++;
            }
            while(head<=tail && a[i]>=q[tail])
            {
                if(tail-1>=head) remove(root,dp[num[tail-1]]+q[tail]);
                tail--;
            }
            q[++tail]=a[i];num[tail]=i;
            int tmp=q[head];
            if(head==tail)
            {
                dp[i]=dp[bound-1]+tmp;
                continue;
            }
            insert(root,dp[num[tail-1]]+a[i]);
            dp[i]=kth2(root,root->s);
            if(dp[bound-1]+tmp<dp[i]) dp[i]=dp[bound-1]+tmp;
        }
        printf("%lld\n",dp[n]);
    return 0;
}

hdoj4557 非诚勿扰

Posted on by

居然0ms，数据略水。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
const int maxn=1e3+10;
typedef struct Node{
    Node *ch[2];
    char name[1004][17];
    int head,tail;
    int r;
    int v;
    int s;
    int cc;
    Node(){}
    Node(int v):v(v) {ch[0]=ch[1]=NULL;r=rand();s=1;cc=1;}
    void init(char str[],int _v)
    {
        v=_v;head=tail=0;
        strcpy(name[head],str);
        ch[0]=ch[1]=NULL;r=rand()%10007;s=1;cc=1;
        return;
    }
    bool operator <(const Node& rhs) const
    {
        return r<rhs.r;
    }
    int cmp(int x) const
    {
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=cc;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
}Node;
Node*root=NULL;
Node pool[maxn];
int cnt;
void rotate(Node* &o,int d)
{
    Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
    o->maintain();k->maintain();o=k;
    return;
}
void insert(Node* &o,char s[],int x)
{
    if(o==NULL)
    {
        o=&pool[cnt++];
        o->init(s,x);
    }
    else
    {
        int d=o->cmp(x);
        if(d==-1)
        {
            o->cc++;
            int head=o->head,tail=o->tail;
            strcpy(o->name[++tail],s);
            o->tail++;
        }
        else
        {
            insert(o->ch[d],s,x);
            if(*(o)<*(o->ch[d])) rotate(o,d^1);
        }
    }
    o->maintain();
    return;
}
void remove(Node* &o,int x)
{
    int d=o->cmp(x);
    if(d==-1 && o->cc>1)
    {
        o->cc--;
    }
    else if(d==-1)
    {
        if(o->ch[0]!=NULL && o->ch[1]!=NULL)
        {
            int d2=(*(o->ch[1])<*(o->ch[0])?1:0);
            rotate(o,d2);remove(o->ch[d2],x);
        }
        else
        {
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
        }
    }
    else remove(o->ch[d],x);
    if(o!=NULL) o->maintain();
}
int kth2(Node* o,int k)//第k大数
{
    if(o==NULL || k<=0 || k>o->s) return 0;//k不合法时返回0
    int s=(o->ch[1]==NULL?0:o->ch[1]->s);
    if(s+1<=k && k<=s+o->cc)
    {
        printf("%s\n",o->name[o->head]);
        o->head++;
        remove(root,o->v);
    }
    else if(k<=s) return kth2(o->ch[1],k);
    else return kth2(o->ch[0],k-s-o->cc);
}
int rank2(Node* o,int x,bool &flag)
{
    int cnt=0;
    while(o!=NULL)
    {
        int d=o->cmp(x);
        if(d==-1)
        {
            if(o->ch[1]!=NULL) cnt+=o->ch[1]->s;
            return cnt+o->cc;
        }
        if(d==0)
        {
            cnt+=o->cc;
            if(o->ch[1]!=NULL) cnt+=(o->ch[1]->s);
            o=o->ch[0];
        }
        else o=o->ch[1];
    }
    flag=0;
    return cnt+1;
}
int main()
{
    srand((unsigned int)time(NULL));
    int T,cases=0;
    int i,j,tmp;
    scanf("%d",&T);
    while(T--)
    {
        int n;char s[10];
        cnt=0;root=NULL;
        scanf("%d",&n);
        printf("Case #%d:\n",++cases);
        for(i=1;i<=n;i++)
        {
            scanf("%s",s);
            if(strcmp(s,"Add")==0)
            {
                scanf("%s %d",s,&tmp);
                insert(root,s,tmp);
                printf("%d\n",root->s);
            }
            else
            {
                scanf("%d",&tmp);
                bool flag=1;
                int ans=rank2(root,tmp,flag);
                if(ans==1 && !flag) printf("WAIT...\n");
                else
                {
                    if(flag) kth2(root,ans);
                    else kth2(root,ans-1);
                }
            }
        }
    }
    return 0;
}

poj1442 Black Box

Posted on by

treap入门题

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
typedef struct Node{
    Node *ch[2];
    int r;
    int v;
    int s;
    int cc;
    Node(){}
    void init(int _v)
    {
        v = _v;
        ch[0] = ch[1] = NULL;r = rand()%100007;s=1;cc=1;
    }
    bool operator <(const Node& rhs) const
    {
        return r<rhs.r;
    }
    int cmp(int x) const
    {
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=cc;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
}Node;
Node pool[4000000];
int cnt;
void rotate(Node* &o,int d)
{
    Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
    o->maintain();k->maintain();o=k;
    return;
}
void insert(Node* &o,int x)
{
    if(o==NULL) {o=&pool[cnt++];o->init(x);}
    else
    {
        int d=o->cmp(x);
        if(d==-1) o->cc++;
        else
        {
            insert(o->ch[d],x);
            if(*(o)<*(o->ch[d])) rotate(o,d^1);
        }
    }
    o->maintain();
    return;
}
int kth2(Node* o,int k)//第k大数
{
    if(o==NULL || k<=0 || k>o->s) return 0;//k不合法时返回0
    int s=(o->ch[1]==NULL?0:o->ch[1]->s);
    if(s+1<=k && k<=s+o->cc) return o->v;
    else if(k<=s) return kth2(o->ch[1],k);
    else return kth2(o->ch[0],k-s-o->cc);
}
int a[30010],b[30010];
int main()
{
    int i,j;
    int n,m;
    srand((unsigned int)time(NULL));
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=m;i++) scanf("%d",&b[i]);
        cnt=0;
        int k=0;Node *root=NULL;
        int pre=1;
        for(i=1;i<=m;i++)
        {
            for(j=pre;j<=b[i];j++)
                insert(root,a[j]);
            pre=b[i]+1;
            k++;
            printf("%d\n",kth2(root,b[i]-k+1));

        }
    }
    return 0;
}

单调队列

Posted on by

fzoj1894 志愿者选拔
裸的单调队列，注意出队的时候，只有当当前删除的人的下标等于优先队列中队首的人的下标，才出队

#include<stdio.h>
#include<string.h>
char s[10];
int q[1000000+10],head,tail;
int num[1000000+10];
int main()
{
    int i,j,t,val;
    scanf("%d",&t);
    while(t--)
    {
        head=0;tail=-1;
        int index=0,index2=0;
        scanf("%s",s);
        while(~scanf("%s",s) && strcmp(s,"END")!=0)
        {
            if(s[0]=='C')
            {
                index++;
                scanf("%s %d",s,&val);
                while(tail>=head && val>=q[tail]) tail--;
                q[++tail]=val;num[tail]=index;
            }
            else if(s[0]=='G')
            {
                index2++;
                if(num[head]==index2) head++;
            }
            else
            {
                if(head>tail) puts("-1");
                else printf("%d\n",q[head]);
            }
        }
    }
    return 0;
}

poj2823 Sliding Window
经典的单调队列应用
f[x]=opt{a[i]|bound[x]<=i<=x}

#include<stdio.h>
#include<string.h>
#define maxn 1000000+10
int a[maxn],q[maxn];
int num[maxn];
int head,tail;
int main()
{
    int i,j;
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        head=0;tail=-1;
        for(i=1;i<=(k<=n?k:n);i++)
        {
            while(head<=tail && q[tail]>=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
        }
        printf("%d",q[head]);
        for(i=k+1;i<=n;i++)
        {
            while(head<=tail && q[tail]>=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
            while(num[head]<i-k+1) head++;
            printf(" %d",q[head]);
        }
        printf("\n");

        head=0;tail=-1;
        for(i=1;i<=(k<=n?k:n);i++)
        {
            while(head<=tail && q[tail]<=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
        }
        printf("%d",q[head]);
        for(i=k+1;i<=n;i++)
        {
            while(head<=tail && q[tail]<=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
            while(num[head]<i-k+1) head++;
            printf(" %d",q[head]);
        }
        printf("\n");



    }
    return 0;
}

hdoj3415 Max Sum of Max-K-sub-sequence
经典单调队列
dp[i]=sum[i]-sum[j]=sum[i]-min{sum[j]|i-k<=j<=i-1}
加输入外挂才能过，，不然TLE。。囧~

#include<stdio.h>
#include<string.h>
#define maxn 200000+10
int a[maxn],q[maxn],head,tail;
int num[maxn];
int path[maxn];
void scan(int &num)//对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-');
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');//去负号后空格
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg) num=0-num;
}

int main()
{
    int i,j;
    int t,n,k;
    scan(t);
    while(t--)
    {
        scan(n);scan(k);
        head=0;tail=-1;
        a[0]=0;
        for(i=1;i<=n;i++) {scan(a[i]);a[i+n]=a[i];}
        for(i=1;i<=2*n;i++) a[i]+=a[i-1];
        q[++tail]=a[0];num[tail]=0;
        for(i=1;i<=2*n;i++)
        {
            while(num[head]<i-k) head++;
            path[i]=num[head]+1;
            while(head<=tail && a[i]<q[tail]) tail--;
            q[++tail]=a[i];num[tail]=i;
        }
        int ans=-1000000000,begin=maxn,end,len;
        for(i=1;i<=2*n;i++)
        {
            if(a[i]-a[path[i]-1]>ans)
            {
                ans=a[i]-a[path[i]-1];len=i-path[i]+1;
                begin=path[i]>n?path[i]-n:path[i];
                end=i>n?i-n:i;
            }
            else if(a[i]-a[path[i]-1]==ans)
            {
                if((path[i]>n?path[i]-n:path[i])<begin)
                {
                    len=i-path[i]+1;
                    begin=path[i]>n?path[i]-n:path[i];
                    end=i>n?i-n:i;
                }
                else if((path[i]>n?path[i]-n:path[i])==begin && i-path[i]+1<len)
                {
                    len=i-path[i]+1;
                    begin=path[i]>n?path[i]-n:path[i];
                    end=i>n?i-n:i;
                }
            }
        }
        printf("%d %d %d\n",ans,begin,end);


    }
    return 0;
}

钢之炼金术士FA的五首OP

Posted on by

终于看完钢炼FA了，有点不舍，动漫里确实塑造了一个全新的很棒的世界观啊
OP1 again
这首很怀旧

OP2 ホログラム
这首最喜欢，有一种给人带来动力的感觉，歌词也很好

OP3 ゴールデンタイムラバー
这首诗最燃的一首，听完有没有充满力量呢

OP4 Period
比较温暖柔和的曲调

OP5 レイン
故事要终了的旋律

ED5 RAY OF LIGHT
这首ED也不错

上下界网络流的一些理解

Posted on by

周源论文中的二分法求解虽用途广，但效率不高，容易被卡时间，所以非二分的扩流法和缩流法比较好
注意点：设下界为low，上界为high，残量网络中该边残余容量c，则最后该边的流量=low+(high-low-c)=high-c;亦即上界-残量
1.有源汇上下界最大流
（1）加弧，转变成无源汇可行流问题
（2）添加附加源汇ss、tt。求出是否存在可行流。
（3）现在已经有了可行流，去掉。从s到t求最大流，（网上说要去掉附加源汇ss,tt，其实我感觉不用去，因为ss和tt间没边，所以必要弧不可能退流，个人理解，正确性有待检验）
2.有源汇上下界最小流
（1）和最大流一样构造附加网络（但不添加）
（2）求ss到tt的最大流ans1
（3）加，求ss到tt的最大流ans2
（4）如果ans1+ans2等于附加网络的满流流量(以ss、tt为源汇)，则有解，且的流量就是最小流，否则无解
这个方法无bug，但我还没完全理解
还有一个有bug的方法：和求解最大流基本一样，只是最后一步是从t到s求最大流，也就是缩流，但是存在bug：可能出现缩流的量比可行流还大，也就是最终最小流为负，其实这种情况意味着原网络中间出现环流，也就是源点s不必产生流量也能符合要求，此时最小流为0

上下界网络流专题

Posted on by

各种流的一句话总结，相当经典：http://blog.csdn.net/pouy94/article/details/6628521
zoj 2314 Reactor Cooling
无源汇可行流

#include<stdio.h>
#include<string.h>
#define maxn 210
#define maxe 100000+10
#define inf 0x3f3f3f3f
typedef struct Edge{
    int c;
    int to;
    int next;
    int num;
}Edge;
Edge edge[maxe];
int head[maxn];
int s,t,cnt,n,m;
int c[maxn],d[maxn];
int in[maxn],out[maxn],sum;
int ans[maxe],initc[maxe],initb[maxe];
inline int min(int a,int b) {return a<b?a:b;}
void add(int u,int v,int c,int num)
{
    edge[cnt].num=num;edge[cnt].c=c;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].num=num;edge[cnt].c=0;edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
void init()
{
    sum=cnt=0;memset(head,-1,sizeof(int)*(n+10));
    memset(in,0,sizeof(int)*(n+10));
    memset(out,0,sizeof(int)*(n+10));
    return;
}
int dfs(int cur,int flow)
{
    if(cur==t) return flow;
    int res=0;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to,c=edge[i].c;
        if(c && d[cur]==d[v]+1)
        {
            int delta=dfs(v,min(flow,c));
            edge[i].c-=delta;edge[i^1].c+=delta;
            flow-=delta;res+=delta;
            if(!flow) break;
        }
    }
    if(!res)
    {
        c[d[cur]]--;
        if(!c[d[cur]]) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(c,0,sizeof(int)*(n+10));
    memset(d,0,sizeof(int)*(n+10));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
void build()
{
    int i,cc=m;
    for(i=1;i<=n;i++)
    {
        int M=in[i]-out[i];
        if(M>=0) {add(s,i,M,++cc);sum+=M;}
        else add(i,t,-M,++cc);
    }
    n=t+1;
}
bool solve()
{
    build();
    if(sap()==sum) return 1;
    return 0;
}
int main()
{
    int i,j,T;
    int u,v,b,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        s=0;t=n+1;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&b,&c);
            in[v]+=b;out[u]+=b;
            add(u,v,c-b,i);
            initc[i]=c;initb[i]=b;
        }
        int cc=cnt;
        if(!solve()) {printf("NO\n");if(T!=0) printf("\n");}
        else
        {
            printf("YES\n");
            for(i=0;i<=cc-1;i+=2)
            {
                ans[edge[i].num]=initc[edge[i].num]-edge[i].c;
            }
            for(i=1;i<=m;i++) printf("%d\n",ans[i]);
            if(T!=0) printf("\n");
        }




    }

    return 0;
}

poj2396 && zoj1994 Budget
无源汇可行流

#include<stdio.h>
#include<string.h>
#define maxn 300
#define maxe 100000
#define inf 0x3f3f3f3f
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int cap[maxe];
int head[maxn];
int s,t,cnt,n,m;
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int in[maxn],out[maxn],sum;
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
void add(int u,int v,int c)
{
    edge[cnt].c=c;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].c=0;edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
void init()
{
    sum=cnt=0;memset(head,-1,sizeof(head));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=min(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
int low[210][30],high[210][30];
int row[210],col[30],all;
void cal(int r,int c,char type,int sum)
{
    int i,j;
    if(r==0 && c==0)
    {
        if(type=='<')
        {
            for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                    high[i][j]=min(high[i][j],sum-1);
        }
        else if(type=='>')
        {
            for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                    low[i][j]=max(low[i][j],sum+1);
        }
        else
        {
            for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                {
                    high[i][j]=min(high[i][j],sum);
                    low[i][j]=max(low[i][j],sum);
                }
        }
    }
    else if(r==0 && c!=0)
    {
        if(type=='<')
            for(i=1;i<=n;i++) high[i]1=min(high[i]1,sum-1);
        else if(type=='>')
            for(i=1;i<=n;i++) low[i]1=max(low[i]1,sum+1);
        else
        for(i=1;i<=n;i++) {high[i]1=min(high[i]1,sum);low[i]1=max(low[i]1,sum);}
    }
    else if(c==0 && r!=0)
    {
        if(type=='<')
            for(i=1;i<=m;i++) high[r][i]=min(high[r][i],sum-1);
        else if(type=='>')
            for(i=1;i<=m;i++) low[r][i]=max(low[r][i],sum+1);
        else
        for(i=1;i<=m;i++) {high[r][i]=min(high[r][i],sum);low[r][i]=max(low[r][i],sum);}
    }
    else
    {
        if(type=='<') high[r]1=min(high[r]1,sum-1);
        else if(type=='>')low[r]1=max(low[r]1,sum+1);
        else { high[r]1=min(high[r]1,sum);low[r]1=max(low[r]1,sum); }
    }
    return;
}
int main()
{
    int i,j,T;
    int u,v,b,c,tmp;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(low,0,sizeof(low));
        memset(high,inf,sizeof(high));
        memset(row,0,sizeof(row));memset(col,0,sizeof(col));
        init();
        s=0;t=n+m+1;int ss=t+1;int tt=ss+1;
        all=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&row[i]);all+=row[i];
            add(s,i,row[i]);
        }
        for(i=n+1;i<=n+m;i++)
        {
            scanf("%d",&col[i-n]);
            add(i,t,col[i-n]);
        }
        add(t,s,0);in[s]+=all;out[t]+=all;
        int cn;char str[5];
        bool flag=1;
        scanf("%d",&cn);
        while(cn--)
        {
            scanf("%d%d%s%d",&i,&j,str,&tmp);
            cal(i,j,str[0],tmp);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                if(low[i][j]>high[i][j]) {flag=0;break;}
            if(!flag) break;
        }
        if(!flag) {printf("IMPOSSIBLE\n");if(T!=0) printf("\n");continue;}
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                cap[cnt]=high[i][j];add(i,n+j,high[i][j]-low[i][j]);
                in[n+j]+=low[i][j];out[i]+=low[i][j];
            }
        for(i=s;i<=t;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) {add(ss,i,M);sum+=M;}
            else add(i,tt,-M);
        }
        int ans=isap(ss,tt,tt+1);
        if(ans!=sum) {printf("IMPOSSIBLE\n");if(T!=0) printf("\n");continue;}
        for(i=1;i<=n;i++)
        {
            for(j=head[i];j!=-1;j=edge[j].next)
            {
                if(j&1) continue;
                low[i][edge[j].to-n]=cap[j]-edge[j].c;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                printf("%d",low[i][j]);
                if(j!=m) printf(" ");
            }
            printf("\n");
        }
        if(T!=0) printf("\n");
    }
    return 0;
}

poj2594 Treasure Exploration
解法一：DAG最小可相交路径覆盖：先求佛洛依德传递闭包，再求不相交最小路径覆盖

#include<stdio.h>
#include<string.h>
#define maxn 1000+10
#define maxe 250000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m,cnt;
int match[maxn];
bool use[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        memset(use,0,sizeof(bool)*(2*n+10));
        if(match[i]) continue;
        if(dfs(i)) ans++;
    }
    return ans;
}
bool map[510][510];
int main()
{
    int i,j,k;
    int u,v;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++) map[i][j]=(i==j);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            map[u][v]=1;
        }
        for(k=1;k<=n;k++)
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                {
                    map[i][j]|=(map[i][k] && map[k][j]);
                }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i==j) continue;
                if(map[i][j]) add(i,n+j);
            }
        printf("%d\n",n-xyl());
    }


    return 0;
}

hdoj3157 Crazy Circuits
上下界最小流

#include<stdio.h>
#include<string.h>
#include <queue>
#define maxn 60
#define maxe 610
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Edge
{
    int c,from,to,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int cnt;
int s,t;
inline void add(int u,int v,int c)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=min(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
void scan(int &num)//对G++使用
{
    char in;
    while(((in=getchar()) > '9' || in<'0') && in!='-' && in!='+');
    if(in=='-' || in=='+')
    {
        if(in=='-') num=t;
        if(in=='+') num=s;
        return;
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    return;
}
int in[maxn],out[maxn];
int main()
{
    int i,j;
    int n,m;
    int u,v,c;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));memset(out,0,sizeof(out));
        s=0;t=n+1;
        for(i=1;i<=m;i++)
        {
            scan(u);scan(v);scan(c);
            out[u]+=c;in[v]+=c;
            add(u,v,inf-c);
        }
        int ss=t+1,tt=ss+1,sum=0;
        for(i=0;i<=t;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) {add(ss,i,M);sum+=M;}
            else add(i,tt,-M);
        }
        int ans1=isap(ss,tt,tt+1);
        add(t,s,inf);
        int ans2=isap(ss,tt,tt+1);
        if(ans1+ans2!=sum) printf("impossible\n");
        else printf("%d\n",edge[cnt-1].c);
    }
    return 0;
}

SGU176 Flow construction
上下界最小流

#include<stdio.h>
#include<string.h>
#include <queue>
#define maxn 110
#define maxe 50010
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Edge
{
    int from,to,c;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int cnt,n,m,s,t;
int in[maxn],out[maxn];
int low[maxe];
inline void add(int u,int v,int c)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=1;i<=n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=min(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
int main()
{
    int i,j;
    int u,v,c,flag;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));memset(out,0,sizeof(out));
        memset(low,0,sizeof(low));
        s=1;t=n;
        int ss=n+1,tt=ss+1;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&c,&flag);
            if(flag) {in[v]+=c;out[u]+=c;low[cnt]=c;add(u,v,0);}
            else add(u,v,c);
        }
        int sum=0;
        for(i=1;i<=n;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) {add(ss,i,M);sum+=M;}
            else add(i,tt,-M);
        }
        int ans1=isap(ss,tt,tt);
        add(t,s,inf);
        int ans2=isap(ss,tt,tt);
        if(ans1+ans2!=sum) {printf("Impossible\n");continue;}
        printf("%d\n",edge[cnt-1].c);
        bool p=1;
        for(i=0;i<=2*m-2;i+=2)
        {
            if(!p) printf(" ");
            else p=0;
            printf("%d",low[i]+edge[i^1].c);
        }
        printf("\n");


    }
    return 0;
}

zoj 3229 Shoot the Bullet
裸的上下界最大流水题，数组开小了，折磨了好几天，按题意明明点数组400够用的。。

#include<stdio.h>
#include<string.h>
#define maxn 4000
#define maxe 368000
#define inf 1000000000
typedef struct Edge
{
    int from,to,c,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int cnt;
inline int minx(int a,int b){return a<b?a:b;}
void add(int u,int v,int c)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=minx(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
int low[maxe],in[maxn],out[maxn];
int dd[maxn];
int main()
{
    int i,j;
    int n,m,tmp;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));memset(out,0,sizeof(out));
        int s=0,t=n+m+1,ss=t+1,tt=ss+1;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&tmp);
            add(n+i,t,inf-tmp);
            in[t]+=tmp;out[n+i]+=tmp;
        }
        int start=cnt,end;
        for(i=1;i<=n;i++)
        {
            int cn,D;
            scanf("%d%d",&cn,&D);dd[i]=D;
            for(j=1;j<=cn;j++)
            {
                int tar,high,l;
                scanf("%d%d%d",&tar,&l,&high);
                low[cnt]=l;
                add(i,n+tar+1,high-l);
                out[i]+=l;in[n+tar+1]+=l;
            }
        }
        end=cnt;
        for(i=1;i<=n;i++) add(s,i,dd[i]);
        int sum=0;
        for(i=s;i<=t;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) add(ss,i,M),sum+=M;
            else add(i,tt,-M);
        }
        add(t,s,inf);
        int ans1=isap(ss,tt,tt+1);
        if(ans1!=sum) {printf("-1\n\n");continue;}
        edge[cnt-1].c=edge[cnt-2].c=0;
        int ans2=isap(s,t,tt+1);
        printf("%d\n",ans1+ans2);
        for(i=start;i<=end-1;i++)
        {
            if(i&1) continue;
            int v=edge[i].to;
            if(n+1<=v && v<=n+m)
                printf("%d\n",low[i]+edge[i^1].c);

        }
        printf("\n");
    }

    return 0;
}