线性规划与网络流之2 最大权闭合图

题目:http://www.byvoid.com/blog/lpf24-solution/

分析

按照题意,可以构建一个二分图,然后我们可以发现这是一个依赖关系的最大权取值问题。所以直接套用《最小割模型在信息学竞赛中的应用》里的最大权闭合图模型解决。

code:

#include #define E 1000001
#define N 1001
#define Maxnum 1000000000
int m,n,x[E],y[E],next[E],c[E],op[E],ls[N],d[N],fa[N],num[N],cur[N],vs,vt,e=0,s=0,flow=0;

void add(int X,int Y,int C){
     e++;
     x[e]=X; y[e]=Y; c[e]=C; next[e]=ls[X]; ls[X]=e; op[e]=e+1;
     e++;
     x[e]=Y; y[e]=X; c[e]=0; next[e]=ls[Y]; ls[Y]=e; op[e]=e-1;
}

void init(){
     scanf("%d%d",&m,&n);
     vs=0; vt=m+n+1;
     char ch;
     for (int i=1;i<=m;i++){
         int t;
         scanf("%d",&t);
         s+=t;
         add(vs,i,t);
         while (scanf("%c",&ch)!=EOF && ch!=’n’){
               scanf("%d",&t);
               add(i,m+t,Maxnum);
         }
     }
     for (int i=1;i<=n;i++){
         int t;
         scanf("%d",&t);
         add(m+i,vt,t);
     }
}

