线性规划与网络流之4 抽象模型、网络流

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

分析：

把每根柱子上按顺序插的球当做是一条路径。然后这题变成了N个不相交路径最多可以覆盖多少连续的球。我们可以枚举答案。然后每次加入一个点。然后sap。直到不能覆盖。因为每次最多增加1的流量，所以sap会非常快。平均起来也就几乎O(N)每一次

code:

#include #include #define E 2222222
#define N 111111
#define sqr(x) (x)*(x)
using namespace std;

struct gtp{int x,y,next,c,op;} g[E];
int n,e=0,ls[N],S=0,T=1,p=1,Flow=0,cur[N],fa[N],d[N],num[N];

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

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

void change(){
     int i;
     i=T;
     while (i!=S){
           g[fa[i]].c–;
           g[g[fa[i]].op].c++;
           i=g[fa[i]].x;
     }
     Flow++;
}

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

bool Try(int k){
     p++;
     add(S,p,1);
     p++;
     add(p,T,1);
     for (int i=1;i       if (sqr((int)(sqrt(i+k)+0.5))==i+k)
         add(i<<1,p,1);
     sap();
     if (k-Flow<=n) return true;
     return false;
}

int main(){
    freopen("ball10.in","r",stdin);
    freopen("ball10.ans","w",stdout);
    cin >> n;
    for (int i=1;i<=99999;i++)
        if (!Try(i)){
          cout << i-1 << endl;
          return 0;
        }
}