void relabel(int k){
     int min=vt,i=ls[k];
     cur[k]=ls[k];
     while (i>0){
       if (c[i]>0 && d[y[i]]       i=next[i];
     }
     d[k]=min+1;
}

void change(){
     int i=vt,nf=Maxnum;
     while (i!=vs){
           if (c[fa[i]]           i=x[fa[i]];
     }
     flow+=nf;
     i=vt;
     while (i!=vs){
           c[fa[i]]-=nf;
           c[op[fa[i]]]+=nf;
           i=x[fa[i]];
     }
}

void sap(){
     for (int i=vs;i<=vt;i++){
         num[i]=0;
         d[i]=0;
         cur[i]=ls[i];
     }
     num[0]=vt+1;
     int i=vs;
     while (d[vs]           while (cur[i]>0)
             if (d[x[cur[i]]]==d[y[cur[i]]]+1 && c[cur[i]]>0)
               break;
             else
               cur[i]=next[cur[i]];
           if (cur[i]==0){
              num[d[i]]–;
              if (num[d[i]]==0) break;
              relabel(i);
              num[d[i]]++;
              if (i!=vs) i=x[fa[i]];
           }
           else{
              fa[y[cur[i]]]=cur[i];
              i=y[cur[i]];
              if (i==vt){
                 change();
                 i=vs;
              }
           }
     }
}

int main(){
    freopen("shut10.in","r",stdin);
    freopen("shut10.ans","w",stdout);
    init();
    sap();
    printf("%dn",s-flow);
}

线性规划与网络流之1 最大匹配

http://www.byvoid.com/blog/lpf24-solution/

这是线性规划与网络流的下载地址…

说明:

我都是不输出方案的

code:

#include using namespace std;
int m,n,g[101][101],v[101],link[101];

void Init(){
    cin >> m >> n;
    int x,y;
    while ((cin >> x >> y) && (x+y!=-2))
      g[x][y]=1;
}

bool Find(int k){
    for (int i=1;i<=n;i++)
      if (v[i]==0 && g[k][i]==1){
          v[i]=1;
          int q=link[i];
          link[i]=k;
          if (q==0 || Find(q)) return true;
          link[i]=q;
      }
    return false;
}

void Match(){
    memset(link,0,sizeof(link));
    int ans=0;
    for (int i=1;i<=m;i++){
        memset(v,0,sizeof(v));
        if (Find(i)) ans++;
    }
    if (ans==0) cout << "No Solution!" << endl;
           else cout << ans << endl;
}

int main(){
    freopen("air10.in","r",stdin);
    freopen("air10.ans","w",stdout);
    Init();
    Match();
    return 0;
}

SPOJ 726 大根堆+小根堆 || 平衡树

题目:

https://www.spoj.pl/problems/PRO/

题意描述:

总共N天,每天取已加入的数的最大值和最小值相减并累加到ans,并删掉这两个数。

数据保证每天至少有两个数可以删。

解题分析:

这题可以建两个堆,然后按题意模拟,但是用平衡树更方便。

我用的是SBT。比堆更简短。

插曲:

WA到2B去了。。。原来是要用INT64

code:

#include #include #include #define N 1000000
using namespace std;
struct sbttype{int l,r,w,s;}tr[N];
int a[N],tot=0,n,root=0;

void Left(int &p){
    int t=tr[p].r;
    tr[p].r=tr[t].l;
    tr[t].l=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void Right(int &p){
    int t=tr[p].l;
    tr[p].l=tr[t].r;
    tr[t].r=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void repair(int &p){
    bool flag=false;
    if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
        Left(tr[p].l);
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
        Left(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
        Right(tr[p].r);
        Left(p);
        flag=true;
    }
    if (flag){
        repair(tr[p].l);
        repair(tr[p].r);
        repair(p);
    }
}

void ins(int &p,int w){
    if (p==0){
        tr[++tot].l=0;
        tr[tot].r=0;
        tr[tot].s=1;
        tr[tot].w=w;
        p=tot;
        return;
    }
    if (w<=tr[p].w) ins(tr[p].l,w);
               else ins(tr[p].r,w);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

int del(int &p,int w){
    tr[p].s–;
    if (tr[p].w==w || tr[p].l==0 && w<=tr[p].w || tr[p].r==0 && w>tr[p].w){
        int delnum=tr[p].w;
        if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
        else tr[p].w=del(tr[p].l,0x7FFFFFFF);
        return delnum;
    }
    if (w<=tr[p].w) return del(tr[p].l,w);
               else return del(tr[p].r,w);
}

int getmax(int k){
    int p=k;
    while (tr[p].r!=0) p=tr[p].r;
    return tr[p].w;
}

int getmin(int k){
    int p=k;
    while (tr[p].l!=0) p=tr[p].l;
    return tr[p].w;
}

int main(){
      while (cin >> n){
        tot=0; root=0;
        long long ans=0;
        for (int i=1;i<=n;i++){
            int num;
            scanf("%d",&num);
            for (int j=1;j<=num;j++){
                int tmp;
                scanf("%d",&tmp);
                ins(root,tmp);
            }
            int tx=getmax(root),ty=getmin(root);
            ans+=(tx-ty);
            del(root,tx);
            del(root,ty);
        }
        cout << ans << endl;
      }
    return 0;
}

ZOJ 2112 线段树+平衡树

题意:

N<=50000 M<=10000

给定一个数组A[1]~A[N],有M个操作

每个操作可以如下

Q i j t 输出 A[I]~A[J]之间第t小的数

C i t 将A[I]赋值为t

解题分析:

线段树套一个平衡树,然后二分答案。

利用线段树和平衡树来求区间内<=这个数的数的个数。

复杂度O(M(lgN)^3)

code:

#include #include #define L(x) ((x)*2)
#define R(x) ((x)*2+1)
#define N 1000001
#define INF 0x7FFFFFFF/2-10
#define min(x,y) (x)<(y)?(x):(y)

struct SbtTreeType{int l,r,s,w;}tr[N];
struct InterZoneType{int l,r,root;}T[N];
int a[N],n,m,tot;

void Left(int &p){
    int t=tr[p].r;
    tr[p].r=tr[t].l;
    tr[t].l=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void Right(int &p){
    int t=tr[p].l;
    tr[p].l=tr[t].r;
    tr[t].r=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void repair(int &p){
    bool flag=false;
    if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
        Left(tr[p].l);
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
        Left(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
        Right(tr[p].r);
        Left(p);
        flag=true;
    }
    if (flag){
        repair(tr[p].l);
        repair(tr[p].r);
        repair(p);
    }
}

void ins(int &p,int w){
    if (p==0){
        tr[++tot].l=0;
        tr[tot].r=0;
        tr[tot].s=1;
        tr[tot].w=w;
        p=tot;
        return;
    }
    if (w<=tr[p].w) ins(tr[p].l,w);
               else ins(tr[p].r,w);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

int del(int &p,int w){
    tr[p].s–;
    if (tr[p].w==w || tr[p].l==0 && w<=tr[p].w || tr[p].r==0 && w>tr[p].w){
        int delnum=tr[p].w;
        if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
        else tr[p].w=del(tr[p].l,0x7FFFFFFF);
        return delnum;
    }
    if (w<=tr[p].w) return del(tr[p].l,w);
               else return del(tr[p].r,w);
}

void Build(int p,int l,int r){
    T[p].l=l; T[p].r=r; T[p].root=0;
    int i;
    for (i=l;i<=r;i++) ins(T[p].root,a[i]);
    if (l        int mid=(l+r)/2;
        Build(L(p),l,mid);
        Build(R(p),mid+1,r);
    }
}

void Change(int p,int pos,int pre,int key){
    if (pos    del(T[p].root,pre);
    ins(T[p].root,key);
    if (T[p].l        Change(L(p),pos,pre,key);
        Change(R(p),pos,pre,key);
    }
}

int rank(int p,int w){
    if (p==0) return 0;
    if (w    return (tr[tr[p].l].s+1+rank(tr[p].r,w));
}

int Getnum(int p,int l,int r,int x){
    if (r    if (l<=T[p].l && T[p].r<=r) return rank(T[p].root,x);
    int tx=Getnum(L(p),l,r,x),ty=Getnum(R(p),l,r,x);
    return (tx+ty);
}

void work(){
    int i;
    tot=0;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    Build(1,1,n);
    char ch;
    int il,ir,dj,x,y,l,r,mid;
    for (i=1;i<=m;i++){
        scanf("%c",&ch);
        while (ch==10 || ch==13) scanf("%c",&ch);
        if (ch!=’C’){
            scanf("%d%d%d",&il,&ir,&dj);
            l=-INF;
            r=INF;
            while (l                mid=(l+r)/2;
                if (Getnum(1,il,ir,mid)                                       else r=mid;
            }
            printf("%dn",l);
        }
        else {
            scanf("%d%d",&x,&y);
            Change(1,x,a[x],y);
            a[x]=y;
        }
    }
}

int main(){
    int TC;
    scanf("%d",&TC);
    int i;
    for (i=1;i<=TC;i++)
      work();
    return 0;
}

POJ 2985 并差集+SBT

题目大意:

有N只猫,M个操作。

操作种类如下:

0:把两只猫所在的组合并

1:数量第K大的组的数量是多少。

题目分析:

很容易想到用并差集合并组。但是至于那个第K大的组怎么求,可以用树状数组或者平衡树或者线段树。反正选一个用就好了。

插曲:

调了N久,发现delete操作之前没有真正理解。写错了。。。现在总算懂了。

实际上delete是会破坏SBT性质的。但是在插入的时候会修复。所以树的总高度将会是O(lgn),其中n为插入操作执行的次数。

code:

#include #include #define N 200001
using namespace std;
struct treetype{int w,l,r,s;} tr[N*4];
int n,operate,f[N],tot,root,num[N];

void Left(int &p){
    int t=tr[p].r;
    tr[p].r=tr[t].l;
    tr[t].l=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void Right(int &p){
    int t=tr[p].l;
    tr[p].l=tr[t].r;
    tr[t].r=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void repair(int &p){
    bool flag=false;
    if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
        Left(tr[p].l);
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
        Left(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
        Right(tr[p].r);
        Left(p);
        flag=true;
    }
    if (flag){
        repair(tr[p].l);
        repair(tr[p].r);
        repair(p);
    }
}

void ins(int &p,int w){
    if (p==0){
        tr[++tot].l=0;
        tr[tot].r=0;
        tr[tot].s=1;
        tr[tot].w=w;
        p=tot;
        return;
    }
    if (w<=tr[p].w) ins(tr[p].l,w);
               else ins(tr[p].r,w);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

int del(int &p,int w){
    tr[p].s–;
    if (tr[p].w==w || tr[p].l==0 && w<=tr[p].w || tr[p].r==0 && w>tr[p].w){
        int delnum=tr[p].w;
        if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
        else tr[p].w=del(tr[p].l,0x7FFFFFFF);
        return delnum;
    }
    if (w<=tr[p].w) return del(tr[p].l,w);
               else return del(tr[p].r,w);
}

int gf(int p){
    if (f[p]==p) return p;
    f[p]=gf(f[p]);
    return f[p];
}

int Find(int p,int k){
    if (tr[tr[p].r].s+1==k) return tr[p].w;
    if (tr[tr[p].r].s>=k) return Find(tr[p].r,k);
    return Find(tr[p].l,k-tr[tr[p].r].s-1);
}

void init(){
    tot=0; root=0;
    for (int i=1;i<=n;i++){
      f[i]=i;
      num[i]=1;
      ins(root,1);
    }
}

void work(){
    int op,x,y;
    for (int i=1;i<=operate;i++){
        scanf("%d",&op);
        if (op==0){
            scanf("%d%d",&x,&y);
            if (gf(x)==gf(y)) continue;
            if (num[f[x]]>num[f[y]]) swap(x,y);
            del(root,num[f[x]]);
            del(root,num[f[y]]);
            num[f[y]]+=num[f[x]];
            num[f[x]]=0;
            ins(root,num[f[y]]);
            f[f[x]]=f[y];
        }
        else{
            scanf("%d",&x);
            printf("%dn",Find(root,x));
        }
    }
}

int main(){
    scanf("%d%d",&n,&operate);
    init();
    work();
}